HashMap原理

蔚落 2023-09-25 19:35 113阅读 0赞

### HashMap原理 ###

*  单线程下的HashMap
 *  HashMap中的字段
 *  存储结构
 *  Node节点
 *  插入数据
 *  确定Node的存储位置
 *   *  例子1：添加Key键为字符‘e’
     *  例子2：存放键key分别为'a','b','d','r','t','e','a','g','i'对象
     *  例子3

# 单线程下的HashMap #

HashMap类主要用来处理具有键值对特征的数据。随着JDK版本的更新，JDK1.8对HashMap底层也进行了优化。

![在这里插入图片描述][8f11d2eb62ce4c13a76dc0eac1f1dc3b.png]  
HashMap是基于哈希表对Map接口的实现，HashMap具有较快的访问速度，但是遍历顺序却是不确定的。

new HashMap<>().put(null, null)

HashMap提供所有可选的映射操作，并允许使用null值和null键。

HashMap并非线程安全，当存在多个线程同时写入HashMap时，可能会导致数据的不一致。

# HashMap中的字段 #

![在这里插入图片描述][7c6127182eab4246aff193159d90328a.png]  
loadFactor称为负载因子，默认值为0.75。threshold表示所能容纳的键值对的临界值。

**threshold = 数组长度 \* 负载因子**

size是HashMap中实际存在的键值对数量。modCount字段用来记录HashMap内部结构发生变化的次数。HashMap的默认容量INITIAL\_CAPACITY为16。

# 存储结构 #

HashMap采用了数组+链表+红黑树（jdk1.8）的存储结构。  
![在这里插入图片描述][9222565633de4c21af61c322c2b161f0.png]  
HashMap数组部分称为**哈希桶**。当链表长度大于等于8时，链表数据将从红黑树的形式进行存储。当长度降到6时，转成链表。

1.  链表的时间复杂度为O(n)
2.  红黑树的时间复杂度O(logn)

# Node节点 #

![在这里插入图片描述][8cadbe0e4c044bac8a49304b1a85530f.png]  
每个Node节点存储着用来定位数据索引位置的hash值，k键，v值以及指向链表下一个节点的Node<K,V>next节点组成。

Node是HashMap的内部类，实现了Map.Entry接口，本质是一个键值对。

# 插入数据 #

当向HashMap中插入数据时，首先要确定在哈希数组中的位置。

# 确定Node的存储位置 #

![在这里插入图片描述][e4db0676597443e8bf7af9fe9cf3c4cb.png]![在这里插入图片描述][32cc218804494c6eaa1954f2f4b86d47.png]

## 例子1：添加Key键为字符‘e’ ##

HashMap首先调用hashCode()方法，获取键key的hashCode值h（101），然后对其进行高位运算：  
将h右移16位以取得h的高16位，与原h的低16位进行异或运算（结果为101）。  
最后将得到的h值与（table.length-1）进行与运算获得该对象的保留位以计算下标。

## 例子2：存放键key分别为’a’,‘b’,‘d’,‘r’,‘t’,‘e’,‘a’,‘g’,'i’对象 ##

通过计算知‘a’的下标为1(0001), 'b’为2(0010), 'd’为4（0100），’r’为2（0010），‘t’为4（0100），’e’为5（0101）

![在这里插入图片描述][946ec41a4d82446ea4c7e0b2c155e8af.png]

当插入第二个以‘a’为key的对象时，将新值赋值给’a’的值。

当插入的对象大小超过临界值时，HashMap将新建一个桶数组并重新赋值（jdk1.7和jdk1.8重新赋值方式略有不同）。

## 例子3 ##

![在这里插入图片描述][af11ea74f7084355bb6051b84b7ee790.png]  
参考资料：[3分钟轻松理解HashMap原理 面试不再下饭][3_HashMap_]

[8f11d2eb62ce4c13a76dc0eac1f1dc3b.png]: https://img-blog.csdnimg.cn/8f11d2eb62ce4c13a76dc0eac1f1dc3b.png
[7c6127182eab4246aff193159d90328a.png]: https://img-blog.csdnimg.cn/7c6127182eab4246aff193159d90328a.png
[9222565633de4c21af61c322c2b161f0.png]: https://img-blog.csdnimg.cn/9222565633de4c21af61c322c2b161f0.png
[8cadbe0e4c044bac8a49304b1a85530f.png]: https://img-blog.csdnimg.cn/8cadbe0e4c044bac8a49304b1a85530f.png
[e4db0676597443e8bf7af9fe9cf3c4cb.png]: https://img-blog.csdnimg.cn/e4db0676597443e8bf7af9fe9cf3c4cb.png
[32cc218804494c6eaa1954f2f4b86d47.png]: https://img-blog.csdnimg.cn/32cc218804494c6eaa1954f2f4b86d47.png
[946ec41a4d82446ea4c7e0b2c155e8af.png]: https://img-blog.csdnimg.cn/946ec41a4d82446ea4c7e0b2c155e8af.png
[af11ea74f7084355bb6051b84b7ee790.png]: https://img-blog.csdnimg.cn/af11ea74f7084355bb6051b84b7ee790.png
[3_HashMap_]: https://www.bilibili.com/video/BV1oE411n7ug/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb