【JAVA-哈希表实现】_java实现哈希表

/**
 * 哈希表：
 * 节点类：Node类
 * 属性：
 * 存储结构-节点数组
 * 元素个数
 * 存储结构数组被占用的格子数量
 * 默认初始长度 16
 * 扩容阈值 0.75
 * 数组长度
 * 方法：
 * put: 存储
 * resize(); 扩容
 * get: 获取
 *
 * @param <K>
 * @param <V>
 */
class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;
    int hash;// K的hash值
    public Node(K key, V value, int hash) {
        this.key = key;
        this.value = value;
        this.hash = hash;
    }
}
public class MyHashMap<K,V> {
    private Node<K, V>[] table;
    private int modCount;// 数组被占用的格子数量
    private int elmSize;// 元素个数
    private int capacity;// 数组的容量
    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;
 
    /**
     * 构造方法 根据传进来的容量进行初始化哈希表
     *
     * @param initCapacity
     */
    public MyHashMap(int initCapacity) {
        if (initCapacity < DEFAULT_CAPACITY) {
            initCapacity = DEFAULT_CAPACITY;
        }
        table = new Node[initCapacity];
        capacity = initCapacity;
        elmSize = 0;
        modCount = 0;
    }
 
    public V get(K key) {
        int h = key.hashCode();
        int index = h & (capacity - 1);
        Node<K, V> first = table[index];
        // 判断 目标位置的节点是否为null
        if (first != null) {
            // 判断 first 是否是咱们需要的节点
            // 1： 哈希值一致 才需要比较后面的
            // 2： 接着比较key的引用地址 如果地址一致 就不需要比较内容
            // 3： 地址不一致的情况会存在内容一致的情况 使用equals比较
            if (first.hash == h && first.key == key || first.key.equals(key)) {
                return first.value;
            }
            // 第一个节点比较不成功 从这个节点开始作为头节点遍历链表
            Node temp = first;// 此处与java底层实现有区别：判断 first 是链表节点（写循环进行遍历）还是红黑树节点（写方法去遍历红黑树）
            while (temp.next != null) {
                temp = temp.next;
                if (temp.hash == h && temp.key == key || temp.key.equals(key)) {
                    return (V) temp.value;
                }
            }
        }
        return null;
    }
 
    /**
     * 设置元素 用键值对进行存放
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
//        System.out.println("Put");
        int h = key.hashCode();// 计算Key 的hash
        Node<K, V> elmNode = new Node<>(key, value, h);// 新节点
        int index = h & (capacity - 1);// 根据hash值 与 数组长度 得到下标
        // System.out.println(index);
        Node<K, V> first = table[index];
        if (first == null) {
            table[index] = elmNode;
            modCount++;
            elmSize++;
        } else {
            Node<K, V> oldNode = null;
            // 如果first 与 新节点的key一致 更新 first节点的v
            if (first.hash == h && first.key == key || first.key.equals(key)) {
                first.value = value;
                oldNode = new Node<>(key, first.value, h);
            } else {
                Node<K, V> temp = first;
                while (temp.next != null) {
                    temp = temp.next;
                    if (temp.hash == h && temp.key == key || temp.key.equals(key)) {
                        temp.value = value;
                        oldNode = new Node<>(key, temp.value, h);
                        break;
                    }
                }
                if (oldNode == null) {// 新增节点
                    temp.next = elmNode;
                    elmSize++;
                }
            }
        }
// 扩容： 数组的被占用格子数 比例大于数组容量的百分之75的时候扩容
        if (modCount >= capacity * LOAD_FACTOR) {
            resize();
        }
    }
 
    /**
    *      扩容：
    *      扩容 2倍扩容
    *      创建一个更大的数组 将原本的所有元素存储进去
     *      (每个元素取出 重新映射位置 因为放置进去时是根据 int index = h & (capacity - 1); capacity放置的，扩容后capacity发生改变)
    *      每个元素存储的位置与当前数组的长度capacity相关
     *     写函数时，如果出现问题，自己重新写一遍
    */
 
    private void resize() {
        System.out.println("扩容进入：" + capacity);
        modCount = 0;
        elmSize = 0;
        int oldCapacity = capacity;
        int newCapacity = oldCapacity + oldCapacity; //加法比乘法快
        Node<K, V>[] oldTable = table;
        Node<K, V>[] newTable = new Node[newCapacity];
 
        //把表中的数据取出来一个一个放到新的表中去
        for (int i = 0; i < oldCapacity; i++) {
//            System.out.println("扩容循环");
            // 取出旧节点
            Node<K, V> node = oldTable[i];
 
            //此处与对比处的bug进行对比
            //取出旧表中的一个node，看这个node的头是否为空。如果头为空，设置该节点放入元素；如果头不为空，循环遍历到链表尾部，尾部下一个节点设置为该节点放入元素
            //如果oldTable中node为空，则不考虑
            while (node != null) {
                Node<K, V> newNode = new Node<>(node.key, node.value, node.hash);
                System.out.println("遍历旧数组中的链表");
                int h = node.hash;
                System.out.println("旧数组中元素重新进行映射");
                int index = h & (newCapacity - 1);
                Node<K, V> first = newTable[index];
                if (first == null) {
                    newTable[index] = newNode;
                    elmSize++;
                    modCount++;
                } else {
                    System.out.println("新数组目标位置是一条链表");
                    Node<K, V> temp = first;
                    while (temp.next != null) {
                    // System.out.println("temp.next !=null");
                    // System.out.println(temp.value);
                        temp = temp.next;
                    }
                    temp.next = newNode;
                    elmSize++;
                }
                node = node.next;
            }
        }
        //更新全局的 哈希表与容量
        table = newTable;
        capacity = newCapacity;
        System.out.println("扩容：" + capacity);
    }
 
    /**
     * 测试存储以及输出
     * @param args
     */
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>(16);
        for (int i = 0; i < 100; i++) {
            map.put("Hello" + i, i);    //存进去的字符Hello是哈希值就比较大了
        }
        System.out.println("数组长度：" + map.capacity);
        System.out.println("数组被占用格子数量：" + map.modCount);
        System.out.println("元素个数：" + map.elmSize);
    }
 
}