HashMap in Java

为什么写这篇

在 关于我在技术的这一面 那篇里我提过，如果有人问我「Java 的 HashMap 在 1.7 和 1.8 里，数据结构有哪些变化」，我大概率得翻开笔记才能答顺。

这并不丢人——HashMap 天天用，真问到桶、扰动函数、头插法扩容成环、树化阈值这些细节，脑子一瞬间宕机也正常。但正因为它是面试关键词链里很靠前的一环：

HashMap → 红黑树 → ConcurrentModificationException →
synchronized → AQS → CAS → ...

我觉得值得单独留一篇笔记，把我自己理解过的部分写清楚。下面重点放在 Java 7 的底层实现，再对比 Java 8 引入红黑树 之后变了什么。细节若有偏差，欢迎指正——我自己也是对着源码笔记和资料整理的，不是背教科书。

日常怎么用

业务里 HashMap 就是存键值对，查改删靠 put / get / remove，没什么神秘的：

final var map = new HashMap<String, Integer>();
map.put("张三", 20);
map.put("李四", 25);
 
map.get("张三");      // 查
map.put("张三", 30);  // 改（同 key 覆盖 value）
map.remove("张三");   // 删

缓存用户 ID → 用户信息、关键字 → 文档 ID 列表，都是同一套思路：用 key 的哈希值快速定位，尽量 O(1) 读写。

往底层看，就是一个数组，每个位置是一个桶（Bucket），桶里可能是单个节点、一条链表，Java 8 之后链表太长还可能变成红黑树——后面展开讲。

基本结构（Java 7）

Java 7 里，HashMap 底层是 Entry[] table 数组，每个数组槽位是一个桶。哈希冲突时，同一个桶里的多个元素串成 单向链表。

table[0] -> Entry1 -> Entry2 -> Entry3
table[1] -> null
table[2] -> Entry4 -> Entry5
...

Entry 节点大致长这样：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
 
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

put 的时候根据 key 算出在数组里的下标，插进对应桶；get 的时候同样算下标，去桶里找。听起来简单，魔鬼在哈希怎么算、冲突怎么解、满了怎么扩。

哈希计算与寻址

HashMap 用 key 的 hashCode() 决定落哪个桶，但不会直接拿 hashCode 当数组下标——Java 7 会再过一道 扰动函数，让高位也参与运算，分布更均匀一些：

final int hash(Object k) {
    int h = k.hashCode();
    return h ^ (h >>> 16);  // 高位扰动
}

算完 hash 之后，用位运算求模（数组长度始终是 2 的幂，所以可以用 & 替代 %）：

int hash = hash(key);
int index = (table.length - 1) & hash;

这一步面试常问，但日常写业务几乎碰不到——知道「不是直接 hashCode % length」就够了。

哈希冲突与链表

两个不同的 key 算到同一个 index，就是 哈希冲突。HashMap 用 链地址法：往这个桶的链表里塞新节点。

Entry<K,V> e = table[index];
table[index] = new Entry<>(hash, key, value, e);

Java 7 用的是 头插法——新节点插到链表头部，原来的头变成 next。插入快，但有个恶名在外的后果：多线程扩容时，头插法可能导致链表成环，CPU 100% 死循环。这是 Java 7 时代 HashMap 线程不安全最常被拿来讲的段子。

单线程开发一般遇不到；但如果你被人追问「HashMap 为什么线程不安全」，除了「没加锁」，这条扩容成环也值得提一句。

扩容（Rehashing）

元素数量超过阈值就扩容。阈值 = capacity × loadFactor，默认容量 16、负载因子 0.75，也就是 放进第 13 个元素就扩（12 是阈值，第 13 个触发）。

initialCapacity = 16
loadFactor = 0.75
// 阈值 = 12

扩容时数组容量翻倍，每个元素 重新算桶位置（Rehashing），开销不小，所以构造 HashMap 时如果能预估元素数量，给个合理的 initialCapacity 能少扩几次。

简化版扩容逻辑：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    Entry[] newTable = new Entry[newCapacity];
    for (Entry<K,V> e : oldTable) {
        while (e != null) {
            Entry<K,V> next = e.next;
            int i = e.hash & (newCapacity - 1);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
    table = newTable;
}

Java 8 改了什么：红黑树

profile 里那条面试接龙，追问完 HashMap 结构变化，下一棒往往就是红黑树。Java 8 的核心改动在这里：某个桶的链表长度超过 8，且数组容量大于 64 时，链表会树化成红黑树。

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

链表查找是 O(n)，红黑树是 O(log n)。哈希冲突严重时，性能差距能拉出来。节点也从 Entry 换成了 Node，树化后是 TreeNode：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

另外 Java 8 把链表插入改成了 尾插法，扩容逻辑也调整了，至少不会再出现 Java 7 那种「扩容成环死循环」的经典 bug。但 HashMap 依然线程不安全——多线程请用 ConcurrentHashMap，或者 Collections.synchronizedMap() 包一层，别心存侥幸。

Java 7 vs Java 8 一览

收尾

HashMap 是我用得最多的 Java 集合之一，但「天天用」和「说得清底层」确实是两回事。

我自己复习时的感受是：先把 数组 + 链表 + 扰动哈希 + 链地址法 这条主线握住，再补上 Java 8 树化 和 扩容成环 这两个面试高频点，应付大部分追问就够用了。红黑树的具体旋转、变色？那是下一棒的问题了，得另开一篇或者另翻笔记。

如果你也在准备面试，或者排查过「Map 莫名变慢」「多线程 Map 出问题」这类事，希望这篇能当一份随手翻的参考。答不上来某个细节的时候，状态不好而已——翻开笔记接上，缘分还在。