集合-HashMap源码解析.md

HashMap 深度剖析：从原理到源码

HashMap 是 Java 集合框架中最常用的实现类之一，基于哈希表实现 Map<K,V> 接口，支持键值对存储，允许 null 键和 null 值，非线程安全。其核心优势是 查询、插入、删除操作的平均时间复杂度为 O(1)，但在极端哈希冲突下可能退化为 O(n)（JDK 1.8 引入红黑树优化为 O(logn)）。

一、数据结构演变：从「数组+链表」到「数组+链表+红黑树」

HashMap 的底层数据结构在 JDK 1.7 和 JDK 1.8 中有显著差异，理解这种演变是掌握其原理的关键。

1.1 JDK 1.7：数组 + 链表

• 数组（Entry[] table）：作为哈希表的主体，每个元素是一个链表的头节点，数组索引通过哈希计算得到。
• 链表（Entry 节点）：当多个键（Key）计算出相同的数组索引时（哈希冲突），通过链表将这些键值对串联起来，每个 Entry 包含 key、value、next（下一个节点引用）和 hash（键的哈希值）。

1.2 JDK 1.8：数组 + 链表 + 红黑树

• 数组（Node<K,V>[] table）：主体结构不变，节点类型从 Entry 改为 Node（功能类似）。
• 链表 → 红黑树：当链表长度超过阈值（默认 TREEIFY_THRESHOLD = 8），且数组长度 ≥ MIN_TREEIFY_CAPACITY（默认 64）时，链表会转为红黑树（节点类型变为 TreeNode，继承 Node）。
  • 红黑树优势：链表查询时间复杂度为 O(n)，红黑树为 O(logn)，大幅优化哈希冲突严重时的性能。
  • 转回链表：当红黑树节点数减少到 UNTREEIFY_THRESHOLD（默认 6）时，会退化为链表。

二、核心成员变量：控制哈希表行为的关键参数

HashMap 的行为由多个核心变量控制，理解这些变量的作用是分析源码的基础：

// 1. 哈希表主体数组（首次使用时初始化，长度为 2 的幂次方）
transient Node<K,V>[] table;

// 2. 键值对数量（当前存储的有效元素数）
transient int size;

// 3. 结构性修改次数（用于快速失败机制，如迭代器）
transient int modCount;

// 4. 扩容阈值（当 size > threshold 时触发扩容，threshold = capacity * loadFactor）
int threshold;

// 5. 负载因子（默认 0.75，控制哈希表的「填满程度」）
final float loadFactor;

// 6. 链表转红黑树的阈值（默认 8）
static final int TREEIFY_THRESHOLD = 8;

// 7. 红黑树转链表的阈值（默认 6）
static final int UNTREEIFY_THRESHOLD = 6;

// 8. 允许链表转红黑树的最小数组容量（默认 64）
static final int MIN_TREEIFY_CAPACITY = 64;

关键变量解析：

• 负载因子（loadFactor）：默认 0.75，是「时间-空间」权衡的结果。

  • 若 loadFactor 过小（如 0.5）：哈希表填充率低，冲突少，但数组利用率低，浪费空间。
  • 若 loadFactor 过大（如 1.0）：空间利用率高，但冲突概率增加，链表/红黑树变长，查询效率下降。
  • 为什么是 0.75？ 根据泊松分布，当 loadFactor=0.75 时，链表长度为 8 的概率仅为 0.00000006（几乎不可能），此时转红黑树的收益最大。

• 数组长度（capacity）：始终为 2 的幂次方（初始化时或扩容后）。这是为了通过 (n-1) & hash 快速计算数组索引（等价于 hash % n，但位运算效率更高）。

三、哈希计算：如何将 Key 映射到数组索引？

HashMap 的核心是通过哈希函数将 Key 映射到数组索引，分为两步：计算 Key 的哈希值 和 通过哈希值计算索引。

3.1 哈希值计算（hash(Object key) 方法）

static final int hash(Object key) {
    int h;
    // 1. 若 key 为 null，哈希值为 0（HashMap 允许 null 键，固定存储在索引 0）
    // 2. 否则，取 key 的 hashCode()，并将高 16 位与低 16 位异或（减少哈希冲突）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 为什么异或高 16 位？
  若直接用 hashCode() 作为哈希值，当数组长度较小时（如 16），(n-1) & hash 实际上只用到了哈希值的低 4 位，高 28 位被忽略，容易导致冲突。通过 h ^ (h >>> 16)，将高 16 位的「特征」混入低 16 位，减少冲突概率。

3.2 索引计算（(n-1) & hash）

数组索引通过 (n-1) & hash 计算，其中 n 是数组长度（2 的幂次方）。例如：

• 若 n=16（二进制 10000），则 n-1=15（二进制 01111），(n-1) & hash 等价于 hash % 16，但位运算效率更高。
• 若 n 不是 2 的幂次方，n-1 的二进制会存在 0 位，导致某些索引永远无法被映射（如 n=10 时 n-1=9 二进制 1001，此时索引的第 2、3 位永远为 0），增加冲突。

四、核心方法源码剖析

4.1 put(K key, V value)：插入键值对

put 方法的核心逻辑在 putVal 中，流程如下：

1. 若数组 table 未初始化，先调用 resize() 初始化；
2. 计算 Key 的哈希值和数组索引 i，若 table[i] 为空，直接插入新节点；
3. 若 table[i] 不为空（哈希冲突）：
   • 若头节点的 Key 与当前 Key 相同，直接覆盖 Value；
   • 若头节点是红黑树节点（TreeNode），调用红黑树的插入方法；
   • 若头节点是链表节点，遍历链表：
     • 若找到 Key 相同的节点，覆盖 Value；
     • 若未找到，尾插法插入新节点，插入后若链表长度 ≥ TREEIFY_THRESHOLD，调用 treeifyBin 尝试转红黑树；
4. 插入成功后，若 size 超过 threshold，调用 resize() 扩容。

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;
    // 步骤 1：若数组未初始化，调用 resize() 初始化（n 为数组长度）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤 2：计算索引 i，若 table[i] 为空，直接插入新节点（尾插法）
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { // 步骤 3：哈希冲突处理
        Node<K,V> e; K k;
        // 3.1 头节点 Key 相同，记录 e 用于后续覆盖 Value
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 3.2 红黑树节点，调用红黑树插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 3.3 链表节点，遍历链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 3.3.1 遍历到链表尾部，尾插法插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入后链表长度 ≥ 8，尝试转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 因为从 0 开始计数
                        treeifyBin(tab, hash);
                    break;
                }
                // 3.3.2 找到 Key 相同的节点，跳出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 步骤 4：若找到 Key 相同的节点，覆盖 Value（onlyIfAbsent 为 false 时）
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // LinkedHashMap 回调，HashMap 为空实现
            return oldValue;
        }
    }
    ++modCount; // 结构性修改计数
    // 步骤 5：若 size 超过 threshold，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // LinkedHashMap 回调，HashMap 为空实现
    return null;
}

4.2 resize()：扩容机制

当 size > threshold 时触发扩容，核心逻辑：

1. 计算新容量：新容量 = 旧容量 × 2（若旧容量为 0，初始化为默认容量 16）；
2. 计算新阈值：新阈值 = 新容量 × loadFactor（若旧阈值为 0，初始化为 16 × 0.75 = 12）；
3. 转移元素：将旧数组中的元素重新映射到新数组（JDK 1.8 优化了 rehash 过程）。

JDK 1.8 扩容的 rehash 优化：
旧数组长度为 oldCap（2 的幂次方），新数组长度为 newCap = oldCap × 2。对于某个元素的哈希值 hash：

• 若 (hash & oldCap) == 0：新索引 = 旧索引；
• 若 (hash & oldCap) != 0：新索引 = 旧索引 + oldCap。

原理：oldCap 是 2 的幂次方，其二进制只有最高位为 1（如 oldCap=16 时二进制 10000）。hash & oldCap 本质是判断 hash 的第 log2(oldCap) 位是否为 1，若为 0 则索引不变，若为 1 则索引增加 oldCap。
这一优化避免了 JDK 1.7 中重新计算所有元素哈希值的开销，提升扩容效率。

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;

    // 情况 1：旧数组已初始化（oldCap > 0）
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { // 达到最大容量（2^30），不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量 = 旧容量 × 2，若未超过最大容量且旧容量 ≥ 初始容量（16），新阈值 = 旧阈值 × 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    // 情况 2：旧数组未初始化，但旧阈值 > 0（用户指定了初始容量，通过 tableSizeFor 转为 2 的幂次方）
    else if (oldThr > 0) 
        newCap = oldThr;
    // 情况 3：旧数组未初始化且旧阈值 = 0（使用默认值：容量 16，阈值 12）
    else { 
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 计算新阈值（若未在情况 1/2 中设置，如用户指定初始容量时）
    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; // 释放旧数组引用
                // 情况 A：当前桶只有一个节点，直接计算新索引并放入新数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 情况 B：当前桶是红黑树，拆分红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 情况 C：当前桶是链表，按 (hash & oldCap) 拆分链表为两个子链表
                else { 
                    Node<K,V> loHead = null, loTail = null; // 新索引 = 旧索引
                    Node<K,V> hiHead = null, hiTail = null; // 新索引 = 旧索引 + oldCap
                    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;
}

4.3 treeifyBin(Node<K,V>[] tab, int hash)：链表转红黑树

当链表长度 ≥ TREEIFY_THRESHOLD（8）时，调用 treeifyBin 方法。但转红黑树有前置条件：数组长度必须 ≥ MIN_TREEIFY_CAPACITY（64），否则会先触发扩容而非转树。

treeifyBin 核心逻辑：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 若数组为空或长度 < 64，调用 resize() 扩容而非转树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 将链表节点转为红黑树节点（TreeNode）
        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);
    }
}

4.4 get(Object key)：查询键值对

get 方法逻辑较简单：

1. 计算 Key 的哈希值和数组索引；
2. 若索引位置为红黑树，调用红黑树查询方法；
3. 若为链表，遍历链表查找 Key 相同的节点；
4. 找到则返回 Value，否则返回 null。

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;
}

五、JDK 1.7 vs JDK 1.8：核心差异对比

特性	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树（链表过长时）
链表插入方式	头插法（扩容时可能导致环形链表）	尾插法（避免环形链表）
扩容 rehash	重新计算所有元素哈希值	优化为 (hash & oldCap) 判断新索引
查询效率	最坏 O(n)	最坏 O(logn)（红黑树）
null 键处理	允许，存储在索引 0	允许，存储在索引 0

六、线程安全问题

HashMap 非线程安全，多线程环境下可能出现以下问题：

1. 并发修改异常（ConcurrentModificationException）：迭代时若其他线程修改了 modCount，会触发快速失败机制。
2. 数据覆盖：多线程同时 put 可能导致后插入的元素覆盖先插入的元素。
3. JDK 1.7 死循环：扩容时头插法可能导致链表成环，后续 get 会陷入死循环（JDK 1.8 尾插法已修复）。

线程安全替代方案：

• Hashtable：方法加 synchronized，效率低。
• ConcurrentHashMap：JDK 1.8 基于 CAS + synchronized 实现，并发效率高。

七、最佳实践与注意事项

1. 初始容量设置：若已知存储元素数量，建议初始化时指定容量 initialCapacity = (int)(expectedSize / loadFactor) + 1，避免频繁扩容。例如，预计存储 100 个元素，initialCapacity = 100 / 0.75 + 1 ≈ 134，HashMap 会自动转为 256（下一个 2 的幂次方）。
2. Key 的选择：Key 应重写 hashCode() 和 equals()，确保：
   • 若 a.equals(b)，则 a.hashCode() == b.hashCode()；
   • hashCode() 结果稳定（避免使用可变对象作为 Key，如 ArrayList，修改后哈希值变化会导致无法查询）。
3. 避免使用 null Key/Value：虽然允许，但可能增加代码歧义（无法区分「Key 不存在」和「Value 为 null」）。

总结

HashMap 是基于哈希表的高效键值对存储结构，通过「数组+链表+红黑树」的组合优化了哈希冲突场景下的性能。核心机制包括哈希计算、冲突解决（链地址法）、动态扩容和红黑树转换。理解其源码中的哈希函数设计、扩容优化和数据结构转换逻辑，有助于写出更高效的 Java 代码，并应对面试中的深入提问。