HashMap底层结构和实现原理

谁借莪１个温暖的怀抱￠ 2023-07-07 08:43 59阅读 0赞

## jdk1.8的HashMap的底层结构 ##

1.  HashMap的结构是数组+链表+红黑树
2.  当数组中的元素发生hash冲突的时候，当前相同的下标的数组元素上会形成链表结构，jdk1.8采用的是尾插法即在每个entry后依次加入新的entry,增加nextnode指向下一个entry。  
    ![HashMap机构图][HashMap]
3.  当链表中的元素大于等于8个时候会形成红黑树结构，（这也是jdk1.7和1.8的主要区别之一）。
4.  **红黑树**虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的**时间复杂度最坏为O(log n)。加快检索速率**。

## HashMap底层实现机制 ##

例子：

HashMap<String,String>map = new HashMap<>();
    map.put("杨过","小龙女");

以上map为例子，计算key的index的过程如下：  
1.计算key.hashCode()也就是"杨过".hashCode();  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70]  
2.用得到的hashcode进行二进制转换为32位来计算，高位补12个零够32位：  
1101 0001 0101 0101 1111补零后得：0000 0000 0000 1101 0001 0101 0101 1111  
3.32位的二进制hashcode右移16位即：1101 0001 0101 0101 1111右移16位后是  
0000 0000 0000 0000 0000 0000 0000 0000 1101（高位补16个零,超出32位溢出部分去掉）；  
3.hashcode值和右移之后的二进制进行异或运算（相同为0，不同为1）得到hash值。  
int i = hashCode ^ (hashCode >>> 16);  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 1]  
4.用得到的hash值去和arr.length-1去做&运算，（数组初始化后默认大小是16，不减去1的话无论hash值如何变化，都会和10000做&运算，都会分布到0或15的下标下）即15&hash值得到key在数组中的下标是2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 3]  
以上运算可以在数据量大的时候，尽量去避免大量的hash碰撞，使得每个元素都尽量分散地分布在数组的各个下标中。因为哈希碰撞后会形成链表，链表结构的查询时间复杂度是n。

## HashMap进行put操作的源码步骤 ##

1.  判断数组有没有初始化，没有的话去进行初始化
2.  初始化后的数组，判断当前计算出的index下标是不是为null,如果为null就创建新的节点。然后把数据放到node下。
3.  如果当前index下不是null,就去判断当前的key是不是已经存在，如果已经存在就会把旧的value替换成最新的value;  
    如果当前key不存在就会去判断当前的数据类型如果是红黑树的话就往红黑树里放入元素。如果是链表的数据类型就去遍历整个链表，如果链表的长度达到8的时候，此时链表就会转成红黑树，如果遍历过程中有相同的key就会替换旧的value,否则就把新的value追加到链表的末尾。
4.  最后，判断当前的HashMap的容量是不是已经达到了扩容的阈值，如果达到的话就调用resize()方法去扩容。

[HashMap]: https://img-blog.csdnimg.cn/20200222113950825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222135311102.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200222140108650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200222145345651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200222145536419.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUwNzMyNA==,size_16,color_FFFFFF,t_70