HashMap 大概是 Java 面试里出场率最高的类，没有之一。但很多人对它的理解 停留在“数组加链表，JDK 8 之后加了红黑树”这种背诵式的答案。这一篇我想换一种讲法—— 忘掉最终形态，从一个最朴素的哈希表开始，一步步问“为什么”，直到把 JDK 8 的 HashMap 推导出来。

从一个最朴素的哈希表说起

哈希表的核心思想极其简单：用一个数组来存数据，用 key 的哈希值决定它放在数组的第几个格子。 理想情况下，查找是 O(1) 的。于是最朴素的结构就是一个数组： 

Object[] table = new Object[16];

void put(String key, Object value) {
    int index = key.hashCode() % table.length; // 放到第 index 格
    table[index] = value;
}

Object get(String key) {
    int index = key.hashCode() % table.length;
    return table[index];
}

问题立刻就来了：两个不同的 key 完全可能算出同一个下标，这叫哈希冲突。 把后一个直接覆盖前一个显然不行。解决办法是让每个格子不再只存一个值，而是存一条链表， 冲突的元素挂到同一个桶（bucket）里。这正是 HashMap 的骨架： 

// JDK 中 Node 的真实定义，精简后
static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next; // 同一个桶里的下一个节点
}

transient Node<K, V>[] table;

哈希函数：扰动函数在做什么

如果冲突太多，链表会变长，查找退化为 O(n)。要减少冲突，首先得让哈希值尽量均匀。 HashMap 没有直接用 hashCode()，而是做了一次“扰动”： 

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

h ^ (h >>> 16) 的意思是：把哈希值的高 16 位异或到低 16 位上。 为什么要这么做？因为数组长度通常不大（比如 16），计算下标时只会用到哈希值的低位， 高位几乎没参与运算。把高位“混”进低位，能让那些高位不同、低位相同 的 key 也能尽量分散开，减少冲突。

另外注意 key == null 时返回 0，所以 HashMap 允许一个 null 作为 key， 它固定放在第 0 个桶。

下标计算：为什么容量必须是 2 的幂

我们朴素的版本用的是 hashCode % length，HashMap 却用了一个更快的写法： 

int index = (n - 1) & hash; // n 是数组长度

当 n 是 2 的幂时，n - 1 的二进制全是一串 1（比如 16-1=15，即 0000 0000 0000 0000 0000 0000 0000 1111），此时 (n - 1) & hash 等价于 hash % n，但位与运算比取模快得多。 这就是 HashMap 容量强制为 2 的幂的原因：用更廉价的位运算替代取模。

你传一个 new HashMap<>(100)，它也不会真的开 100，而是向上取最近的 2 的幂，即 128。

面试常问

“为什么 HashMap 容量要是 2 的幂？”——答案正是： 为了用 (n - 1) & hash 替代取模，既快又均匀，还让扩容时重排变得简单（见下文）。

put 的完整流程

把前面几块拼起来，put 的逻辑（简化版，省略了为空初始化等细节）是这样： 

final V putVal(int hash, K key, V value, boolean onlyIfAbsent) {
    Node<K, V>[] tab = table;
    int n = tab.length;
    int i = (n - 1) & hash;          // 1. 算出桶下标
    Node<K, V> first = tab[i];

    if (first == null) {
        tab[i] = newNode(hash, key, value, null); // 2. 空桶，直接放
        return null;
    }

    // 3. 桶不空：先看第一个节点是不是同一个 key
    if (first.hash == hash && keyEquals(first.key, key)) {
        // 命中，记录下来，后面替换 value
    } else if (first instanceof TreeNode) {
        // 4. 这个桶已经是红黑树了，按树的方式插入
    } else {
        // 5. 遍历链表
        for (int binCount = 0; ; ++binCount) {
            Node<K, V> next = first.next;
            if (next == null) {
                // 走到链表尾部还没找到，尾插法追加
                first.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash); // 链表够长，转红黑树
                break;
            }
            if (next.hash == hash && keyEquals(next.key, key))
                break; // 链表中找到了同一个 key
            first = next;
        }
    }
    // 命中的话，替换旧 value，返回旧值
    // ...
}

有两个细节值得记住：

  • JDK 8 用尾插法（first.next = newNode(...)）， 而 JDK 7 是头插法。头插法在多线程扩容时可能形成环形链表导致 CPU 100%， 尾插法避免了这个问题（但 HashMap 依然不是线程安全的）。
  • 插入后如果链表长度达到阈值，会触发 treeifyBin。

扩容：什么时候、怎么扩

数组不可能无限大，也不能太小否则冲突多。HashMap 用负载因子（load factor） 来权衡，默认 0.75。当元素个数超过 容量 × 负载因子（这个临界值叫 threshold）， 就触发扩容： 

int threshold = (int) (capacity * 0.75f);
// size 超过 threshold 时，容量翻倍
int newCapacity = capacity << 1;

扩容要把所有元素重新分配到新数组里。由于新容量仍是 2 的幂（翻倍）， 重排有一个非常聪明的优化：一个节点要么留在原下标， 要么挪到原下标 + 旧容量，取决于它的哈希值在“新增的那一位”是 0 还是 1。 

// 扩容时判断节点去留，newCap = oldCap << 1
if ((e.hash & oldCap) == 0) {
    // 这一位是 0：留在低位链（原下标）
} else {
    // 这一位是 1：挪到高位链（原下标 + oldCap）
}

这正是“容量必须是 2 的幂”带来的第二个红利：扩容重排不需要重新计算每个元素的下标， 只需看一个比特位，把一条链表干净地一分为二。

链表转红黑树：那个 8 从哪来

链表太长时，HashMap 会把它转成红黑树，把最坏查找从 O(n) 压到 O(log n)。触发条件是：

  • 链表长度达到 TREEIFY_THRESHOLD = 8；
  • 并且数组容量达到 MIN_TREEIFY_CAPACITY = 64（否则优先扩容而非树化）。

为什么偏偏是 8？这是基于概率分析的。在哈希足够随机、负载因子 0.75 的前提下， 一个桶里的元素个数近似服从参数 λ=0.5 的泊松分布。按这个分布算，一个桶里出现 8 个元素的概率大约是 0.00000006，亿分之六。也就是说，在正常情况下你几乎永远碰不到树化。

所以红黑树是一道防御性的安全网，专门兜底那些哈希极不均匀（比如被恶意构造的 key） 的极端场景，而不是日常路径。理解了这一点，就不会误以为“HashMap 平时都在用红黑树”。

还有个小细节：退化阈值 UNTREEIFY_THRESHOLD = 6，比 8 小。这个“8 升 6 降”的差值是有意的， 为了避免在临界点反复树化、去树化带来的抖动。

线程安全：HashMap 不是用来共享的

最后必须强调：HashMap 不是线程安全的。多线程下可能出现数据丢失、size 不准， 甚至结构损坏。需要并发就用 ConcurrentHashMap——它在 JDK 8 之后用 CAS + synchronized 锁住单个桶，粒度细、性能好，是这个问题的标准答案。

面试考 HashMap，本质上考的是你对“时空权衡”和“工程取舍”的理解： 0.75 的负载因子、2 的幂容量、亿分之六才触发的红黑树，没有一个数字是随便定的。

把这些“为什么”想透了，HashMap 就不再是一段要背的八股，而是一套精巧的设计。 下次被问到，你也能讲出自己的推导过程。