HashMap超详细分析

柔情只为你懂 2023-10-05 14:38 9阅读 0赞

特点：

1.存取无序的

2.键和值位置都可以是null，但是键位置只能是一个null

3.键位置是唯一的，底层的数据结构控制键的

4.jdk1.8前数据结构是：链表 + 数组 jdk1.8之后是 ： 链表 + 数组 + 红黑树

5.阈值(边界值) > 8 并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

# 存放数据步骤： #

1）先通过hash值计算出key映射到哪个桶；

2）如果桶上没有碰撞冲突，则直接插入；

3）如果出现碰撞冲突了，则需要处理冲突：

a:如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
    
    b:否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；

4）如果桶中存在重复的键，则为该键替换新值value；

5）如果size大于阈值threshold，则进行扩容；

## 第一步：首次插入元素 ##

1.1 [ 通过key调用String类中的hashCode()方法计算出hash值][_key_String_hashCode_hash]。  
1.2 hash值与数组长度减一做按位与运算得到[数组下标索引。][Link 1]  
1.3 如果此位置上数据为空，将元素放入。

## 第二步： ##

2.1如果数组下标相同，比较hash值，  
2.2 hash值不同，向下生成一个链表放入数据  
hash值相同，产生hash碰撞，进一步实用equals()方法，比较内容是否相同  
相同：新的value覆盖旧的value  
不相同：向下比较链表中元素，不同将新的键值对放入链表中。

## 第三步： ##

在不断添加数据过程中，[数组中元素个数大于阈值12时，会对数组长度2倍扩容][12_2]，将原有的数据赋值过来。

## 第四步： ##

当一个链表中元素较多时，通过key值依次查找效率较低，而JDK1.8中，哈希表存储采用数组+链表+红黑树实现。当[链表长度大于8且当前数组长度>64时][8_64]，将链表转换为红黑树这样大大减少了查找时间。

[源码解析之HashMap实现原理][HashMap]

[_key_String_hashCode_hash]: https://blog.csdn.net/weixin_43811057/article/details/110287480
[Link 1]: https://blog.csdn.net/weixin_43811057/article/details/110285768
[12_2]: https://blog.csdn.net/weixin_43811057/article/details/110287165
[8_64]: https://blog.csdn.net/weixin_43811057/article/details/110286219
[HashMap]: https://blog.csdn.net/pihailailou/article/details/82053420?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~Rate-1-82053420-blog-110282168.pc_relevant_landingrelevant&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~Rate-1-82053420-blog-110282168.pc_relevant_landingrelevant&utm_relevant_index=1