【集合】JDK1.8 HashMap 底层数据结构深度解析
一、核心数据结构：为什么是 \"数组 + 链表 + 红黑树\"？
HashMap 的底层设计本质是用空间换时间，通过哈希表的快速定位特性，结合链表和红黑树处理冲突，平衡查询与插入效率。
1.1 基础容器：哈希桶数组（Node [] table）
- 数组角色：作为哈希表的 \"骨架\"，每个下标对应一个哈希桶（bucket），通过哈希值直接定位元素所在桶的位置，实现 O (1) 级别的快速访问。
- Node 节点结构：数组中存储的是Node对象，包含四个核心字段：
static class Node implements Map.Entry { final int hash; // 键的哈希值（经过扰动处理） final K key; // 键（唯一） V value; // 值 Node next; // 下一个节点引用（用于链表）}
这里的next字段是实现链表的关键，当多个元素哈希冲突时，会通过该字段串成链表。
1.2 解决冲突：链表的作用
当两个不同的 key 计算出相同的哈希值（即哈希冲突）时，HashMap 会将新元素以链表节点的形式 \"挂\" 在同一哈希桶的尾部。这种处理方式称为链地址法，是哈希表解决冲突的经典方案。
1.3 性能优化：红黑树的引入
JDK1.8 之前，HashMap 仅用数组 + 链表的结构，当哈希冲突严重时（如大量元素集中在同一桶中），链表会退化为 \"长链\"，此时查询时间复杂度会从 O (1) 退化到 O (n)。
为解决这个问题，JDK1.8 引入了红黑树（TreeNode）：当链表长度超过阈值（默认 8）且数组长度≥64 时，链表会自动转为红黑树，将查询时间复杂度优化到 O (log n)。
二、关键机制解析：哈希、扩容与树化
2.1 哈希函数：如何计算元素在数组中的位置？
HashMap 的高效查询依赖于哈希值的精准计算，核心步骤分为两步：
① 计算 key 的哈希值（扰动函数）
static final int hash(Object key) { int h; // 1. 取key的hashCode值；2. 高16位与低16位异或（扰动处理） return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}- 为什么要做扰动处理？
若直接使用key.hashCode()的低几位计算索引，当哈希值的高位变化大但低位变化小时，容易导致哈希冲突（例如hashCode=0x0001FFFF和0x0002FFFF，低 16 位相同）。通过高 16 位与低 16 位异或，能让高位信息参与哈希计算，减少冲突概率。
② 计算数组索引
// n为数组长度（必须是2的幂）int index = (n - 1) & hash;- 这里用(n-1) & hash代替取模运算（hash % n），因为当 n 是 2 的幂时，两者结果等价，但位运算效率更高。
2.2 扩容机制：数组不够用了怎么办？
当 HashMap 中的元素数量超过阈值（threshold = 容量 × 负载因子）时，会触发扩容（resize），将数组长度翻倍（新容量 = 旧容量 ×2）。
扩容的核心步骤：
（1）计算新容量与新阈值：默认初始容量为 16，负载因子 0.75，初始阈值 = 16×0.75=12。扩容后新容量 = 32，新阈值 = 32×0.75=24。
（2）创建新数组：长度为新容量。
（3）迁移旧元素：将旧数组中的元素重新计算索引，迁移到新数组中（JDK1.8 优化点：通过hash & oldCap判断元素是否需要移动，避免重复计算哈希）。
扩容时的元素迁移逻辑：
- 若元素所在桶是单节点：直接计算新索引并放入新数组。
- 若元素所在桶是链表：
通过hash & oldCap将链表拆分为两个子链表：
- 结果为 0：元素留在原索引位置（新数组的j处）。
- 结果为非 0：元素迁移到新索引位置（新数组的j + oldCap处）。
- 若元素所在桶是红黑树：拆分树节点为两个子树，若子树长度≤6 则退化为链表。
2.3 树化与反树化：链表和红黑树如何转换？
树化（链表转红黑树）的触发条件：
- 链表长度≥8（TREEIFY_THRESHOLD = 8）。
- 数组长度≥64（MIN_TREEIFY_CAPACITY = 64）。
若数组长度不足 64，会先触发扩容而非树化，避免在小容量数组上过度树化浪费资源。
反树化（红黑树转链表）的触发条件：
当红黑树的节点数量≤6（UNTREEIFY_THRESHOLD = 6）时，会自动退化为链表，减少树结构带来的维护成本。
为什么阈值是 8 和 6？
- 官方注释提到，根据泊松分布，链表长度达到 8 的概率仅为 0.00000006（几乎是小概率事件），此时树化收益大于成本。
- 用 6 作为反树化阈值，是为了避免链表在 8 附近频繁树化 / 反树化（ hysteresis 机制）。
三、源码直击：put () 与 resize () 核心逻辑
3.1 put () 方法：元素插入全流程
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 步骤1：数组为空则初始化（第一次put时触发） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步骤2：计算索引，若桶为空则直接插入新节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 步骤3：若桶中首个节点的key与插入key相同，直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步骤4：若桶中是红黑树，则调用树插入方法 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 步骤5：若桶中是链表，遍历链表寻找插入位置 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表长度≥8，触发树化 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 找到相同key的节点，跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 步骤6：若存在相同key的节点，替换value if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 步骤7：元素数量超过阈值，触发扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}3.2 resize () 方法：扩容核心逻辑
final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 计算新容量和新阈值（省略细节） if (oldCap > 0) { newCap = oldCap << 1; // 容量翻倍 newThr = oldThr < 0) { newCap = oldThr; } else { newCap = 16; // 默认初始容量 newThr = 12; // 默认初始阈值（16*0.75） } // 创建新数组 Node[] newTab = (Node[])new Node[newCap]; table = newTab; // 迁移旧元素到新数组（省略链表和红黑树的迁移细节） if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 单节点直接迁移 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 链表和红黑树的迁移逻辑（见上文） // ... } } } return newTab;}四、高频面试题：HashMap 的那些 \"为什么\"
4.1 为什么 HashMap 的容量必须是 2 的幂？
- 确保(n-1) & hash等价于hash % n，用高效的位运算替代取模。
- 扩容时可通过hash & oldCap快速判断元素是否需要迁移（结果为 0 则留在原位置，否则迁移到j+oldCap）。
4.2 为什么选择红黑树而非 AVL 树？
- 红黑树：插入和删除时最多需要 2 次旋转，调整成本低，适合频繁插入删除的场景。
- AVL 树：是严格平衡树，查询效率更高，但插入删除可能需要多次旋转，调整成本高。
HashMap 更注重整体的插入删除效率，因此选择红黑树。
4.3 HashMap 为什么线程不安全？如何解决？
- 线程不安全表现：多线程并发扩容时，JDK1.7 中可能出现链表环（导致死循环）；JDK1.8 中虽解决了环问题，但仍可能出现数据覆盖。
- 线程安全方案：
- 使用ConcurrentHashMap（JDK1.7 分段锁，JDK1.8 CAS+ synchronized）。
- 通过Collections.synchronizedMap(new HashMap())包装（性能较差，不推荐）。
4.4 负载因子为什么默认是 0.75？
- 负载因子过小（如 0.5）：哈希冲突少，但数组扩容频繁，浪费空间。
- 负载因子过大（如 1.0）：空间利用率高，但哈希冲突概率剧增，查询效率下降。
0.75 是时间与空间成本的平衡点，由泊松分布计算得出，此时哈希冲突概率较低。
五、总结
JDK1.8 的 HashMap 通过数组 + 链表 + 红黑树的复合结构，结合哈希函数的扰动优化、高效扩容机制和树化策略，实现了 \"查询快、插入快、冲突少\" 的核心目标。其设计细节（如 2 的幂容量、0.75 负载因子、8/6 树化阈值）处处体现了 \"平衡取舍\" 的设计思想。
理解这些底层原理，不仅能帮助我们在开发中规避 HashMap 的使用陷阱（如 key 未重写 hashCode/equals 导致的内存泄漏），更能在面试中脱颖而出。建议结合源码调试，观察哈希冲突、扩容、树化的实际过程，加深理解。
