请讲一讲HashMap的实现原理。

朱雀 2023-10-14 10:20 17阅读 0赞

嗯好的，我先说一下`为什么要用HashMap，它解决了什么问题？`

如果我们在一个元素顺序无序的数组中查找指定元素的话，我们需要从0下标开始依次遍历数组元素进行匹配，直到找到了目标元素，这种查找效率在最坏情况下需要将所有元素都遍历一遍，时间复杂度高达O(N)，而若数组元素有序，我们可以使用二分查找，通过比较中间值和目标值的大小来不断缩小查找范围，进而将找到目标元素所耗费的时间复杂度降低至O(log2N)，但是这还不能满足我们的需求，我们需要一个O(1)时间复杂度的算法来进行查找，这就用上了HashMap。

HashMap实现快速查找的方式是将元素和其在内存中的存储位置建立起一个映射关系，使得 存储位置 =f(key)f(key)f(key)，通过这个映射关系我们可以将查找元素的时间复杂度控制在O(1)。

HashMap的内容比较多，我主要讲三个最重要的：**存储结构 、put元素的过程** 和 **扩容机制**。

### 存储结构 ###

在JDK1.8版本中的HashMap内部是使用 `数组+链表+红黑树` 作为数据存储结构，当第一次为hashmap开辟元素存储空间时，是在内存中申请了一块地址连续的空间，也就是数组。该数组中存放的是链表的头节点或红黑树的根节点，如下图

![image-20230730185635711.png][]

在HashMap中用`Node<K，V>`来描述链表节点，用`TreeNode<K，V>`来描述树节点，TreeNode是从Node派生出来的。

在Node<K，V>内部有4个字段：

*  hash：保存key的hashCode值，HashMap通过 `hash & array.length - 1` 来计算出元素在数组中的存储位置；
 *  key：保存键的实例；
 *  value：保存键对应的值的实例；
 *  next：保存下一个节点的引用。

当第一次调用HashMap的无参构造器时，只是初始化了内部的装填因子`loadFactor`字段，并没有开辟数组空间，在第一次put元素时再去开辟，也就是懒加载机制。

当调用带`initialCapacity`参数的构造器时，也没有开辟数组空间，但是会对initialCapacity做处理，将其转换成2的次方数，在第一次put元素时，将其转换后的2次方数作为要进行开辟的数组空间大小，为什么要做转换2次方数操作，原因是为了在数组扩容过程中，其内部存储的元素进行rehash重新计算存储位置时，可以让元素要么在原来的位置上不动，要么放到扩容出来的高位上，一是减少了所有元素都进行重新定位的开销，二是让元素分配的更加均匀一点，减少冲突。

### put元素的过程 ###

1.  首次put

当首次put元素时，会先开辟数组空间，然后用key的 `hashcode & array.length - 1` 来计算出该元素要存放的位置，接着创建节点对象然后放在该位置上。

1.  第N次put

① 当第N次put元素时，也是会先计算出元素要存放的位置，如果该位置上已经存在节点，则和它进行比较一下，若key相同则用新value直接覆盖掉key原先映射的value，然后返回旧的value。

② 如果与该位置上的节点不相同，则先判断一下该节点是否为红黑树节点，若是，则在树中进行查找，看是否有Key相同的节点，若有，也是用新Value覆盖掉原Value并返回旧Value，若没有，则执行树的插入操作。

③ 若不是红黑树节点，则在链表中进行查找，也是相同的过程。但是在遍历链表的过程中，若发现没有相同的节点并在执行插入操作后，发现本条链表的节点个数大于或等于8了，且整个哈希表中元素的个数大于或等于64了，则会将该链表转换成红黑树，因为红黑树的查找时间复杂度为O(log2N)，比单链表的查找时间复杂度更低，若在之后删除节点的操作过程中使树节点的个数小于6了，则会将树再退化成单链表。

④ 在节点添加完成后若表中存放元素的个数超过了阈值threshold，就会将数组进行扩容。

### 扩容机制 ###

在扩容前会先检查一下当前表中元素的个数是否达到了最大容量，若是，则将threshold修改为Integer.MAX\_VALUE，并返回，此操作代表，不会再继续扩容了，之后存放元素就是要么往链表上加要么往树上挂。若没有超过最大容量，则将数组扩容为原来的两倍，同时也将阈值修改为原来的两倍。

扩容的实际过程就是申请一块原来数组长度两倍大小的空间，然后将节点重新rehash放到新数组中，并释放掉旧数组中的节点引用，在rehash的过程中因为新数组的大小也是2的次方数，所以元素要么在原来的位置上不动，要么放到扩容出来的高位地址上，同时还可以让元素分布的更均匀些。

在扩容的过程中，元素与元素之间的关联关系会发生改变，例如某条链表上的节点转移到了新数组位置上成了新链表的表头，或者红黑树上节点转移到了链表上，当某棵红黑树上的节点变少，小于或等于6时，就会触发树退化的操作。

值得一提的是，如果数组的长度很大，在扩容过程中消耗的时间也会随之增加，出现的场景就是，某个用户在添加节点后引发了扩容会导致其响应时间比其他的要稍长一点。

额外补充一点：HashMap不是线程安全的类，在并发场景下操作同一个HashMap会产生线程安全问题，如果想让HashMap变为线程安全的，可以在读写操作时进行加锁，或者使用`Collections.synchronizedMap()`方法得到一个线程安全的map，也是在读写操作进行加锁了，就是封装了一下。这里说的加锁是对整个表进行加锁，会极大降低并发效率，更推荐使用`ConcurrentHashMap`，它里面是运用了分段加锁机制，保障线程安全的同时，不会像直接锁整个表那样低效率，而且ConcurrentHashMap还优化了扩容机制，这里就留到之后将ConcurrentHashMap再细说吧。

[image-20230730185635711.png]: https://img-blog.csdnimg.cn/img_convert/41ebc491a0bac4c9b3cfe2f053e6e523.webp?x-oss-process=image/format,png