Java-HashMap底层原理和扩容机制详解_Java

一句话总结

hashmap底层采用数组+链表/红黑树结构，通过哈希算法确定元素存储位置。默认初始容量16，负载因子0.75，当元素数量超过（容量×负载因子）时触发扩容。

扩容时创建双倍容量新数组，通过高位运算重新计算节点位置（jdk8优化为无需重新hash），原数据通过尾插法迁移到新数组。

链表长度超过8且数组长度≥64时会转为红黑树，提升查询效率。

详细解析

一、底层数据结构：数组 + 链表（jdk7） → 数组 + 链表/红黑树（jdk8）

hashmap 的底层是一个 哈希表（hash table），本质是一个动态扩容的数组（称为table），数组的每个元素是一个链表（或 红黑树，jdk8 及以后），用于存储哈希冲突的键值对。

核心结构术语

桶（bucket）：数组的每个槽位（table[i]）称为一个桶，用于存放哈希值相同的键值对。
哈希冲突（hash collision）：不同键通过哈希函数计算出相同的桶下标，导致多个键值对需要存放在同一个桶中。
链表（entry 或 node 节点）：jdk7 中桶内元素以链表形式存储（节点类型为entry<k,v>）；jdk8 中改为node<k,v>，当链表长度超过阈值时转换为红黑树。
红黑树（treenode）：jdk8 引入，当链表长度 ≥8 且数组长度 ≥64 时，链表转换为红黑树（节点类型为treenode<k,v>），以将查找时间复杂度从 o(n) 优化到 o(logn)。

二、核心机制：哈希计算、冲突解决、扩容

哈希计算与桶定位

hashmap 通过以下步骤确定键值对的存储位置：

步骤 1：计算键的哈希值

键的哈希值通过key.hashcode()方法获取，但 hashmap 会对其进行二次哈希（hash()方法），目的是 减少哈希冲突。

jdk7 的hash()方法通过多次位运算（如异或、右移）扩散哈希值；

jdk8 简化为：(h = key.hashcode()) ^ (h >>> 16)（高 16 位与低 16 位异或），让高位参与低位计算，减少低位冲突。

步骤 2：确定桶下标

桶下标通过(n - 1) & hash计算（n是数组长度，必须是 2 的幂次）。该计算等价于hash % n，但位运算更高效。数组长度为 2 的幂次是为了保证(n-1) & hash的结果均匀分布。

若n非 2 的幂次，&运算会导致某些桶永远无法被访问。

比如n=10，那么n-1=9，二进制为1001。(n-1) & hash 等价于取 hash 的二进制与 1001 的按位与，结果的二进制只能是以下四种可能（因为 1001 只有第 0 位和第 3 位是 1）：0000（0）、0001（1）、1000（8）、1001（9）。因此，无论 hash 是什么值，最终的桶下标只能是 0、1、8、9 这四个值。

哈希冲突解决：链地址法

当不同键的哈希值映射到同一个桶时，hashmap 使用 链地址法 解决冲突：将冲突的键值对以链表形式挂在同一个桶下。

jdk8 之前链表的插入方式是 头插法（新节点插入链表头部），jdk8 改为 尾插法（新节点插入链表尾部），避免扩容时的死循环问题（下文详述）。

扩容机制：动态调整数组大小

hashmap 通过 扩容（resize） 保持负载因子（load factor）在合理范围，避免哈希冲突过多导致性能下降。

触发条件：

当元素数量（size）超过容量（capacity） × 负载因子（loadfactor）时触发扩容。
默认容量为 16，负载因子为 0.75（空间与时间的权衡：负载因子过小会导致频繁扩容；过大则哈希冲突概率增加）。

扩容过程：

jdk8 扩容优化：

由于数组长度是 2 的幂次，旧数组的桶下标为i，新数组长度为2×oldcap，新桶下标只能是i或i + oldcap（通过hash & oldcap是否为 0 判断）。因此，无需重新计算哈希值，只需判断hash的最高位（相对于旧容量的位置）是否为 0，即可确定新位置，大幅提升扩容效率，可以看下图容量从16扩充为32的resize示意图加深理解。

创建新数组：容量翻倍（newcap = oldcap << 1），新数组长度仍为 2 的幂次。
迁移元素：将旧数组中的所有键值对重新分配到新数组的桶中（jdk7 需重新计算哈希值，jdk8 优化为通过hash & oldcap判断是否需要移动）。

三、jdk7 与 jdk8 的核心差异

特性	jdk7 实现	jdk8 实现
底层结构	数组 + 链表（entry 节点）	数组 + 链表/红黑树（node/treenode 节点）
冲突解决	链表（长度无限制，查找 o(n)）	链表长度 ≥8 且数组长度 ≥64 时转为红黑树（查找 o(logn)）
插入方式	头插法（新节点插入链表头部）	尾插法（新节点插入链表尾部）
扩容时哈希计算	重新计算哈希值（hash()方法）	通过hash & oldcap判断是否需要移动（无需重新计算哈希）
死循环问题	多线程扩容时可能导致链表成环（死循环）	尾插法避免了死循环，但仍存在数据覆盖问题（线程不安全本质未变）

四、线程不安全的原因

hashmap 是 线程不安全 的，多线程环境下可能导致以下问题：

数据覆盖（最常见）：多个线程同时执行put操作时，若哈希冲突导致两个线程同时修改同一个桶的链表，可能出现后写入的数据覆盖先写入的数据。
扩容死循环（jdk7）：jdk7 采用头插法扩容，多线程迁移元素时可能导致链表成环（如线程 a 和 b 同时迁移同一链表，指针互相引用），后续查询时陷入死循环。
数据丢失：多线程扩容时，可能丢失部分键值对（如两个线程同时计算出相同的新桶位置，导致其中一个线程的数据被覆盖）。