HashMap底层实现原理概述

原文https://blog.csdn.net/fedorafrog/article/details/115478407

hashMap结构

常见问题

在理解了HashMap的整体架构的基础上，我们可以试着回答一下下面的几个问题，如果对其中的某几个问题还有疑惑，那就说明我们还需要深入代码，把书读厚。

• HashMap内部的bucket数组长度为什么一直都是2的整数次幂
• HashMap默认的bucket数组是多大
• HashMap什么时候开辟bucket数组占用内存
• HashMap何时扩容？
• 桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？
• Java 8中为什么要引进红黑树，是为了解决什么场景的问题？
• HashMap如何处理key为null的键值对？

new HashMap()

在JDK 8中，在调用new HashMap()的时候并没有分配数组堆内存，只是做了一些参数校验，初始化了一些常量

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

tableSizeFor的作用是找到大于cap的最小的2的整数幂，我们假设n(注意是n，不是cap哈)对应的二进制为000001xxxxxx，其中x代表的二进制位是0是1我们不关心，

可以看到此时n的二进制最高两位已经变成了1（1和0或1异或都是1），再接着执行第二行代码：

可见n的二进制最高四位已经变成了1，等到执行完代码n |= n >>> 16;之后，n的二进制最低位全都变成了1，也就是n = 2^x - 1其中x和n的值有关，如果没有超过MAXIMUM_CAPACITY，最后会返回一个2的正整数次幂，因此tableSizeFor的作用就是保证返回一个比入参大的最小的2的正整数次幂。

这里我们也回答了开头提出来的问题：

HashMap什么时候开辟bucket数组占用内存？答案是在HashMap第一次put的时候，无论Java 8还是Java 7都是这样实现的。

为什么桶数组的大小都是2的正整数幂？

Hash

在HashMap这个特殊的数据结构中，hash函数承担着寻址定址的作用，其性能对整个HashMap的性能影响巨大，那什么才是一个好的hash函数呢？

• 计算出来的哈希值足够散列，能够有效减少哈希碰撞
• 本身能够快速计算得出，因为HashMap每次调用get和put的时候都会调用hash方法

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

异或是相加

这里比较重要的是(h = key.hashCode()) ^ (h >>> 16)，这个位运算其实是将key.hashCode()计算出来的hash值的高16位与低16位继续异或，为什么要这么做呢？

我们知道hash函数的作用是用来确定key在桶数组中的位置的，在JDK中为了更好的性能，通常会这样写：

index =(table.length - 1) & key.hash();

& 运算是相乘

回忆前文中的内容，table.length是一个2的正整数次幂，类似于000100000，这样的值减一就成了000011111，通过位运算可以高效寻址，

这也回答了前文中提到的一个问题，HashMap内部的bucket数组长度为什么一直都是2的整数次幂？好处之一就是可以通过构造位运算快速寻址定址。

回到本小节的议题，既然计算出来的哈希值都要与table.length - 1做与运算，那就意味着计算出来的hash值只有低位有效，这样会加大碰撞几率，因此让高16位与低16位做异或，让低位保留部分高位信息，减少哈希碰撞。

Put

在Java 8中put这个方法的思路分为以下几步：

1、调用key的hashCode方法计算哈希值，并据此计算出数组下标index
2、如果发现当前的桶数组为null，则调用resize()方法进行初始化
3、如果没有发生哈希碰撞，则直接放到对应的桶中
4、如果发生哈希碰撞，且节点已经存在，就替换掉相应的value
5、如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上
6、如果碰撞后为链表，添加到链表尾，如果链表长度超过TREEIFY_THRESHOLD默认是8，则将链表转换为树结构
7、数据put完成后，如果HashMap的总数超过threshold就要resize

public V put(K key, V value) {// 调用上文我们已经分析过的hash方法return putVal(hash(key), key, value, false, true);
}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)// 第一次put时，会调用resize进行桶数组初始化n = (tab = resize()).length;// 根据数组长度和哈希值相与来寻址，原理上文也分析过if ((p = tab[i = (n - 1) & hash]) == null)// 如果没有哈希碰撞，直接放到桶中tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 哈希碰撞，且节点已存在，直接替换e = p;else if (p instanceof TreeNode)// 哈希碰撞，树结构e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 哈希碰撞，链表结构for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 链表过长，转换为树结构if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 如果节点已存在，则跳出循环break;// 否则，指针后移，继续后循环p = e;}}if (e != null) { // existing mapping for key// 对应着上文中节点已存在，跳出循环的分支// 直接替换V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)// 如果超过阈值，还需要扩容resize();afterNodeInsertion(evict);return null;
}

resize（）

resize是整个HashMap中最复杂的一个模块，如果在put数据之后超过了threshold的值，则需要扩容，扩容意味着桶数组大小变化，我们在前文中分析过，HashMap寻址是通过index =(table.length - 1) & key.hash();来计算的，现在table.length发生了变化，势必会导致部分key的位置也发生了变化，HashMap是如何设计的呢？

通过这个分析可以看到如果在即将扩容的那个位上key.hash()的二进制值为0，则扩容后在桶中的地址不变，否则，扩容后的最高位变为了1，新的地址也可以快速计算出来newIndex = oldCap + oldIndex;

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 如果oldCap > 0则对应的是扩容而不是初始化if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 没有超过最大值，就扩大为原先的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in threshold// 如果oldCap为0， 但是oldThr不为0，则代表的是table还未进行过初始化newCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {// 如果到这里newThr还未计算，比如初始化时，则根据容量计算出新的阈值float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {// 遍历之前的桶数组，对其值重新散列Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 如果原先的桶中只有一个元素，则直接放置到新的桶中newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order// 如果原先的桶中是链表Node<K,V> loHead = null, loTail = null;// hiHead和hiTail代表元素在新的桶中和旧的桶中的位置不一致Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;// loHead和loTail代表元素在新的桶中和旧的桶中的位置一致newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;// 新的桶中的位置 = 旧的桶中的位置 + oldCap， 详细分析见前文newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

总结

HashMap什么时候开辟bucket数组占用内存？

答案是在HashMap第一次put的时候，无论Java 8还是Java 7都是这样实现的。

为什么hashMap大小必须是2的次幂？

好处1:
那得从她的结构说起，当put，get的时候，内部会通过对key进行hash运算，运算结果是二进制低位有效，然后对 （数组大小-1 ）（低位有效）进行& 运算（相乘）实际上得到的结果就会映射到 数组大小之内，因此数组大小定义为2的次幂，能够快速的定位寻址，除此之外，其中的位运算也是为了加快处理速度。

好处2
在HashMap扩容的时候可以保证同一个桶中的元素均匀地散列到新的桶中，具体一点就是同一个桶中的元素在扩容后一般留在原先的桶中，一般放到了新的桶中。

HashMap默认的bucket数组是多大？

默认是16，即时指定的大小不是2的整数次幂，HashMap也会找到一个最近的2的整数次幂来初始化桶数组。

HashMap何时扩容？

答：当HashMap中的元素熟练超过阈值时，阈值计算方式是capacity * loadFactor，在HashMap中loadFactor是0.75

桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？

答：当同一个桶中的元素数量大于等于8的时候元素中的链表转换为红黑树，反之，当桶中的元素数量小于等于6的时候又会转为链表，这样做的原因是避免红黑树和链表之间频繁转换，引起性能损耗

Java 8中为什么要引进红黑树，是为了解决什么场景的问题？

答：引入红黑树是为了避免hash性能急剧下降，引起HashMap的读写性能急剧下降的场景，正常情况下，一般是不会用到红黑树的，在一些极端场景下，假如客户端实现了一个性能拙劣的hashCode方法，可以保证HashMap的读写复杂度不会低于O(lgN)
public int hashCode() {
return 1;
}

HashMap如何处理key为null的键值对？

答：放置在桶数组中下标为0的位置

在Java 8中put这个方法的思路分为以下几步：

1、调用key的hashCode方法计算哈希值，并据此计算出数组下标index
2、如果发现当前的桶数组为null，则调用resize()方法进行初始化
3、如果没有发生哈希碰撞，则直接放到对应的桶中
4、如果发生哈希碰撞，且节点已经存在，就替换掉相应的value
5、如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上
6、如果碰撞后为链表，添加到链表尾，如果链表长度超过TREEIFY_THRESHOLD默认是8，则将链表转换为树结构
7、数据put完成后，如果HashMap的总数超过threshold就要resize