HashMap源码解析

ℹ️定位说明

Map 系列第 2 篇深读篇：hash 计算的高 16 位异或、put 全流程、2 倍扩容与 rehash、树化阈值 8/6 的取舍、JDK 7 死循环问题。

HashMap 是 Java 中最常用的数据结构之一，基于哈希表实现，允许 null 键/值，非线程安全。

一、存储结构

HashMap 内部由 数组 + 链表 + 红黑树 组成：

transient Node<K,V>[] table; // 数组
static class Node<K,V> {     // 链表节点
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { // 红黑树节点
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

数组：哈希桶，每个位置称为一个 "桶"（bucket）。
链表：解决哈希冲突，冲突的键值对以链表形式存储。
红黑树：当链表长度 ≥8 且数组长度 ≥64 时，链表转换为红黑树（查询效率从 O(n) 提升到 O(logn)）。

二、关键参数

初始容量：默认 16 (DEFAULT_INITIAL_CAPACITY)，必须是 2 的幂。
加载因子（Load Factor）：默认 0.75f (DEFAULT_LOAD_FACTOR)，控制扩容阈值。
扩容阈值：容量 * 加载因子，当元素数量超过阈值时触发扩容。
树化阈值：链表长度 ≥8 且数组长度 ≥64 时转换为红黑树。

三、哈希计算

计算 key 的 hashCode：

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高位与低位异或
   }

通过异或高位和低位，减少哈希冲突。

确定桶的位置：

index = (n - 1) & hash; // n 是数组长度，等价于 hash % n（但位运算更快）

四、put 方法流程

源码核心方法 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. 如果 table 为空或长度为 0，进行扩容（延迟初始化）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 计算桶的位置，若该位置为空，直接插入新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 若节点 key 相同，直接覆盖
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 若节点是红黑树节点，调用树插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5. 遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度 ≥8，尝试树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. 更新已存在的键值对
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 7. 检查是否扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

五、扩容机制

扩容方法 resize()：

新容量：旧容量的 2 倍（保持 2 的幂）。
数据迁移：
- 链表拆分：根据 (e.hash & oldCap) 判断节点在新数组中的位置（原位置或原位置 + 旧容量）。
- 红黑树拆分：调用 split() 方法。

六、红黑树转换

树化条件：

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
       resize(); // 数组长度不足 64 时优先扩容
   else {
       // 将链表转换为红黑树
       TreeNode<K,V> hd = null, tl = null;
       for (Node<K,V> e = tab[index]; e != null; e = e.next) {
           TreeNode<K,V> p = replacementTreeNode(e, null);
           if (tl == null)
               hd = p;
           else {
               p.prev = tl;
               tl.next = p;
           }
           tl = p;
       }
       tab[index] = hd;
       if (hd != null)
           hd.treeify(tab);

七、线程安全问题

HashMap 非线程安全，多线程操作可能导致：

数据覆盖：同时 put 导致数据丢失。
死循环：JDK 1.7 及之前链表头插法扩容时可能形成环形链表（JDK 1.8 改用尾插法修复）。

八、性能优化建议

预分配容量：避免频繁扩容，初始化时指定预期大小。
重写 hashCode() 和 equals()：确保键的哈希分布均匀，减少冲突。

源码设计亮点

位运算优化：用 & 代替 % 计算桶位置。
延迟初始化：首次 put 时分配内存。
红黑树退化：当红黑树节点 ≤6 时退化为链表。

通过深入源码，可以更好地理解 HashMap 的高效设计与潜在风险，合理使用以优化性能。

⬅️ HashMap 🏠 00-Java ➡️ LinkedHashMap

02-HashMap源码解析