HashMap 内部结构：扰动、扩容与树化

扰动函数：把高位带下来01

下标只用 hash 的低位（n-1 的位数）。如果 hashCode 的高位有信息、低位全 0，直接取模会全部撞到同一个桶；JDK 8 用 (h = key.hashCode()) ^ (h >>> 16) 把高 16 位异或到低 16 位。

int h = 0x00010000;
System.out.println((16 - 1) & h);
System.out.println((16 - 1) & (h ^ (h >>> 16)));

0
1

扰动不是「消除碰撞」，只是让高位参与索引；两个不同 key 仍然可能得到同一个下标。它也不能替代一个好的 hashCode。

扩容：翻倍与高低位拆分02

当元素数超过 threshold = capacity * loadFactor 时，容量翻倍，阈值也跟着翻倍。JDK 8 把每个旧桶拆成 lo/hi 两条链：(e.hash & oldCap) == 0 留在原下标，否则移到 原下标 + oldCap。

拆分保持链表相对顺序（头插改尾插），避免了 JDK 7 并发扩容时的环形链表；但这不是线程安全保证。

HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 1; i <= 12; i++) map.put(i, i);
System.out.println(map.size()); // 12，仍未扩容
map.put(13, 13);
// table 从 16 扩到 32

树化：极端碰撞的兜底03

当某个桶的链表节点数超过阈值，treeifyBin 会把链表转成红黑树。JDK 8 的实际判断是插入后 binCount >= TREEIFY_THRESHOLD - 1：桶内已有 8 个节点、再插入第 9 个时才触发。

如果此时 table 容量小于 64，treeifyBin 不树化，而是先扩容；因为小表扩容比树化更划算。树化后查找 O(log n)，但节点更大、维护成本更高。

删除导致树变小时，removeTreeNode 会按树结构退化为链表；扩容拆分时，如果树桶拆分后的节点数不超过 6，也会退回链表。

用反射观察 table 与树化01

下面这段代码在 JDK 8 上直接读 table 字段，观察桶的节点类型和容量变化。它只用于教学，生产代码不要依赖 HashMap 的内部结构。

import java.lang.reflect.Field;
import java.util.HashMap;

public class HashMapProbe {
    static final class Key {
        final int h;
        final String name;
        Key(int h, String name) { this.h = h; this.name = name; }
        public int hashCode() { return h; }
        public boolean equals(Object o) {
            return o instanceof Key && ((Key) o).h == h
                    && ((Key) o).name.equals(name);
        }
    }

    static Object[] table(HashMap<?, ?> map) throws Exception {
        Field f = HashMap.class.getDeclaredField("table");
        f.setAccessible(true);
        return (Object[]) f.get(map);
    }

    public static void main(String[] args) throws Exception {
        HashMap<Key, String> map = new HashMap<>(64);
        for (int i = 1; i <= 8; i++) {
            map.put(new Key(1, "k" + i), "v" + i);
        }
        System.out.println("size=8 type="
                + table(map)[1].getClass().getSimpleName());

        map.put(new Key(1, "k9"), "v9");
        System.out.println("size=9 type="
                + table(map)[1].getClass().getSimpleName());

        HashMap<Integer, Integer> grow = new HashMap<>();
        for (int i = 1; i <= 12; i++) grow.put(i, i);
        System.out.println("n=12 cap=" + table(grow).length);

        grow.put(13, 13);
        System.out.println("n=13 cap=" + table(grow).length);
    }
}

size=8 type=Node
size=9 type=TreeNode
n=12 cap=16
n=13 cap=32

输出验证了两点：8 个碰撞节点仍是 Node，第 9 个才变 TreeNode；默认容量在第 13 个元素时从 16 扩到 32。

并发：JDK 8 没有死循环，但仍会丢数据02

JDK 7 的扩容用头插法，两个线程同时 resize 可能把链表接成环，导致 get 死循环。JDK 8 改成尾插并保留 lo/hi 顺序，环的问题基本消失，但并发 put 仍可能丢更新、读到旧值、size 不一致。

• modCount 的 fail-fast 只是尽力检测，不保证并发下一定抛 ConcurrentModificationException。
• 复合操作（先 get 再 put）不是原子的；computeIfAbsent 才是原子操作。
• 并发场景用 ConcurrentHashMap；JDK 8 用 CAS + synchronized 锁桶，不再用 Segment 分段锁。
• Collections.synchronizedMap 只同步单个方法，复合操作仍需外部加锁。

容量、key 与碰撞攻击03

• 预设容量按 expected / 0.75 + 1 估算，减少扩容；不要设得过大，浪费数组。
• key 用不可变对象；equals 与 hashCode 用同一组字段。
• hashCode 要均匀；常量 hashCode 会让所有 key 挤进一个桶，退化成链表/树。
• 树化能防御哈希碰撞攻击，但不能防御糟糕的 key 设计；攻击者仍可用大量碰撞消耗 CPU。
• 负载因子调低会增加空间、减少碰撞；调高会省空间、增加查找成本。

先猜再看01

能否讲清因果02