【集合】JDK1.8 HashMap 底层数据结构深度解析

一、核心数据结构：为什么是 "数组 + 链表 + 红黑树"？

HashMap 的底层设计本质是用空间换时间，通过哈希表的快速定位特性，结合链表和红黑树处理冲突，平衡查询与插入效率。

1.1 基础容器：哈希桶数组（Node [] table）

数组角色：作为哈希表的 "骨架"，每个下标对应一个哈希桶（bucket），通过哈希值直接定位元素所在桶的位置，实现 O (1) 级别的快速访问。

Node 节点结构：数组中存储的是Node<K,V>对象，包含四个核心字段：

static class Node<K,V> implements Map.Entry<K,V> {final int hash;    // 键的哈希值（经过扰动处理）final K key;       // 键（唯一）V value;           // 值Node<K,V> 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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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的节点，替换valueif (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<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// 计算新容量和新阈值（省略细节）if (oldCap > 0) {newCap = oldCap << 1; // 容量翻倍newThr = oldThr << 1; // 阈值翻倍} else if (oldThr > 0) {newCap = oldThr;} else {newCap = 16; // 默认初始容量newThr = 12; // 默认初始阈值（16*0.75）}// 创建新数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 迁移旧元素到新数组（省略链表和红黑树的迁移细节）if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;// 单节点直接迁移if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 链表和红黑树的迁移逻辑（见上文）// ...}}}return newTab;
}