Java HashMap底层实现

深藏阁楼爱情的钟 2022-05-03 02:25 235阅读 0赞

Java HashMap底层实现

## HashMap的底层物理结构： ##

Entry 数组 
    JDK1.7 数组+链表
    JDK1.8 数组+链表/红黑树

## Hash table–散列表的原理 ##

在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，
    哈希表	的主干就是数组。哈希表的事件复杂度为O(1)，在不考虑冲突的情况下，
    可以非常快速找到。

**存储位置 = f(关键字)**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTAxMDIzNDk5MQ_size_27_color_FFFFFF_t_70]

## HashMap实现原理 ##

### (1)数组元素类型 ###

HashMap维护了一个长度为2的幂次方的Entry类型的数组table,数组的每一个元素成为
    	桶（bucket）,添加的数据最终都会被封装成一个Map.Entry类型的对象，放在table[index]
    	桶中transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

(\`\`\`)

JDK1.7

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
     //...省略
    }

JDK1.8

transient Node<K,V>[] table;
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    //...省略
    }

(\`\`\`)

### 重要字段 ###

初始化容量 :16	
    扩展为原来的:2倍
    //实际存储的key-value键值对的个数
    transient int size;
    //阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap
    在进行扩容时需要参考threshold，后面会详细谈到
    int threshold;
    //负载因子，代表了table的填充度有多少，默认是0.75
    final float loadFactor;
    //用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他
    线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常	ConcurrentModificationException
    transient int modCount;

### HashMap的映射原理 ###

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
           
    }
      在hash()中，一个32位整数无符号右移16位>>>16, 然后 h = h ^(h>>>16),这样异或操作  
      保留了高位的16位，然后 index = hash &(length-1),使得结果一定在[0,n-1]范围。

### JDK1.8的put存储过程 ###

*  先计算key的hash值，如果key是null ， hash值直接为0，否则就按照 ( h = key.hashCode()) ^(h >>>16)得到hash 值
 *  如果table是空的，先初始化table数组；
 *  通过hash值计算存储的索引位置index = hash & (table.length-1)
 *  如果table\[index\]==null，那么直接创建一个Node结点存储到table\[index\]中即可
 *  如果table\[index\]!=null，并且table\[index\]是一个TreeNode结点，说明table\[index\]下是一棵红黑树，如果该树的某个结点的key与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），那么用新的value替换原来的value，否则将(key,value)封装为一个TreeNode结点，连接到红黑树中
 *  如果table\[index\]不是一个TreeNode结点，说明table\[index\]下是一个链表，如果该链表中的某个结点的key与新的key“相同”，那么用新的value替换原来的value，否则需要判断table\[index\]下结点个数，如果没有达到TREEIFY\_THRESHOLD(8)个，那么(key,value)将会封装为一个Node结点直接链接到链表尾部。
 *  如果table\[index\]下结点个数已经达到TREEIFY\_THRESHOLD(8)个，那么再判断table.length是否达到MIN\_TREEIFY\_CAPACITY(64)，如果没达到，那么先扩容，扩容会导致所有元素重新计算index，并调整位置；
 *  如果table\[index\]下结点个数已经达到TREEIFY\_THRESHOLD(8)个并table.length也已经达到MIN\_TREEIFY\_CAPACITY(64)，那么会将该链表转成一棵自平衡的红黑树，并将结点链接到红黑树中。
 *  如果新增结点而不是替换，那么size++，并且还要重新判断size是否达到threshold阈值，如果达到，还要扩容。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTAxMDIzNDk5MQ_size_27_color_FFFFFF_t_70]: /images/20220503/a95a612700d74c1ca96dfb1979ff3d59.png