HashMap 的底层实现原理是怎样的？（基于JDK 8）-java教程-PHP中文网

HashMap 的底层实现原理是怎样的？（基于JDK 8）

betcha

发布： 2025-09-03 23:31:02

原创

160人浏览过

答案：JDK 8中HashMap采用“数组+链表/红黑树”结构，通过扰动哈希值并按位与确定索引，冲突时链表存储，链表长度≥8且容量≥64时转为红黑树；扩容时容量翻倍并再哈希，多线程不安全，推荐使用ConcurrentHashMap。

hashmap 的底层实现原理是怎样的？（基于jdk 8）

HashMap在JDK 8中的底层实现，核心是“数组+链表/红黑树”的混合结构。它通过哈希函数将键映射到数组索引，处理哈希冲突时，先用链表串联，当链表长度达到一定阈值后，会自动转换为红黑树以优化查找性能。

深入探讨HashMap的底层，我们得从它的骨架——一个

Node[] table

登录后复制

说起。这本质上就是一个数组，每个数组元素，我们称之为“桶”（bucket），可以存放一个

Node

登录后复制

对象。这个

Node

登录后复制

，其实就是

Entry

登录后复制

的升级版，它存储着键值对（key-value pair）、哈希值以及指向下一个Node的引用（

next

登录后复制

），这正是链表结构的基础。

当你调用

put(key, value)

登录后复制

时，HashMap首先会计算

key

登录后复制

的哈希值。这个哈希值的计算并非简单地直接使用

key.hashCode()

登录后复制

，而是经过一番位运算的“扰动处理”，目的是让哈希值的高位也能参与到最终的索引计算中，从而减少哈希冲突。具体来说，它会把

key.hashCode()

登录后复制

与

key.hashCode() >>> 16

登录后复制

进行异或操作，这在一定程度上打散了哈希值，让它们分布得更均匀。

得到扰动后的哈希值后，HashMap会用这个哈希值与

table.length - 1

登录后复制

进行按位与操作，得到最终的数组索引。这相当于取模运算，但位运算效率更高。

如果计算出的索引位置是空的，那很简单，直接创建一个新的

Node

登录后复制

并放进去。但如果这个位置已经有Node了，也就是发生了哈希冲突，事情就变得有趣了。

在JDK 8之前，这里通常就是简单的链表追加。但在JDK 8中，为了应对极端情况下的链表过长（导致查找效率退化到O(n)），引入了红黑树。当某个桶位的链表长度达到

TREEIFY_THRESHOLD

登录后复制

（默认是8）时，并且

HashMap

登录后复制

的容量

table.length

登录后复制

也达到了

MIN_TREEIFY_CAPACITY

登录后复制

（默认是64），这个链表就会被“树化”成红黑树。红黑树的查找、插入、删除操作的平均时间复杂度都是O(log n)，这大大提升了性能。如果

HashMap

登录后复制

容量不足64，即使链表长度达到8，也不会直接树化，而是会先进行扩容（resize），因为扩容可能让元素重新分布，从而缓解冲突。

get(key)

登录后复制

的逻辑也类似，先计算

key

登录后复制

的哈希值和索引，然后去对应的桶位查找。如果桶位是链表，就遍历链表，通过

equals()

登录后复制

方法找到匹配的键；如果是红黑树，就按照红黑树的查找逻辑来。

HashMap为什么选择“数组+链表/红黑树”的混合结构？

这其实是一个经典的性能与空间平衡问题。单纯的数组查找效率高（O(1)），但一旦哈希冲突，处理起来就麻烦；单纯的链表插入删除快，但查找效率低（O(n)）。HashMap巧妙地结合了两者：数组提供快速的索引定位，链表/红黑树处理冲突。

早期版本用链表，简单直接，但在哈希函数设计不佳或数据分布极端时，链表可能变得非常长，导致性能急剧下降。这就像你把所有文件都扔进一个文件夹，找起来自然慢。JDK 8引入红黑树，正是为了解决这个痛点。当冲突严重到一定程度，自动升级为红黑树，将查找复杂度从O(n)优化到O(log n)，这是个非常聪明的权衡。它不是一开始就用红黑树，因为红黑树的节点比链表节点占用更多内存，且维护成本更高。只有在必要时才进行“树化”，这体现了其设计上的精妙与实用主义。

HashMap的扩容机制是如何工作的？

HashMap的容量不是一成不变的。当

HashMap

登录后复制

中的元素数量（

size

登录后复制

）超过了容量（

capacity

登录后复制

）与负载因子（

loadFactor

登录后复制

）的乘积，也就是

threshold

登录后复制

时，

HashMap

登录后复制

就会进行扩容操作。默认的负载因子是0.75，这意味着当

HashMap

登录后复制

填满其75%的容量时，它就会扩容。

扩容通常会使底层数组的容量翻倍。例如，如果当前容量是16，扩容后就变成32。扩容不仅仅是简单地增加数组大小，更重要的是要进行“再哈希”（rehash）。这意味着所有旧数组中的元素都需要重新计算它们在新数组中的位置，因为数组长度变了，

hash & (newCapacity - 1)

登录后复制

的结果也会改变。

硅基智能

基于Web3.0的元宇宙，去中心化的互联网，高质量、沉浸式元宇宙直播平台，用数字化重新定义直播

查看详情

这个过程是比较耗时的，因为它涉及到遍历所有已存在的Node，并重新分配到新的数组中。如果链表被树化了，在扩容时，红黑树也会被拆分或重新构建。JDK 8在扩容时对链表元素的重新定位做了优化：对于旧桶中的每个节点，如果其哈希值与旧容量进行与操作的结果为0，它就留在原位；如果结果不为0，它就会被移动到

原索引 + 旧容量

登录后复制

的位置。这样，一个旧桶中的链表（或红黑树）会被拆分成两个新桶中的链表（或红黑树），避免了重新计算每个元素的完整哈希值和索引，提高了效率。

扩容是保证HashMap性能的关键。它确保了桶的平均长度不会过长，从而维持了O(1)（平均）的查找和插入性能。但频繁的扩容也会带来性能开销，所以初始容量的选择有时也需要考量。

HashMap在多线程环境下为什么不安全，以及有哪些替代方案？

HashMap在多线程环境下是不安全的，这是一个非常重要的点，也是新手常犯的错误。它的不安全体现在几个方面：

数据丢失或覆盖： 在
```
put
```
登录后复制
操作时，如果两个线程同时尝试在同一个桶位插入元素，可能会导致其中一个线程的更新被另一个线程覆盖，或者链表结构被破坏。
死循环（JDK 7及之前）： 在JDK 7及之前的版本中，扩容时，由于链表头插法和多线程并发操作，可能会形成环形链表，导致
```
get
```
登录后复制
操作时陷入死循环，CPU占用100%。JDK 8通过改用尾插法和更精细的扩容逻辑，虽然避免了死循环，但仍然无法保证数据一致性。
脏读： 一个线程在读取
```
HashMap
```
登录后复制
时，另一个线程可能正在修改它，导致读取到不一致的数据状态。

简单来说，

HashMap

登录后复制

的内部状态在并发修改时无法得到正确维护，因为它没有进行任何同步控制。

那么，在多线程环境下，我们应该使用什么呢？

```
Collections.synchronizedMap(Map<K, V> m)
```
登录后复制
：这是最简单粗暴的方法，它会返回一个线程安全的
```
Map
```
登录后复制
视图。它通过对所有方法进行
```
synchronized
```
登录后复制
同步，确保了原子性。但缺点是，它是一个全局锁，所有操作都必须等待，并发性能非常差。在高并发场景下，这几乎不可用。
```
ConcurrentHashMap
```
登录后复制
：这是Java并发包
```
java.util.concurrent
```
登录后复制
下提供的、专门为高并发场景设计的哈希表。它是
```
HashMap
```
登录后复制
的线程安全版本，但其实现远比
```
synchronizedMap
```
登录后复制
复杂和高效。
```
ConcurrentHashMap
```
登录后复制
在JDK 7中采用了
```
Segment
```
登录后复制
分段锁的机制，将整个
```
HashMap
```
登录后复制
分成多个小的
```
Segment
```
登录后复制
，每个
```
Segment
```
登录后复制
独立加锁，从而允许多个线程同时访问不同的
```
Segment
```
登录后复制
，大大提高了并发度。

而在JDK 8中，
```
ConcurrentHashMap
```
登录后复制
进一步优化，放弃了
```
Segment
```
登录后复制
，转而采用了“
```
CAS + synchronized
```
登录后复制
”的策略。它在
```
put
```
登录后复制
操作时，先通过
```
CAS
```
登录后复制
（Compare-And-Swap）尝试更新，如果失败（说明有并发），则使用
```
synchronized
```
登录后复制
锁住当前桶的头节点（或红黑树的根节点）。这样，锁的粒度更细，只锁定发生冲突的桶，而不是整个
```
Map
```
登录后复制
或一个大的
```
Segment
```
登录后复制
，从而实现了更高的并发性能。同时，它也引入了红黑树来处理链表过长的问题，与
```
HashMap
```
登录后复制
的设计思想保持一致。