一句话总结
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 同时迁移同一链表，指针互相引用），后续查询时陷入死循环。
- 数据丢失：多线程扩容时，可能丢失部分键值对（如两个线程同时计算出相同的新桶位置，导致其中一个线程的数据被覆盖）。
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。
