HashMap 进阶：寻址算法、扩容死循环，一次说透 HashSet 和 HashTable

未若君雅裁

545人浏览 · 2026-06-01 08:27:27

未若君雅裁 · 2026-06-01 08:27:27 发布

上一篇把 HashMap 的数据结构和 put 流程讲完了，这一篇专攻那些面试官喜欢深挖的问题——寻址算法里的扰动函数是怎么回事，为什么数组长度非得是 2 的 n 次幂，扩容时数据是怎么迁移的，JDK 1.7 的死循环到底是怎么形成的。最后把 HashSet 和 HashTable 这两个"亲戚"也一并搞清楚。

寻址算法：hash 值是怎么变成数组下标的

HashMap 的寻址分三步走：

源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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

// putVal 中的寻址：
// tab[i = (n - 1) & hash]

第一步：hashCode()

Object.hashCode() 返回一个 int 值，32 位，范围从 -2147483648 到 2147483647。真正用来做数组下标的是低几位。

第二步：扰动函数 hash()

(h = key.hashCode()) ^ (h >>> 16)

把 hashCode 的高 16 位和低 16 位做异或运算。为什么要多此一举？

因为当数组长度比较小的时候（比如容量 16，n-1 = 15，二进制 0000 1111），(n-1) & hash 实际上只用到了 hash 值的低 4 位。高 28 位完全没参与运算，白白浪费了。

扰动函数让高 16 位的信息"混"进了低 16 位，这样 (n-1) & hash 的时候高低位的信息都参与了下标计算，哈希分布更均匀，冲突更少。

第三步：(n-1) & hash 代替取模

如果数组长度 n 是 2 的幂，那 (n-1) & hash 等价于 hash % n，但位运算快得多。

举个例子，n = 16：

n - 1 = 15  →  二进制 0000 0000 0000 1111
hash      →  二进制 xxxx xxxx xxxx 1101

(n-1) & hash → 只看 hash 的低 4 位，范围 0~15，恰好是数组下标的范围

为什么数组长度必须是 2 的 n 次幂？

两个原因，都跟位运算有关。

原因一：用位与代替取模

上面说了，只有当长度是 2 的幂时，hash % n 才能等价替换成 hash & (n-1)。位运算比取模快一个数量级。

原因二：扩容时简化数据迁移

扩容翻倍后，老数据要迁移。对于每个节点，只需要用 e.hash & oldCap 判断它的位置：

为什么这招成立？因为 e.hash & oldCap 检查的就是 hash 值在 oldCap 对应位（第 5 位，16 = 2^4）是 0 还是 1。

容量 16：n-1 = 15 = 0000 1111    → 用低 4 位定下标
容量 32：n-1 = 31 = 0001 1111    → 用低 5 位定下标

扩容后多用了 1 位。如果这一位是 0，下标不变；如果是 1，下标 = 原下标 + oldCap

这比 JDK 1.7 那种对每个元素重新 hash 再取模的做法高效太多。

扩容机制完整流程

扩容的触发条件是 ++size > threshold，threshold = 容量 × 加载因子。

以默认值举例：

初始化：容量 16，threshold = 16 × 0.75 = 12
第 13 个元素插入时触发第一次扩容：容量 16 → 32，threshold → 24
第 25 个元素插入时触发第二次扩容：容量 32 → 64，threshold → 48

扩容的核心代码：

final Node<K,V>[] resize() {
    // ...
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  // threshold 也翻倍
    }
    // ...
    // 数据迁移部分（链表）：
    Node<K,V> loHead = null, loTail = null;  // 低位链表
    Node<K,V> hiHead = null, hiTail = null;  // 高位链表
    Node<K,V> next;
    do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {
            // 放低位链表
            if (loTail == null) loHead = e;
            else loTail.next = e;
            loTail = e;
        } else {
            // 放高位链表
            if (hiTail == null) hiHead = e;
            else hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
    if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;          // 低位：原位置
    }
    if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead; // 高位：原位置 + oldCap
    }
}

注意扩容之后，红黑树也可能退化成链表。如果树拆分后节点数 ≤ 6，就会退化成链表，不至于为了六七个节点还维持一棵树的复杂结构。

JDK 1.7 的死循环问题

这个问题面试特别喜欢问。JDK 1.7 的 HashMap 在扩容时使用的是头插法，多线程并发扩容时可能形成环形链表，导致 get 操作进入死循环 CPU 100%。

先理解 1.7 的头插法做了什么：

// JDK 1.7 的 transfer 方法（简化）
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while (null != e) {
            Entry<K,V> next = e.next;    // 保存下一个节点
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];         // 把 e 插到链表头部
            newTable[i] = e;              // e 成为新的链表头
            e = next;                     // 处理下一个
        }
    }
}

头插法会把原来 A→B 的顺序颠转为 B→A。

死循环的形成过程，用一个时序图来看两个线程的交替执行会更清楚：

把这个过程拆成三步来看：

第一步：初始状态

链表是 A → B → null。线程 1 的局部变量 e = A, next = B，正准备迁移时被挂起。线程 2 也拿到了相同的引用 e = A, next = B。

第二步：线程 2 先完成扩容

线程 2 用头插法完整执行了 transfer：

第 1 轮：A 插入新链表 → A → null
第 2 轮：B 插入新链表头部 → B → A → null

因为头插法，顺序颠倒了。此时堆内存中 B.next 已经指向了 A。

第三步：线程 1 恢复，环形链表形成

线程 1 的局部变量还停留在旧状态 e = A, next = B：

第 1 轮：A 插入自己的新链表，e = next = B
第 2 轮：B 插入链表头部。但此时 B.next 已经被线程 2 改成了 A。B 插入后，B.next = A，而 A 也在链表中……A 的 next 在这个线程 1 的新链表中指向什么？取决于具体实现，但形成了一个环形结构
第 3 轮：e = next = A（因为在第 1 轮中 A 是链头），而 A 已经在链表中

之后任何对这个桶做 get 操作，链表遍历就会陷入死循环：B → A → B → A → B → A……

JDK 1.8 解决了这个问题，方式就是改用尾插法——链表插入时保持原有顺序，不会形成环。

但注意：JDK 1.8 的 HashMap 仍然不是线程安全的。它只是避免了死循环这个具体 bug，多线程 put 仍然会丢数据、覆盖值。并发场景请用 ConcurrentHashMap。

HashSet 与 HashMap 的关系

HashSet 的源码非常短，核心就一句话：

public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private transient HashMap<E,Object> map;

    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

HashSet 底层就是一个 HashMap。元素存在 HashMap 的 key 里，value 统一是一个叫做 PRESENT 的占位 Object。add 元素就是往 HashMap 里 put(key, PRESENT)，remove 就是 map.remove(key)。

所以 HashSet 的去重能力、无序性、允许 null 元素，全部来自 HashMap 的特性。理解了 HashMap，HashSet 等于白送。

HashTable 与 HashMap 的区别

对比维度	HashMap	HashTable
出现版本	JDK 1.2	JDK 1.0
线程安全	不安全	安全（方法加 synchronized）
性能	高	低（锁整个表）
是否允许 null	key 和 value 都可以 null	key 和 value 都不允许 null
初始容量	16	11
扩容机制	2 倍	2n + 1
数据结构	数组 + 链表 + 红黑树	数组 + 链表

HashTable 为什么用 11 和 2n+1？

HashTable 的容量选择跟 HashMap 走的是两条路。HashMap 用 2 的次幂是为了位运算优化；HashTable 用素数（11, 23, 47…即 2n+1 找最近素数）是为了让哈希分布更均匀。

原理是这样的：HashTable 内部用 hashCode % table.length 做取模运算。如果容量是合数（比如 10=2×5），当 hashCode 有某种规律时（比如都是偶数），会和容量产生公约数，导致某些桶利用率极低，加剧冲突。换成素数（比如 11），hashCode 跟容量取模时，结果的分布会更加均匀——因为素数没有非 1 非自身的因子，公约数效应被消除了。

那 HashMap 为什么不用素数？因为 HashMap 用 (n-1) & hash 代替取模，这要求 n 必须是 2 的次幂。牺牲了素数的均匀性优势，换来了位运算的性能优势，同时依赖扰动函数（高低位异或）来弥补分布的均匀性。两种设计取舍的路线不同。

HashTable 已经基本被淘汰了。主要原因有三个：

第一，HashTable 给每个方法都加了 synchronized，并发性能很差——所有线程读写都要抢同一把锁。

第二，Hashtable 不允许 null 键和 null 值，用起来不够灵活。

第三，有了更好的替代品 ConcurrentHashMap（分段锁/CAS + synchronized），没必要再用 HashTable。

ConcurrentHashMap 的演进：从分段锁到 CAS

面试时如果你主动对比 ConcurrentHashMap 和 HashTable 的锁粒度差异，会是一个加分项。

ConcurrentHashMap 自己也经历了一次重大重构：

JDK 1.7：分段锁（Segment）

// 1.7 的 ConcurrentHashMap 内部结构
final Segment<K,V>[] segments;  // 默认 16 个 Segment
// 每个 Segment 内部是一个小 HashMap + 一把 ReentrantLock

思路是"把整张表切成 16 段，每次只锁一段"。并发度默认 16，意味着最多同时有 16 个线程在写不同 Segment 时互不阻塞。比 HashTable 的全表锁是质的提升。

但分段锁也有问题：Segment 数量在构造时固定，不能动态扩展。如果数据量增长远超预期，一个 Segment 里的数据越来越多，锁竞争还是会加剧。而且 Segment 继承了 ReentrantLock，每个 Segment 是一个重量级对象，内存开销大。

JDK 1.8：CAS + synchronized 锁桶头

1.8 完全放弃了 Segment 概念，锁粒度从"段"精细到"桶"（单个数组位置）：

JDK 1.8 ConcurrentHashMap:
  - put 时如果桶为空 → CAS 尝试直接写入（无锁）
  - put 时如果桶有数据 → synchronized 锁住桶的头节点
  - 读操作完全无锁（volatile 保证可见性）
  - 扩容时多个线程可以协同迁移数据

为什么换成 synchronized 而不是继续用 ReentrantLock？

JDK 1.6 之后 synchronized 做了大量优化（偏向锁、轻量级锁、锁粗化），在低竞争场景下性能已经接近甚至超过 ReentrantLock
synchronized 是 JVM 内置的，JIT 编译器可以做更多内联优化，而 Lock 是类库层面的
锁粒度是单桶级别，大多数情况下只有一两个线程竞争同一个桶，synchronized 的偏向锁/轻量级锁效率极高

加一个对比总结：

对比项	HashTable	ConcurrentHashMap 1.7	ConcurrentHashMap 1.8
锁粒度	全表	分段（默认16段）	单桶
锁实现	synchronized	ReentrantLock	CAS + synchronized
读并发	全阻塞	不完全阻塞	完全不阻塞（volatile）
扩容并发	单线程	单线程	多线程协同

面试时如果能把 HashTable → ConcurrentHashMap 1.7 → 1.8 这条演进线讲清楚，面试官就知道你是真的理解了并发容器的设计思路，而不只是背答案。

面试模板

问：“HashMap 的寻址算法是怎样的？为什么数组长度是 2 的幂？”

答：

HashMap 的寻址分两步。第一步是调用 hash 方法，把 key.hashCode() 的高 16 位和低 16 位做异或扰动，让高位也参与下标计算，减少哈希冲突。第二步用 (n-1) & hash 得到数组下标。

数组长度必须是 2 的幂有两个原因。一是计算索引时可以用位与运算代替取模，效率更高。二是扩容迁移数据时，只需要判断 e.hash & oldCap 是否为 0 就能确定元素是留在原位还是移动到原位加 oldCap 的位置，不需要重新计算 hash。

问：“JDK 1.7 HashMap 为什么会死循环？”

答：

JDK 1.7 的 HashMap 在扩容数据迁移时使用头插法，会把链表顺序颠倒。多线程并发扩容时，可能出现两个线程同时操作同一个链表。线程 A 记录了 e 和 next 的引用后被挂起，线程 B 完成扩容，链表已经被反转。线程 A 恢复后继续按原引用操作，最终导致链表中出现环形引用——一个节点的 next 指向了前面已经处理过的节点。此后对这个链表做 get 操作就会陷入死循环，CPU 100%。

JDK 1.8 把插入方式从头插法改为尾插法，就不会出现环形链表了。不过 1.8 的 HashMap 仍然不是线程安全的，put 操作在多线程下会丢数据，并发场景应该用 ConcurrentHashMap。

问：“HashSet 和 HashMap 是什么关系？HashTable 和 HashMap 有什么区别？”

答：

HashSet 底层就是通过 HashMap 实现的。它内部维护了一个 HashMap，add 元素时把元素当做 HashMap 的 key，value 是一个共享的 Object 占位符 PRESENT。HashSet 的去重、无序、允许 null 都来自 HashMap。

HashTable 是 JDK 1.0 的老类，方法加了 synchronized，线程安全但是全表锁，性能低，不允许 null 键值。HashMap 是 JDK 1.2 加入的，线程不安全但性能高，允许一个 null 键和多个 null 值。实际开发中 HashTable 基本不推荐使用，需要线程安全用 ConcurrentHashMap。