HashMap 底层原理

HashMap 基于数组 + 链表 + 红黑树（JDK 1.8+）实现，通过 key 的 hashCode() 计算哈希值确定存储位置。当链表长度超过 8 且数组长度 ≥ 64 时，链表会转化为红黑树。默认初始容量为 16，负载因子为 0.75。

数据结构

// JDK 1.8 中 HashMap 的核心结构
transient Node<K,V>[] table; // 哈希桶数组

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 链表下一个节点
}

put 流程

1. 计算 key 的 hash 值：hash = (h = key.hashCode()) ^ (h >>> 16)
2. 确定桶位置：index = (n - 1) & hash（n 为数组长度，即 table.length）
3. 如果桶为空，直接放入新节点
4. 如果桶不为空：
   • key 相同 → 覆盖旧值
   • key 不同 → 链表尾部追加（尾插法）
   • 链表长度 > 8 且 数组长度 ≥ 64 → 转为红黑树；若数组长度 < 64 则优先扩容
5. 元素个数超过阈值（容量 × 负载因子）→ 扩容（容量翻倍）

get 流程

1. 计算 key 的 hash 值
2. 定位到桶位置
3. 遍历链表/红黑树，通过 equals() 比较 key

红黑树的引入

当哈希冲突严重时，链表退化为 O(n) 查找。红黑树将最坏情况优化为 O(log n)。

扩容为什么必须是 2 的幂次方

HashMap 的容量始终保持为 2 的幂次方（16 → 32 → 64 → ...），这不是随意选择，而是出于性能和均匀分布的考量：

1. 用位运算替代取模，速度更快

// 定位桶的索引
index = (n - 1) & hash   // 位运算，极快
// 等价于
index = hash % n          // 取模运算，较慢

只有当 n 是 2 的幂时，(n - 1) & hash 才等价于 hash % n。因为 2 的幂减 1 后，二进制全是 1（例如 16 - 1 = 0b00001111），与 hash 做 & 运算相当于取 hash 的低位，效果等同于取模但性能更高。

2. 扩容时元素迁移更高效

容量翻倍后，每个元素的新位置只有两种可能：

• 原位置不变
• 原位置 + 旧容量

旧容量 n = 16:  (n-1) = 0b00001111
新容量 n = 32:  (n-1) = 0b00011111
                              ↑ 只多看这一位

JDK 1.8 利用这个特性，只需检查 hash 值新增的那一位是 0 还是 1，就能决定元素去向，无需重新计算 hash，大幅优化了扩容性能。

3. 哈希分布更均匀

如果容量不是 2 的幂，(n - 1) 的二进制中会存在 0 位，导致某些桶位置永远不会被映射到，分布不均匀，冲突加剧。

扩容的完整过程

扩容（resize()）是 HashMap 中最重量级的操作——创建一个容量翻倍的新数组，然后把所有元素搬进去。可以想象成一个快递分拣站：原来有 16 个格子，包裹越来越多放不下了，于是换成 32 个格子的新架子，再把所有包裹按照新编号重新归位。

触发时机

                          首次 put
new HashMap() ──────────────────────→ resize()  → 创建 table[16]

                     size > capacity × 0.75
put(key, value) ─── 第13个元素进来了！──→ resize()  → table[16] 变 table[32]
                     (12 = 16 × 0.75)

resize() 在两种场景下被调用：

1. 首次 put：HashMap 的 table 数组采用懒初始化——new HashMap() 时不分配内存，第一次 put 时才通过 resize() 创建长度为 16 的数组
2. 元素数超过阈值：当 size > threshold（threshold = capacity × loadFactor）时触发，默认就是元素数超过容量的 75%

扩容全景图

以容量 4 → 8 为例，直观展示扩容前后数组的变化：

═══════════════════ 扩容前：oldCap = 4, threshold = 3 ═══════════════════

table (长度4)
┌────────┬────────┬────────┬────────┐
│ 桶[0]  │ 桶[1]  │ 桶[2]  │ 桶[3]  │
└───┬────┴───┬────┴───┬────┴────────┘
    │        │        │
    ▼        ▼        ▼
  [A:0100] [B:0001] [C:0010]
    │                  │
    ▼                  ▼
  [D:1000]           [E:0110]
    │
    ▼
  [F:1100]

  已有 6 个元素，超过 threshold=3，触发 resize()！

═══════════════════ 扩容后：newCap = 8, threshold = 6 ═══════════════════

newTab (长度8)
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ 桶[0]  │ 桶[1]  │ 桶[2]  │ 桶[3]  │ 桶[4]  │ 桶[5]  │ 桶[6]  │ 桶[7]  │
└───┬────┴───┬────┴───┬────┴────────┴───┬────┴────────┴───┬────┴────────┘
    │        │        │                  │                  │
    ▼        ▼        ▼                  ▼                  ▼
  [A:0100] [B:0001] [C:0010]          [D:1000]           [E:0110]
                                         │
                                         ▼
                                       [F:1100]

  元素 A 留在桶[0]，D、F 搬到桶[4]；C 留在桶[2]，E 搬到桶[6]

关键变化：原来挤在同一个桶里的元素，扩容后被拆分到两个桶，链表自然变短，查找更快。

元素如何决定去留：只看一个 bit

回顾一下桶定位公式：index = hash & (n-1)。它本质上是取 hash 的低 N 位作为桶下标（容量为 2^N 时，掩码 n-1 刚好是 N 个 1）。

容量翻倍意味着掩码从 N 个 1 变成 N+1 个 1——也就是说，新公式比旧公式多看了 hash 的一个 bit（最高位那个）。这个多出来的 bit 就决定了元素的去留：

以 oldCap=16 → newCap=32 为例：

                    这一位是新多出来的
                           ↓
旧掩码 (16-1) = 0 1111     ← 只看 hash 的低 4 位
新掩码 (32-1) = 1 1111     ← 多看了 hash 的第 5 位
                ↑
          如果这位是 0 → 新 index 和旧 index 一样 → 留在原位
          如果这位是 1 → 新 index = 旧 index + 16  → 搬到新位置

所以 JDK 1.8 不需要重新用 hash & (newCap-1) 算一遍新位置，只需要用 hash & oldCap 检查那个多出来的 bit 是 0 还是 1：

• (e.hash & oldCap) == 0 → 那个 bit 是 0 → 留在原位
• (e.hash & oldCap) != 0 → 那个 bit 是 1 → 搬到 原位 + oldCap

为了更清晰，我们用 oldCap = 16 → newCap = 32 来做一次完整的推演：

oldCap = 16,  旧掩码 = 01111  (16-1)
newCap = 32,  新掩码 = 11111  (32-1)
                        ↑ 第5位，即 oldCap 那一位

假设桶[5] 上挂着三个节点 A → B → C:

节点A:  hash = 69  = 0b 0‖1000101
                          ↑
        旧index = 01000101 & 01111 = 00101 = 5  ✓ 在桶[5]
        hash & oldCap = 01000101 & 10000 = 0    → 留在桶[5]

节点B:  hash = 85  = 0b 1‖0101 01
                          ↑
        旧index = 01010101 & 01111 = 00101 = 5  ✓ 在桶[5]
        hash & oldCap = 01010101 & 10000 = 1    → 搬到桶[5 + 16 = 21]

节点C:  hash = 37  = 0b 0‖0100101
                          ↑
        旧index = 00100101 & 01111 = 00101 = 5  ✓ 在桶[5]
        hash & oldCap = 00100101 & 10000 = 0    → 留在桶[5]

结果：
  旧桶[5]:  A → B → C
            ↓ 扩容后拆分为 ↓
  新桶[5]:  A → C          （第5位 = 0，原地不动）
  新桶[21]: B              （第5位 = 1，原位 + oldCap）

链表拆分的源码实现

resize() 用两对指针（lo 和 hi）把一条链表拆成两条，就像把一副扑克牌按花色分成两堆：

// 遍历旧桶中的链表，拆分为 lo / hi 两条链
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) {        // 新增 bit 为 0 → 留原位
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {                              // 新增 bit 为 1 → 搬新位
        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;          // 放入 原位置 + 旧容量
}

这段逻辑使用尾插法，元素的相对顺序保持不变——这是 JDK 1.8 的重要改进，JDK 1.7 的头插法在并发扩容时会导致链表成环（死循环）。

红黑树的拆分

如果桶中是红黑树，resize() 调用 TreeNode.split() 方法处理。拆分逻辑与链表相同——也是根据 (e.hash & oldCap) 拆成两组。拆分后根据节点数决定结构：

• 节点数 ≤ 6（UNTREEIFY_THRESHOLD）→ 退化为链表（维护树的开销不值得）
• 节点数 > 6 → 重新构建红黑树

resize() 完整源码

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // ① 计算新容量和新阈值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {      // 已达最大容量(2^30)，不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;              // 容量和阈值都翻倍
    }
    else if (oldThr > 0)                       // 指定了初始容量，首次初始化
        newCap = oldThr;
    else {                                     // 无参构造，使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;     // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    if (newThr == 0) {                         // 补算阈值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // ② 创建新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    // ③ 迁移旧数组中的所有元素
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {     // 逐桶处理
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;               // 帮助 GC 回收旧数组

                if (e.next == null)             // 桶中只有一个节点
                    newTab[e.hash & (newCap - 1)] = e;

                else if (e instanceof TreeNode) // 桶中是红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                else {                          // 桶中是链表（≥2 个节点）
                    // 拆分为 lo（留原位）和 hi（搬新位）两条链表
                    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;  // 原位置 + 旧容量
                    }
                }
            }
        }
    }
    return newTab;
}

扩容的性能开销

扩容是 O(n) 操作，需要遍历所有元素。因此：

• 频繁扩容会严重影响性能，每次扩容都要创建新数组 + 迁移全部元素
• 预估容量是最有效的优化：如果已知要存 1000 个元素，用 new HashMap<>(1334)（1000 / 0.75 ≈ 1334）初始化，可以完全避免扩容
• 扩容不会缩容：即使删除了大量元素，HashMap 也不会自动缩小数组。如果需要释放内存，只能创建一个新的 HashMap

链表转红黑树的条件

链表转红黑树需要同时满足两个条件：

为什么需要两个条件？

• 如果数组够小（< 64），说明冲突可能是容量不足导致的，此时优先扩容（resize()）来分散元素，而不是直接树化。
• 只有数组已经足够大、仍然出现长链表时，才说明是真正的哈希冲突热点，这时树化才有意义。

为什么阈值是 8？

根据泊松分布，在良好的哈希函数下，一个桶中出现 8 个元素的概率约为 0.00000006（千万分之六），是极其罕见的事件。选 8 作为阈值，意味着只有在哈希分布极端异常时才会触发树化，正常场景几乎不会发生，避免了不必要的树化开销。

红黑树何时退化回链表？

当红黑树节点数 ≤ 6（UNTREEIFY_THRESHOLD）时，会退化回链表。阈值选 6 而非 8，是为了避免在 8 附近反复树化、退化的抖动。

链表过长的性能影响

如果一个桶上的链表节点过多，会带来严重的性能问题：

性能退化

HashMap 的应对机制（由轻到重）

插入元素 → 链表长度 > 8？
                ├─ 否 → 保持链表
                └─ 是 → 数组容量 ≥ 64？
                            ├─ 否 → 扩容（resize），元素重新分布
                            └─ 是 → 链表 → 红黑树（treeifyBin）

1. 优先扩容：数组容量不足时，通过 resize() 将容量翻倍。扩容后元素会被重新分配到不同的桶，自然缩短链表长度。
2. 树化兜底：扩容后仍然存在长链表（真正的热点冲突），则将链表转为红黑树，将查找复杂度从 O(n) 降为 O(log n)。
3. 退化回链表：当树中节点因删除而减少到 6 个以下时，红黑树退化回链表，降低内存开销（红黑树节点占用的内存约为链表节点的 2 倍）。

hash 扰动函数的作用

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

将 hashCode 的高 16 位与低 16 位做异或，目的是让高位也参与到索引计算中。因为桶定位 (n-1) & hash 只使用了 hash 的低位，如果不做扰动，高位信息完全被浪费，容易产生冲突。扰动后，即使两个 key 的 hashCode 低位相同但高位不同，也能被分散到不同的桶中。

同时重写 hashCode() 和 equals() 的必要性

HashMap 查找 key 分两步：

1. hashCode() → 定位桶位置
2. equals() → 在桶内精确匹配 key

如果只重写其中一个，会出现问题：

Java 规约：如果 a.equals(b) == true，则 a.hashCode() == b.hashCode() 必须成立。

负载因子为什么是 0.75

负载因子（load factor）决定了 HashMap 在多满的时候触发扩容：

0.75 是基于泊松分布的数学计算得出的最佳平衡点——在理想哈希分布下，桶内链表长度超过 8 的概率极小（约千万分之六），同时空间利用率也足够高。

HashMap 的线程安全问题

HashMap 不是线程安全的。多线程并发操作 HashMap 可能导致：

1. 数据丢失：两个线程同时 put，可能覆盖彼此的写入
2. JDK 1.7 死循环：并发 resize() 时头插法导致链表成环，get() 陷入死循环，CPU 飙至 100%
3. JDK 1.8 数据不一致：虽然改为尾插法避免了死循环，但仍存在并发写入丢失、size 计数不准等问题

解决方案对比：

JDK 1.7 并发死循环的原因

JDK 1.7 的 resize() 采用头插法迁移链表元素。两个线程同时扩容时：

原链表: A → B → C

线程1 迁移了 A（暂停）
线程2 完成迁移: C → B → A

线程1 恢复，继续按头插法迁移 B：
  B.next = A（线程1 看到的旧关系）
  A.next = B（线程2 的结果）
  结果: A ↔ B 成环！

一旦链表成环，任何命中该桶的 get() 都会死循环。JDK 1.8 改为尾插法，保持元素原有顺序，从根本上避免了这个问题。

ConcurrentHashMap 的线程安全实现

JDK 1.7：分段锁（Segment）

ConcurrentHashMap
├── Segment[0] (ReentrantLock) → HashEntry[]
├── Segment[1] (ReentrantLock) → HashEntry[]
├── ...
└── Segment[15] (ReentrantLock) → HashEntry[]

• 将数据分为 16 个 Segment，每个 Segment 各自加锁
• 不同 Segment 可以并发读写，最多支持 16 个线程同时写入
• 缺点：Segment 数量固定，锁粒度仍然较粗

JDK 1.8：CAS + synchronized（锁桶头节点）

// put 操作的核心逻辑
if (桶为空) {
    CAS 写入新节点;  // 无锁操作
} else {
    synchronized (桶头节点) {  // 只锁一个桶
        链表或红黑树操作;
    }
}

• 锁粒度细化到单个桶，不同桶完全不阻塞
• 空桶用 CAS 无锁写入，进一步减少竞争
• 读操作利用 volatile 保证可见性，完全无锁

HashMap 与 Hashtable 的区别

ConcurrentHashMap 不允许 null key/value 的原因

在多线程环境下，null 值存在语义歧义：

map.get(key); // 返回 null

// 无法区分：
// 1. key 不存在
// 2. key 存在，但 value 是 null

单线程的 HashMap 可以用 containsKey() 来区分，但在并发环境中，containsKey() 和 get() 之间可能有其他线程修改了数据，导致判断不可靠。因此 ConcurrentHashMap 直接禁止 null，消除歧义。

用 String 作为 HashMap key 的优势

1. 不可变性（Immutable）：String 是 final 类，创建后不可修改。这保证了 key 的 hashCode() 不会变化，不会出现"put 进去后 get 不到"的问题
2. hashCode 缓存：String 内部缓存了 hashCode 值（private int hash），重复计算时直接返回，性能更高
3. equals/hashCode 已正确重写：无需开发者额外处理

反面案例：用可变对象作 key 的危险

List<String> key = new ArrayList<>(Arrays.asList("a", "b"));
map.put(key, "value");

key.add("c");  // 修改了 key，hashCode 改变！
map.get(key);  // 返回 null！找不到了

put 操作的返回值

V put(K key, V value);

• 如果 key 不存在，插入新节点，返回 null
• 如果 key 已存在，用新 value 覆盖旧 value，返回旧 value

这个返回值可以用来判断是"新增"还是"更新"操作。

fail-fast 迭代器机制

HashMap 内部维护一个 modCount 计数器，每次结构性修改（put、remove）都会递增。迭代器创建时记录当前 modCount，每次 next() 时检查：

if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

fail-fast：迭代过程中如果有其他线程（或本线程非迭代器方式）修改了 HashMap，立即抛出异常，快速暴露并发问题。

对比 fail-safe：ConcurrentHashMap 的迭代器是 fail-safe 的，它基于快照思想，不会抛异常，但也不保证能看到迭代期间的修改。

JDK 1.7 与 1.8 的 HashMap 区别

时间复杂度

注意 resize() 是全表操作，时间复杂度始终为 O(n)，这也是为什么要合理设置初始容量以减少扩容次数。

性能优化建议

1. 预估容量：如果已知数据量，用 new HashMap<>(expectedSize / 0.75 + 1) 避免反复扩容
2. 好的 hashCode：确保 key 的 hashCode 分布均匀，避免大量冲突
3. 不可变 key：使用 String、Integer 等不可变对象作 key
4. 避免在多线程中使用 HashMap：用 ConcurrentHashMap 替代
5. JDK 版本：使用 JDK 1.8+，利用红黑树优化最坏情况性能