hashmap底层实现原理1.8 HashMap底层原理分析

本文将从以下方面结合源码进行分析：自动扩容、初始化与懒加载、哈希计算、位运算（默认采用JDK1.8）。自动扩容扩容操作发生在putVal最后部分，在增加元素后才判断是否需要扩容，如果超过阈值，会自动扩容。

文章插图
这里扩容都是<<1翻倍进行扩容的。

文章插图
扩容时节点数组进行数据转移的三种情况：

节点的元素无后继节点：

直接根据节点hash值重新计算下标,然后复制到新的数组中。

文章插图

节点为树节点：

进行红黑树的扩容操作。

文章插图
因为capacity变化后，hash&(cap-1)可能得到不同结果。原有的红黑树变成高低位两个红黑树。低位红黑树下标位置和旧数组相同，高位红黑树下标位置在旧数组的基础上+oldCap，因为hash&(2*cap-1)结果等于hash&(cap-1)或者hash&(cap-1)+cap 。

文章插图
红黑树扩容时遍历原有链表，然后根据新的hash值重新分为低位链表和高位链表。若所有元素都在低位链表或高位链表，则不需要重新树化，直接将链表头节点插入数组对应位置；若低位链表或高位链表的数量<7，则深拷贝低位或高位树节点链表得到普通节点新链表（低位或高位树节点链表含有树的偏序关系，拷贝得到的普通节点链表只有链表的偏序关系），并将新链表头节点插入数组对应位置。如果数量>=7则深拷贝低位或高位树节点链表得到普通节点新链表，再进行树化。具体源码分析如下： 1 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 2// 获取自身树节点 3TreeNode<K,V> b = this; 4// Relink into lo and hi lists, preserving order 5// 低位链表的头尾节点 6TreeNode<K,V> loHead = null, loTail = null; 7// 高位链表的头尾节点 8TreeNode<K,V> hiHead = null, hiTail = null; 9// 低位链表节点数量、高位链表节点数量10int lc = 0, hc = 0;11for (TreeNode<K,V> e = b, next; e != null; e = next) {12next = (TreeNode<K,V>)e.next;13// 这步操作不是多余的，在e为低位或高位链表最终尾节点时起到赋空作用14e.next = null;15// 如果仍然在原位置，则加入低位链表16if ((e.hash & bit) == 0) {17if ((e.prev = loTail) == null)18loHead = e;19else20loTail.next = e;21loTail = e;22++lc;//低位链表数量+123}24else {25// 如果是在新的位置(原索引值+oldcap)，加入高位链表26if ((e.prev = hiTail) == null)27hiHead = e;28else29hiTail.next = e;30hiTail = e;31++hc;// 高位链表数量+132}33}34// 低位链表不为空35if (loHead != null) {36// 低位链表数量不超过6，则深拷贝低位树节点链表得到普通节点新链表，并将新链表头部放入数组37if (lc <= UNTREEIFY_THRESHOLD)38tab[index] = loHead.untreeify(map);39else {40tab[index] = loHead;41// 如果高位链表为空，说明全部元素都在低位链表中，因为原链表已经是树化的了，所以不用再转为红黑树42if (hiHead != null) // (else is already treeified)43loHead.treeify(tab);44}45}46// 高位链表不为空47if (hiHead != null) {48// 高位链表数量不超过6，则深拷贝树节点高位链表得到普通节点新链表，并将新链表头部放入数组49if (hc <= UNTREEIFY_THRESHOLD)50tab[index + bit] = hiHead.untreeify(map);51else {52tab[index + bit] = hiHead;53// 如果低位链表为空，说明全部元素都在高位链表中，因为原链表已经是树化的了，所以不用再转为红黑树54if (loHead != null)55hiHead.treeify(tab);56}57}58 }

节点为链表节点：

进行链表的复制操作。操作和红黑树扩容操作非常相似。也是先遍历原有链表节点，然后根据新的hash值分为低位链表和高位链表。分完高低位链表后，将头节点插入数组对应位置即可。具体源码分析如下： 1 // case3：节点为链表节点，进行链表的赋值操作2 else { // preserve order 3// 低位Node链表头节点和尾节点 4Node<K,V> loHead = null, loTail = null; 5// 高位Node链表头节点和尾节点 6Node<K,V> hiHead = null, hiTail = null; 7Node<K,V> next; 8// 遍历原链表，拆分成低位链表和高位链表 9do {10next = e.next;11// 如果是在原位置，则加入低位链表12if ((e.hash & oldCap) == 0) {13if (loTail == null)14loHead = e;15else16loTail.next = e;17loTail = e;18}19else {20// 如果不在原位置，加入高位链表21if (hiTail == null)22hiHead = e;23else24hiTail.next = e;25hiTail = e;26}27} while ((e = next) != null);28// 如果低位链表不为空29if (loTail != null) {30// 尾部节点赋空并将头部节点放入数组指定位置31loTail.next = null;32newTab[j] = loHead;33}34// 如果高位链表不为空35if (hiTail != null) {36// 尾部节点赋空并将头部节点放入数组指定位置37hiTail.next = null;38newTab[j + oldCap] = hiHead;39}40 }　在jdk1.8之前，hashmap在多线程环境中使用会出现死链问题。如果有多个线程同时进行扩容操作，一个线程拿到链表头节点和后继节点时挂起，另一个线程执行完扩容操作，会使得这两个节点互相依赖，出现死链，导致第一个线程不能退出循环，CPU使用率飙升。
jdk1.8将原来的头插法改为了尾插法，同时复制链表时不再是遍历一个节点就插入，而是使用高低位链表。待遍历完所有节点后，再将高低位链表放入新数组对应位置。
但是仍然不建议在多线程环境下使用，仍然会有数据缺失和数据重复等等问题。
初始化与懒加载hashmap节点数组的定义和初始化不会在构造函数中完成，而是在首次执行put()操作时才完成的。1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,2boolean evict) {3Node<K,V>[] tab; Node<K,V> p; int n, i;4// 如果节点数组未初始化或为空，则进行初始化操作5if ((tab = table) == null || (n = tab.length) == 0)6n = (tab = resize()).length;resize()中会设置默认的初始化容量DEFAULT_INITIAL_CAPACITY为16，扩容的阈值为0.75*16 = 12，即哈希桶数组中元素达到12个便进行扩容操作。最后创建容量为16的Node数组，并赋值给成员变量哈希桶table，即完成了HashMap的初始化操作。1 final Node<K,V>[] resize() { 2// 获取原有table 3Node<K,V>[] oldTab = table; 4int oldCap = (oldTab == null) ? 0 : oldTab.length; 5int oldThr = threshold; 6// 新容量、新阈值 7int newCap, newThr = 0; 8...................... 9else {// zero initial threshold signifies using defaults10// 原容量和阈值都<=0,则用默认值初始化,默认容量16，负载因子0.75，对应的是hashmap没带参数初始化。11newCap = DEFAULT_INITIAL_CAPACITY;12newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);13}哈希计算null的hash值为0 。计算key的hash值时先获取key的32位hashCode，然后将hashcode&(hashcode>>>16),等效于高16位不变，高16位与低16位作异或，结果为新的低16位。将高16位与低16位进行异或的操作称之为扰动函数，目的是将高位的特征融入到低位之中，降低哈希冲突的概率。【hashmap底层实现原理1.8 HashMap底层原理分析】1 static final int hash(Object key) {2int h;3return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);4 }ConcurrentHashMap中经过扰乱函数处理之后，需要与HASH_BITS做与运算，HASH_BITS为0x7ffffff，即只有最高位为0，这样运算的结果使hashCode永远为正数。在ConcurrentHashMap中，预定义了几个特殊节点的hashCode，如：MOVED、TREEBIN、RESERVED，它们的hashCode均定义为负值。因此，将普通节点的hashCode限定为正数，也就是为了防止与这些特殊节点的hashCode产生冲突。
1 static final int MOVED= -1; // hash for forwarding nodes2 static final int TREEBIN= -2; // hash for roots of trees3 static final int RESERVED= -3; // hash for transient reservations4 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash5 static final int spread(int h) {6return (h ^ (h >>> 16)) & HASH_BITS;7 }哈希冲突如有多个key计算得到的hashCode相同，就会产生hash冲突。jdk1.8的hashmap使用了链表法和红黑树去处理hash冲突。当出现hash冲突时，将新插入的节点通过尾插法插入到链表的尾部。当链表的长度超过8且数组的capacity>=64则将链表转为红黑树。1// 如果链表的数量超过了8,且数组cap大小>=64则转为红黑树 2// 如果链表数量超过了8，但数组cap大小<64则resize()扩容 3if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 4treeifyBin(tab, hash); 56final void treeifyBin(Node<K,V>[] tab, int hash) { 7int n, index; Node<K,V> e; 8// 如果数组长度没达到64就扩容 9if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)10resize();位运算计算数组大小的方法，给定一个输出值，找到大于等于给定值的最小的2^n 。1 static final int tableSizeFor(int cap) {2int n = cap - 1;3n |= n >>> 1;4n |= n >>> 2;5n |= n >>> 4;6n |= n >>> 8;7n |= n >>> 16;8return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;9 }这里是实现了找>=cap的最小2^n 。cap为int类型，长度32位。对于一个正数，找大于该数的最小的2^n,都可以采用这种方式,将n最高位后面全部置为1，然后加1，因为位运算非常快速，这种方法比找到最高位然后构造新的数要更快。至于数组大小设置为2^n，是为了提高数组的空间利用率。计算索引的方法是hash&(cap-1)，当cap为2^n,cap-1为00001111(忽略前置0）的形式，这样得到的索引位置为[0,cap-1],每一个位置都由机会。如果cap不为2^n,比如15，那么cap-1为00001110,计算得到的索引只有0，2，4，6，8，10，12，14这些位置，空间利用率只有50% 。