HashMap 源码相关问题¶

1. 底层数据结构¶

JDK8：数组（table）+ 链表 + 红黑树。

table[0] -> Node -> Node -> ...
table[1] -> TreeNode (红黑树)
table[2] -> null

2. 关键常量¶

常量	值	含义
`DEFAULT_INITIAL_CAPACITY`	16	默认容量
`MAXIMUM_CAPACITY`	1 << 30	最大容量
`DEFAULT_LOAD_FACTOR`	0.75	负载因子
`TREEIFY_THRESHOLD`	8	链表转树阈值
`UNTREEIFY_THRESHOLD`	6	树退化为链表阈值
`MIN_TREEIFY_CAPACITY`	64	树化要求的最小数组长度

3. put 流程¶

对 key 做扰动哈希：(h = key.hashCode()) ^ (h >>> 16)。
计算下标 i = (n - 1) & hash。
桶为空，直接 new Node 放入。
桶非空：
头节点 key 相同，覆盖 value。
是 TreeNode，走红黑树插入。
是链表，遍历尾插；长度 ≥ 8 且数组长度 ≥ 64 时树化。
++size > threshold 时扩容。

4. 为什么用尾插法（JDK8）？¶

JDK7 用头插法，多线程扩容时可能把链表成环，导致 CPU 100%。JDK8 改为尾插法，但仍非线程安全，只是解决了成环问题。

5. 扩容机制¶

容量翻倍：newCap = oldCap << 1。
因为容量是 2 的幂，扩容后元素的新位置只有两种可能：
原位置：哈希与旧容量的位为 0。
原位置 + oldCap：该位为 1。
因此不需要重新计算 hash，只需看 hash & oldCap，效率高。

6. 为什么容量必须是 2 的幂？¶

为了用 (n - 1) & hash 替代 hash % n。如果 n 是 2 的幂，(n-1) 二进制全是 1，按位与的结果等价于取模且更快。

构造时传入非 2 的幂容量，HashMap 会向上取最近的 2 的幂：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return n + 1;
}

7. 为什么链表长度到 8 才树化？¶

泊松分布：负载因子 0.75 时，桶内节点数达到 8 的概率约千万分之 6。8 是性能与空间的折中——链表查找 O(n)，树化后 O(log n)，但树节点比链表节点占用更多内存。

8. 为什么负载因子是 0.75？¶

时间与空间的权衡：过大（如 1.0）空间利用率高但碰撞多；过小（如 0.5）碰撞少但浪费空间。0.75 配合泊松分布，哈希分布最均匀。

高频追问

JDK7 头插法死循环：多线程扩容时，节点的 next 指针被反向链接。
为什么 String 的 hashCode 用 s[0]*31^(n-1) + ...？31 是奇素数，31 * i == (i << 5) - i，JVM 可优化。