← 返回首页 📚 实战课程
📑 本篇章节导航 (共5章,点击直达)
本节目标(学完能回答的面试题)核心知识(1小时精讲内容)面试速记卡(考前30秒速看)练习题(自测)学习资料

L06 - HashMap源码深潜

本节目标(学完能回答的面试题)

核心知识(1小时精讲内容)

一、数据结构总览


JDK 8 HashMap:数组 + 链表 + 红黑树

  Node<K,V>[] table(桶数组)
  ┌─────┐
  │ [0] │ → null
  ├─────┤
  │ [1] │ → Node(K1,V1) → Node(K2,V2) → null         (链表,长度<8)
  ├─────┤
  │ [2] │ → null
  ├─────┤
  │ [3] │ → TreeNode(K3,V3)                            (红黑树,链表长度≥8且数组≥64)
  │     │    ╱              ╲
  │     │ TreeNode(K4,V4)  TreeNode(K5,V5)
  │     │    ╱    ╲              ╱    ╲
  │     │  ...    ...          ...    ...
  ├─────┤
  │ [4] │ → Node(K6,V6) → null
  ├─────┤
  │ ... │
  └─────┘

核心参数:
  DEFAULT_INITIAL_CAPACITY = 16    // 默认初始容量
  DEFAULT_LOAD_FACTOR = 0.75f      // 负载因子
  TREEIFY_THRESHOLD = 8            // 链表→红黑树阈值
  UNTREEIFY_THRESHOLD = 6          // 红黑树→链表阈值
  MIN_TREEIFY_CAPACITY = 64        // 树化的最小数组容量

二、hash计算(扰动函数)


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

// 为什么不直接用 hashCode % length?
// 1. 扰动:高16位异或低16位,让高位也参与定位计算
// 2. 减少冲突:hashCode可能低位变化不大,扰动后分布更均匀
// 3. 定位桶:(n - 1) & hash,等价于 hash % n(n为2的幂时)

// 示例:
// hashCode = 0x12345678
// h >>> 16 = 0x00001234
// hash     = 0x12345678 ^ 0x00001234 = 0x1234444C
// index    = 0x1234444C & 0x0000000F = 0x0C = 12(假设n=16)

三、putVal完整流程(核心源码)


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // ① 初始化table(延迟初始化)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // ② 定位桶,如果桶为空直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {
        Node<K,V> e; K k;

        // ③ 桶中第一个Node的key匹配 → 找到更新目标
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // ④ 桶头是TreeNode → 红黑树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // ⑤ 链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null); // 尾插法!
                    // 链表长度达到8 → 尝试树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1是因为binCount从0开始
                        treeifyBin(tab, hash);             // 注意:不一定真的树化!
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // ⑥ 找到已存在的key → 更新value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // LinkedHashMap回调
            return oldValue;
        }
    }

    ++modCount;

    // ⑦ 检查是否需要扩容
    if (++size > threshold)  // threshold = capacity * loadFactor
        resize();

    afterNodeInsertion(evict);
    return null;
}

putVal流程图:


┌──────────────────────────────────────────────────────────────┐
│                    putVal(key, value)                         │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  1. table为空? → resize()初始化                              │
│                                                              │
│  2. tab[index]为空? → 直接插入新Node                         │
│     │否                                                      │
│     ▼                                                        │
│  3. 头节点key匹配? → 记录e,后续更新value                     │
│     │否                                                      │
│     ▼                                                        │
│  4. 头节点是TreeNode? → putTreeVal红黑树插入                  │
│     │否(链表)                                               │
│     ▼                                                        │
│  5. 遍历链表:                                                │
│     ├── 找到相同key → 记录e,后续更新value                     │
│     └── 遍历到尾部 → 尾插法插入新Node                         │
│         └── 链表长度≥8? → treeifyBin()                       │
│                                                              │
│  6. e != null → 更新旧值,返回旧值                            │
│                                                              │
│  7. ++size > threshold → resize()扩容                        │
│                                                              │
└──────────────────────────────────────────────────────────────┘

四、treeifyBin —— 树化条件(双条件)


final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 关键判断!数组长度 < 64 → 只扩容不树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();  // 优先扩容而不是树化!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 链表转红黑树
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

// 树化双条件:
//   1. 链表长度 ≥ 8(TREEIFY_THRESHOLD)
//   2. 数组长度 ≥ 64(MIN_TREEIFY_CAPACITY)
// 两个条件同时满足才真正树化!
// 只满足条件1 → 只扩容不树化

五、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) { // 已达最大容量
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩容为2倍
        else if ((newCap = oldCap << 1) <= MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // threshold也翻倍
    }
    // ... 初始化分支省略 ...

    // 数据迁移
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            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 {
                // 链表拆分:高位链和低位链(JDK 8优化!)
                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 {
                        // 高位链:新位置 = 原位置 + oldCap
                        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;
}

为什么容量必须是2的幂:


1. 定位桶的公式:index = (n - 1) & hash
   当n为2的幂时,n-1的二进制全为1(如15=1111)
   等价于 hash % n,但位运算比取模快得多

2. 扩容时hash重计算优化:
   新容量 = 2 * 旧容量
   节点在新数组中的位置只有两种可能:
   - 原位置(hash & oldCap == 0)
   - 原位置 + oldCap(hash & oldCap != 0)

   示例(oldCap=16, newCap=32):
   hash=21 (0b10101)
   oldIndex = 21 & 15 = 5 (0b00101 & 0b01111 = 0b00101)
   newIndex = 21 & 31 = 21 (0b10101 & 0b11111 = 0b10101)
   或者 = 5 + 16 = 21
   
   只需要看hash的第5位(oldCap对应的位)是0还是1!

六、JDK 7死链问题 vs JDK 8修复


JDK 7 死链问题(并发扩容时链表成环):

  扩容时使用"头插法"(transfer方法):
  原链表:A → B → C(插入顺序)
  扩容后新链表:C → B → A(反序)

  两个线程同时扩容:
  线程1:取出A,准备插入新表...(被挂起)
  线程2:完成扩容,新链表 C → B → A
  线程1恢复:
    取A → A.next指向新表的B → B.next指向A
    结果:A ⇄ B(环形链表!)
    后续get()操作会死循环!

  ┌─── JDK 7 transfer 头插法 ───┐
  │                              │
  │  while(null != e) {          │
  │    Entry<K,V> next = e.next; │
  │    e.next = newTable[i];     │ ← 头插:新节点指向链表头
  │    newTable[i] = e;          │ ← 更新链表头
  │    e = next;                 │
  │  }                           │
  └──────────────────────────────┘

JDK 8 修复:改用"尾插法" + 高低位拆分

  尾插法保证链表顺序不变 → 不会成环
  高低位拆分(loHead/loTail, hiHead/hiTail) → 不需要遍历链表重新hash

  但注意:JDK 8的HashMap仍然不是线程安全的!
  并发put可能导致数据丢失(两个线程同时往同一个空桶插入,后者的CAS覆盖前者)

七、get流程


public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 先检查桶头
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 红黑树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 链表遍历
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

八、面试追问与回答

Q1: HashMap的key可以是null吗?

可以。null的hash固定为0,存储在table[0]的桶中。但只能有一个null key(因为key不能重复)。value也可以为null。

Q2: 为什么负载因子是0.75?

是时间和空间的折中。太大(如1.0)→ 空间利用率高但冲突多,查找慢;太小(如0.5)→ 冲突少但浪费空间。0.75是统计学上的良好平衡点,且threshold = capacity * 0.75保证是整数(capacity是2的幂)。

Q3: HashMap和HashTable的区别?

(1) HashMap非线程安全,HashTable线程安全(synchronized);(2) HashMap允许null key/value,HashTable不允许;(3) HashMap初始容量16,HashTable 11;(4) HashMap用2的幂+位运算定位,HashTable用素数+取模;(5) HashMap有红黑树优化,HashTable没有。

Q4: hashCode()和equals()的关系?

equals相等的两个对象,hashCode必须相等。hashCode相等的两个对象,equals不一定相等。HashMap先比较hashCode(hash),再比较equals。如果只重写equals不重写hashCode,两个"相等"的对象可能散列到不同桶中,导致get找不到。

Q5: 红黑树的时间复杂度为什么比链表好?

链表查找O(n),红黑树查找O(log n)。当链表长度为8时,红黑树查找最多3次比较。但红黑树节点占用更多内存(TreeNode比Node大),所以只在链表较长时才树化。

面试速记卡(考前30秒速看)

练习题(自测)

1. 手动推演:容量16,依次put key="A"(hash=65), "B"(hash=66), "Q"(hash=81),画出table结构。

2. 为什么树化条件要求数组长度≥64?如果数组长度只有16就树化,会有什么问题?

3. 编写一个测试:创建HashMap,重写key的hashCode让多个key落到同一个桶,观察链表到红黑树的转换。

4. 解释为什么重写equals()必须同时重写hashCode(),用HashMap的put/get流程说明。

5. 比较JDK 7和JDK 8 HashMap扩容的rehash策略差异,解释为什么JDK 8更高效。

学习资料