HashMap扩容 JDK1.8的rehash算法优化

ゝ一世哀愁。 2023-07-17 07:26 15阅读 0赞

HashMap的底层数据结构是数组，如果发生了hash冲突的话，会采用拉链法，将数组中的节点挂载成一个链表，JDK1.8之后如果链表节点数量太多，超过阈值8的话，就会转化为红黑树。因为HashMap在遍历key的时候，如果是链表的话，会循环遍历整个链表，时间复杂度是O(n)，效率较低，使用红黑树的话，时间复杂度是O(logn)，可以有效提升效率

好像有点跑题了，主要是想说HashMap的底层其实是一个数组，既然是一个数组，必然长度是固定的，也就一定存在扩容的问题。在JDK1.7的时候，是将数组扩容为两倍，然后将HashMap中所有的key重新进行hash寻址然后再放入到新的位置

在JDK1.8的时候，扩容同样是按照两倍的大小进行扩容，同时将hash算法、hash寻址算法进行了优化（可以参考我的这篇文章 [HashMap简析][HashMap]）rehash算法，也就是扩容后重新为里面的键值对寻址的算法也优化了  
举个例子，首先你得知道hash寻址算法是 index =（n - 1） & hash，n是数组的容量，hash是key的hash值，这里以默认数组长度16来计算  
![1][]  
上面进行hash寻址之后，就可以得到key的位置index是12（1100的十进制）  
![2][]  
此时，上面两个key会出现hash碰撞的问题，因为计算出来的index是一样的，此时需要使用链表，或者是红黑树来解决

如果数组的长度扩容之后 ，也就是容量变为了32，重新对每个hash值进行寻址  
![3][]  
![4][]  
通过上面的例子，我们可以发现一个规律，每次扩容之后，n - 1这个值的二进制最右边的0变为了1，我用红色标注出来的那个1就是扩容之后改变的  
这时hash值的对应位置的值是0还是1就会影响最终这个key所在的位置，我用绿色标注出来了，对比一下上面没有扩容时的结果  
未扩容时，这个位置的值无论是0还是1对最终的结果都没有影响，因为对应的 n - 1的这个位置的值是0，进行&操作之后，无论何时都是0  
而扩容之后这个位置的hash值，如果是0，那么rehash之后还是在原来的位置index；如果是1，那么rehash之后的位置是原来的位置 + 扩容前的数组容量，即index + oldCap  
所以扩容之后，存在两种情况，一种情况下，key的位置不变，另外一种情况，key的位置往后移动了原先数组长度的位置

在JDK1.8的HashMap的源码中，也将rehash算法最后寻址分为了两种情况  
我们这里讨论一下数组中存在链表的情况，数组中当前位置只有一个节点（简单的没必要说）和红黑树（难的我也不会）的情况这里就不拿出来说了，有兴趣的老哥可以自己去看HashMap的resize()扩容方法  
源码中的处理方式是将未扩容之前的链表rehash之后重新拆分为了两个链表，一个链表rehash之后还是在当前的位置index，另一个链表rehash之后的位置变成了index + oldCap，画个图理解一下  
![链表扩容][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xPX1lVTg_size_16_color_FFFFFF_t_70]  
使用这种方式明显要比把一个个的key重新寻址要快，效率要高，这就是HashMap在JDK1.8中的rehash算法优化

[HashMap]: https://blog.csdn.net/LO_YUN/article/details/103541474
[1]: /images/20230528/8455e25a5a184de290f6fcc72ff32758.png
[2]: /images/20230528/8a9e8a672fdf4c62aa795e850f4ef013.png
[3]: /images/20230528/aeb7883bfa9f41359c147c9b87458625.png
[4]: /images/20230528/8add943d2b7044ba8a720de480c62724.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xPX1lVTg_size_16_color_FFFFFF_t_70]: /images/20230528/b0d797e6217a466eac6bb83f5e3d3e7e.png