主题 01集合框架

1.1为什么第一站是集合

先说清楚这一章要解决什么问题，不然容易背成一堆散点。

面试里的集合问题有个特点：它从来不是孤立的一道题，而是从你写的代码里长出来的追问。 你说「用 HashMap 存一下」，对方就会问「为什么不用数组」；你答「因为查得快」，对方就问「为什么快」； 你答「哈希」，对方就问「哈希冲突怎么办」；你说「链表」，对方就问「链表长了怎么办」。 这四个问题正好对应本章的四节，一路问下去就是一条完整的知识链。

而这条链的价值不止于面试。算法教程的「哈希表」专题里，几乎所有 O(n) 解法都建立在一句隐含假设上： 「哈希表的查找是常数时间」。这句话为什么成立、什么时候不成立、代价是什么—— 如果你没读过这一章，就只是在用别人的结论；读完之后，你是在用自己理解的工具。

1.2数组与链表的真实取舍

这是集合问题的地基。先把三种存储方式摆在一起看，因为面试里「为什么用 X 不用 Y」的答案， 本质都是在两种代价之间做选择。

光看这张表，结论好像是「链表适合频繁插入删除」。但真实工程里的结论恰好相反： ArrayList 几乎在所有场景都赢，LinkedList 几乎没人用。原因不在复杂度，在 CPU。

被复杂度表藏起来的那个常数

CPU 读内存不是一次读 1 个字节，而是一次搬一整条缓存行（cache line，通常 64 字节）。 数组的元素挨在一起，读 arr[0] 时 arr[1]…arr[15] 很可能已经一起进了缓存， 后面 15 次访问几乎不花时间。

链表的节点是 new 出来的，散在堆的各处，地址之间没有规律。 遍历链表时几乎每次访问都是一次缓存未命中，要等主存。所以： 即使两者的复杂度都写成 O(n)，链表遍历的常数可能是数组的十倍以上。

还有一个常被忽略的点：ArrayList 的「扩容」并不是每次加元素都复制。 容量不足时按 1.5 倍增长（oldCap + (oldCap >> 1)）， 所以连续 n 次尾部插入的均摊代价仍是 O(1)——这就是「均摊复杂度」这个词的来历。

1.3HashMap 的骨架：一次 put 的完整流程

先记住骨架，再记细节。HashMap 在 JDK 8 里的结构是三样东西拼起来的：

一次 put 到底发生了几件事

1. 表为空则先初始化。第一次 put 时 table 还是 null，先按默认容量 16 建表（这一步在 resize() 里做）。
2. 算 hash。不是直接用 hashCode()，而是 (h = key.hashCode()) ^ (h >>> 16)——高 16 位异或到低 16 位，原因见 1.4。
3. 定位桶。i = (n - 1) & hash，n 是数组长度。因为 n 是 2 的幂，这个式子等价于取模但快得多。
4. 桶为空：直接放。新建节点放进 table[i]，然后检查是否需要扩容。
5. 桶不空且首节点 key 相同：覆盖。比较方式是 hash 相等 && (key == 同引用 || key.equals(...))。
6. 首节点是树节点：走红黑树插入。
7. 否则遍历链表：途中发现相同 key 就覆盖；走到尾部都没有，就尾插新节点。
8. 收尾检查两件事：① 链表长度 ≥ 8 → 尝试树化（但容量 < 64 时改为先扩容）；② size > threshold → 扩容。

get 就简单得多，只有三步：算 hash → 定位桶 → 在桶里比对 key。 注意它比对的是「hash 相等且 key 相等」，只比 hash 不够——不同对象完全可能撞 hash。

1.4寻址与扰动：容量为什么必须是 2 的幂

这一节是全章最值得较真的地方，因为它把「一句话结论」变成了「能推导的结论」。

先看那个公式：(n - 1) & hash

n 是桶数组长度。当 n 是 2 的幂时，n - 1 的二进制是一串全 1： n=16 → n-1=15 → 1111。任何数与全 1 做「与」运算，结果就是它的低若干位，正好落在 0 ~ n-1 范围内。 这等价于 hash % n，但位运算比取模快得多，而且取模对负数会得到负结果，位运算不会。

但如果 n 不是 2 的幂，n - 1 的二进制里就有 0，与运算会把那些位强制清掉—— 结果是某些桶永远为空，冲突概率大幅上升。下面这张表用 n=15（反例）说明：

n=15 时 14 = 1110，最低位恒为 0，所以所有 hash 的桶下标都是偶数，奇数桶一个也用不上—— 实际容量直接砍半，冲突翻倍。这就是「容量必须是 2 的幂」的全部原因，不是规定，是数学要求。

再看待过的扰动：h ^ (h >>> 16)

公式里只用到 hash 的低位（因为 n 通常很小，n-1 只覆盖低 4~5 位）。 如果两个 key 的 hashCode() 高位不同、低位相同，它们就会挤在同一个桶里—— 而现实中这种情况很常见：很多对象的 hashCode 是「小整数连续变化」或「地址右移生成的」，低位区分度差。

所以 JDK 加了一步扰动：把自己的高 16 位异或到低 16 位上去。

static final int hash(Object key) {
    int h;
    // ① h >>> 16：把高 16 位无符号右移到低位
    // ② ^ 异或：把「高位信息」掺进「低位」，让低位也带上高位的区分度
    // ③ key == null 时返回 0，所以 HashMap 允许一个 null 键，放在 0 号桶
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

一句话概括：容量是 2 的幂保证了「下标算得对」，扰动函数保证了「下标分得散」。 这两句话能同时说出来，比背十遍源码有用。

1.5扩容与树化

扩容：翻倍，但不重算 hash

当 size > capacity × 0.75 时扩容，容量翻倍。传统写法是「重新遍历所有元素、重新算下标」， JDK 8 用了一个巧妙的观察省掉了重算：

容量翻倍后 n - 1 只多了一个高位 1。所以一个元素的新下标只有两种可能： 要么仍在原位 j，要么挪到 j + oldCap。判断依据就一位：hash & oldCap 是 0 还是 1。

// 扩容的核心：把一条桶链拆成「低位链」和「高位链」，一次遍历搞定
Node<K,V> loHead = null, loTail = null;   // 留在原位的
Node<K,V> hiHead = null, hiTail = null;   // 挪到 j + oldCap 的

for (Node<K,V> p = oldTab[j]; p != null; p = p.next) {
    if ((p.hash & oldCap) == 0) {          // 这一位是 0 → 位置不变
        if (loTail == null) loHead = p; else loTail.next = p;
        loTail = p;
    } else {                                 // 这一位是 1 → 挪到高位
        if (hiTail == null) hiHead = p; else hiTail.next = p;
        hiTail = p;
    }
}
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

树化：兜底，不是常态

树化要同时满足两个条件：链表长度 ≥ 8，且桶数组长度 ≥ 64。 第二个条件常被漏掉——容量不足时，treeifyBin() 会先触发一次扩容而不是树化， 因为扩容后链表自然会变短，比维持一棵树更划算。

退化阈值是 6。这里的 2 个空隙就是前面说的防抖缓冲。

1.6ConcurrentHashMap 怎么做到并发安全

面试常把它和 HashMap 连着问：「HashMap 线程不安全，那用哪个？」答 ConcurrentHashMap 之后， 对方一定会追「它怎么保证线程安全」。答案分两代，能说清差异就够了，不必背源码。

还有一个容易被追问的点：size() 怎么数得准？ 并发下累加一个 size 变量本身就是竞争点。JDK 8 借鉴了 LongAdder 的思路： 用 baseCount 做基础计数，冲突时分散到 CounterCell[] 数组的不同槽位各自累加， 最后求和。这样把「一个热点变量」拆成「多个变量」，显著降低 CAS 失败率。

1.7手写一个能跑的简化 HashMap

这一节对应「能手写」。面试让你手写 HashMap，考的从来不是默写 JDK 源码，而是你有没有真正理解 「数组 + 链表 + 扩容」这三件事的配合。所以下面这版刻意砍掉了红黑树，只保留骨架， 但它能跑、能存、能扩容，且每个关键决策都标了原因。

先明确这版实现了什么、没实现什么，避免你误以为手写题要求一致：

import java.util.Objects;

/**
 * 简化版 HashMap：数组 + 链表 + 扩容。
 * 明确不做的两件事：不树化、不保证并发安全。
 */
public class SimpleHashMap<K, V> {

    /** 桶数组，长度恒为 2 的幂 */
    private Node<K, V>[] table;
    /** 实际键值对数量 */
    private int size;
    /** 扩容阈值 = 容量 × 负载因子 */
    private int threshold;

    private static final float LOAD_FACTOR = 0.75f;
    private static final int INIT_CAP = 16;

    /** 链表节点：只存 hash 不存「算好的下标」，因为扩容后下标会变 */
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    @SuppressWarnings("unchecked")
    public SimpleHashMap() {
        table = (Node<K, V>[]) new Node[INIT_CAP];
        threshold = (int) (INIT_CAP * LOAD_FACTOR);
    }

    /** 与 JDK 8 一致：高 16 位异或到低 16 位，让低位也带上高位信息 */
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /** 容量是 2 的幂时，这个运算等价于取模，但快得多 */
    static int indexFor(int hash, int cap) {
        return hash & (cap - 1);
    }

    public V put(K key, V value) {
        int h = hash(key);
        int i = indexFor(h, table.length);

        // ① 桶为空：直接放，这是最快路径
        if (table[i] == null) {
            table[i] = new Node<>(h, key, value, null);
            if (++size > threshold) resize();
            return null;
        }

        // ② 桶不为空：沿链表比对，命中就覆盖
        Node<K, V> p = table[i];
        while (true) {
            // 必须同时比 hash 和 key：只比 hash 会把不同对象误判为同一个
            if (p.hash == h && Objects.equals(p.key, key)) {
                V old = p.value;
                p.value = value;
                return old;
            }
            if (p.next == null) break;
            p = p.next;
        }

        // ③ 走到尾都没找到：尾插新节点
        //    之所以尾插而不是头插，见 1.5 的死循环分析
        p.next = new Node<>(h, key, value, null);
        if (++size > threshold) resize();
        return null;
    }

    public V get(Object key) {
        int h = hash(key);
        for (Node<K, V> p = table[indexFor(h, table.length)]; p != null; p = p.next) {
            if (p.hash == h && Objects.equals(p.key, key)) return p.value;
        }
        return null;   // 做不到区分「不存在」与「值为 null」，这也是 ConcurrentHashMap 禁 null 的原因
    }

    public int size() {
        return size;
    }

    /** 扩容：容量翻倍，旧元素只可能落在「原位」或「原位 + oldCap」 */
    @SuppressWarnings("unchecked")
    private void resize() {
        int oldCap = table.length;
        Node<K, V>[] oldTab = table;
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[oldCap << 1];
        table = newTab;
        threshold = (int) (newTab.length * LOAD_FACTOR);

        for (int j = 0; j < oldCap; j++) {
            Node<K, V> p = oldTab[j];
            if (p == null) continue;

            // 一条桶链拆成两条：hash 在 oldCap 这一位为 0 的留下，为 1 的挪走
            Node<K, V> loHead = null, loTail = null;
            Node<K, V> hiHead = null, hiTail = null;
            while (p != null) {
                Node<K, V> next = p.next;
                p.next = null;                       // 断开旧链，避免残留指针
                if ((p.hash & oldCap) == 0) {
                    if (loTail == null) loHead = p; else loTail.next = p;
                    loTail = p;
                } else {
                    if (hiTail == null) hiHead = p; else hiTail.next = p;
                    hiTail = p;
                }
                p = next;
            }
            if (loTail != null) newTab[j] = loHead;
            if (hiTail != null) newTab[j + oldCap] = hiHead;
        }
    }

    /** 自测：塞 100 个键，验证 get 全中、size 正确、确实扩容了 */
    public static void main(String[] args) {
        SimpleHashMap<Integer, String> map = new SimpleHashMap<>();
        for (int i = 0; i < 100; i++) map.put(i, "v" + i);

        for (int i = 0; i < 100; i++) {
            if (!("v" + i).equals(map.get(i))) throw new AssertionError("取值失败: " + i);
        }
        map.put(42, "覆盖");                       // 覆盖已有 key
        if (!"覆盖".equals(map.get(42))) throw new AssertionError("覆盖失败");
        if (map.size() != 100) throw new AssertionError("size 错误: " + map.size());

        System.out.println("通过：size=" + map.size()
                + ", 桶数=" + map.table.length + ", 阈值=" + map.threshold);
    }
}

看到什么算通过：编译运行后输出 通过：size=100, 桶数=256, 阈值=192。 桶数 256 是因为从 16 开始，装到 12 扩一次、24 扩一次……一直到 192 之前正好到 256——这个数字能自己推出来，说明你真的懂了扩容。

1.8本章速记卡与自测

四槽格式的意义在这一节体现：四个槽位是固定的，所以你默写时能自查「我漏了哪一格」， 而不是感觉「好像记得又好像忘了」。