HashMap底层原理#

JDK 8 的 HashMap 结构：数组 + 链表 + 红黑树

数组（Node[] table）
 index 0: null
 index 1: Node(key1, val1) → Node(key2, val2) → null  ← 链表（哈希冲突）
 index 2: TreeNode(...)                                 ← 红黑树（链表长度≥8后转换）
 index 3: null
 ...
 index n: Node(keyN, valN)

核心字段：

transient Node<K,V>[] table;    // 哈希桶数组
transient int size;             // 实际键值对数量
int threshold;                  // 扩容阈值 = capacity * loadFactor
final float loadFactor;         // 负载因子，默认 0.75
transient int modCount;         // 修改计数，fail-fast 用

哈希计算（扰动函数）：

static final int hash(Object key) {
    int h;
    // 高16位与低16位异或，目的：让高位参与散列，减少冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 确定数组下标：(capacity - 1) & hash
// 等价于 hash % capacity（因为 capacity 是2的幂）

为什么 capacity 必须是 2 的幂？ 使得 hash % capacity 可以用位运算 (capacity-1) & hash 代替，效率更高，且 capacity-1 全为 1，使 hash 低位都能参与索引计算，分布更均匀。

JDK8的HashMap底层是数组加链表加红黑树的结构。默认初始容量16，负载因子0.75，容量始终保持2的幂次方。put操作时先对key的hashCode做扰动处理，高16位与低16位异或让高位也参与散列减少冲突，然后用(capacity-1)与hash做位与运算定位桶下标，这等价于取模但效率更高，前提是容量必须是2的幂。如果桶位为空直接放入，不为空则遍历链表用equals逐个比较，key相同则覆盖value，不同则尾插到链表末尾。当链表长度达到8且数组长度大于等于64时转换为红黑树，查询复杂度从O(n)优化到O(log n)。如果数组长度不足64则优先扩容而非转树。链表长度阈值选8是基于泊松分布计算，正常负载因子下链表长度达到8的概率只有千万分之六，所以红黑树是极端情况下的保底方案。红黑树节点数降到6时会退化回链表，中间留了7的缓冲避免频繁转换。HashMap不是线程安全的，并发场景应使用ConcurrentHashMap。

追问方向：

• “为什么链表转红黑树的阈值是 8？”→ 根据泊松分布计算，正常负载因子下链表长度达到 8 的概率约为千万分之六，红黑树是极端情况的保底方案；退化阈值为 6 是留缓冲防抖动
• “HashMap 是线程安全的吗？并发下会出什么问题？”→ 不安全。JDK7 并发扩容头插法会形成环形链表导致死循环；JDK8 虽改为尾插法但仍有数据覆盖丢失和 size 不准确问题
• “为什么容量必须是 2 的幂次？”→ 使得 hash & (n-1) 等价于 hash % n 但效率更高（位运算替代取模），且 n-1 全为 1 保证 hash 低位充分参与索引计算，分布更均匀

易错点：

• ❌ “红黑树在链表长度到 8 就转换”——还需数组长度 ≥ 64，否则优先扩容
• ❌ 混淆 hashCode 和 equals 的关系——equals 相等则 hashCode 必须相等，反之不一定