HashMap 深度分析

作者：Ethan.Yang
博客：https://blog.ethanyang.cn (opens new window)

---

基于JDK11进行分析, 大部分公司已经开始使用JDK11

一、继承体系

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

类/接口	作用	说明
AbstractMap	抽象骨架	提供了 Map 的骨架实现，简化了子类开发
Map	行为规范	Java 集合的基础接口，定义键值对容器行为
Cloneable	接口能力	支持对象浅拷贝，可使用 clone() 方法
Serializable	接口能力	支持序列化，可通过网络传输或持久化存储

---

二、底层数据结构解析

HashMap 是基于数组 + 链表 + 红黑树的复合结构实现的散列表（Hash Table），为了兼顾时间复杂度与空间效率，JDK8 引入了链表树化机制来解决哈希冲突性能问题。

核心属性

transient Node<K,V>[] table;     // 主体数组（哈希桶），每个桶存储一个链表或红黑树
transient int size;              // 实际存储的键值对数量
int threshold;                   // 扩容临界值 = capacity * loadFactor
final float loadFactor;          // 负载因子，默认 0.75

Node 节点定义

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

• 类似链表结构，用于哈希冲突时的链式存储

• 每个桶（table[i]）存储的是一个链表或红黑树

红黑树支持（JDK8+）

当链表长度大于等于 TREEIFY_THRESHOLD（默认8），且哈希表长度大于 MIN_TREEIFY_CAPACITY（默认64）时，链表会转为红黑树以提升查询效率。

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

• 继承自 LinkedHashMap.Entry 是为了保留插入顺序

• 红黑树结构仅用于桶中的冲突链优化，不影响全局数据结构

• 当多个 key 的 hash 冲突（即定位到同一个桶 table[i]）时，会以链表形式串联

• 如果链表长度超过 TREEIFY_THRESHOLD（默认是 8），就会尝试将链表转换成红黑树，提升查询性能

• 红黑树查询复杂度：O(log n)，链表是 O(n)

树化条件

链表转红黑树有两个条件：

static final int TREEIFY_THRESHOLD = 8;        // 链表长度 >= 8 触发树化
static final int UNTREEIFY_THRESHOLD = 6;      // 树节点数 < 6 时退化为链表
static final int MIN_TREEIFY_CAPACITY = 64;    // 哈希表容量 >= 64 才允许树化

树化前会先检查 table 的容量是否 >= 64，如果不满足会先扩容而不是树化。

数组索引计算（定位桶位置）

int index = (n - 1) & hash

• n 是数组长度，必须是 2 的幂
• 这种按位与操作比取模（%）效率高
• JDK 保证数组扩容后的容量始终是 2 的幂

哈希扰动函数（hash()）

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

• 高位与低位做异或，增加随机性，避免低位冲突
• 让高位信息参与 index 的计算，提高分布均匀性

延迟初始化机制

HashMap 的底层数组是 懒加载的：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 不会立刻初始化 table
}

• 第一次 put 时才初始化 table
• 优点：节省内存（避免空集合浪费空间）

扩容机制（resize）

当元素个数超过 threshold = capacity * loadFactor，会触发扩容。

扩容策略

• 扩容为原来的 2 倍（如 16 → 32）
• 所有元素重新 hash，并再分配到新桶位

高效再分配方式（JDK8 优化）

元素在扩容后只会落入两个位置：

oldIndex 或 oldIndex + oldCapacity

原因：扩容后容量翻倍，掩码多一位：

• 假设旧容量是 16，hash = 101100
• 扩容后容量是 32
• 新索引只受新高位 hash & 16 控制，无需重新计算 hashCode

table[]
  ↓
+------------+
|  Bucket 0  | → null 或 Node / TreeNode
+------------+
|  Bucket 1  | → Node1 → Node2 → ...
+------------+
|  Bucket 2  | → TreeNode1
+------------+
|  ...       |

fail-fast 机制

transient int modCount;

在 HashMap 源码里，modCount 是一个 记录结构性修改次数 的字段：

结构性修改 包括：

• put（新增键值对）
• remove（删除键值对）
• resize（扩容）

但 仅修改 value 不算结构性修改（因为结构没变）。

HashMap 的迭代器会在创建时保存一个 expectedModCount：

expectedModCount = modCount;

然后在遍历过程中，每次 next() 都会检查：

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

只要在遍历过程中集合被结构性修改了（modCount 自增），检查就会失败，抛出异常。

---

二、核心方法解析(JDK11)

增

put(K key, V value)

public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);
}

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 未初始化或长度为 0，先 resize
    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;
        // ③ 桶中第一个节点 key 相同
        if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④ 桶为树节点，走红黑树插入
        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)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // ⑥ 如果找到相同 key，替换值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    ++modCount;
    // ⑦ 超过阈值，扩容
    if (++size > threshold)
        resize();
    return null;
}

1. 对 key 取hash, 调用 putVal

2. putVal

   • 先定位桶位置

   • 桶空 → 新节点

   • 桶非空 → 树节点插入 / 链表尾插

   • 链长 ≥ 8 → 树化

   • 超过阈值 → 扩容

从 ③ 处可以看出，HashMap 在查找节点时，首先会根据 hash 定位到对应的桶，然后在桶内再通过 equals 判断键是否相等。 如果 equals 返回 true，则认为是相同的 key，会直接覆盖旧值。 这正是我们常说的 hashCode 和 equals 需要同时重写 的原因： hashCode 决定元素分布位置，equals 决定同一桶中对象是否相等，二者配合才能确保键的唯一性。

删

remove(Object key)

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
}


final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;

    // ① 检查 table 不为空 且 长度 > 0 且 桶首节点不为 null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {

        Node<K,V> node = null, e; // 要删除的节点引用
        K k; V v;

        // ② 桶首节点命中（hash 和 key 都相等）
        if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k)))) {
            node = p;
        }
        // ③ 桶首不命中，检查后续节点
        else if ((e = p.next) != null) {
            // 桶为红黑树 -> 按树的方式查找节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 桶为链表 -> 逐个遍历查找
            else {
                do {
                    if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e; // 找到待删节点
                        break;
                    }
                    p = e; // 往下走
                } while ((e = e.next) != null);
            }
        }

        // ④ 如果找到节点，并且（不要求匹配 value 或 value 也匹配）
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {

            // ⑤ 桶是树 -> 树节点删除逻辑
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // ⑥ 桶首节点删除
            else if (node == p)
                tab[index] = node.next;
            // ⑦ 链表中间节点删除
            else
                p.next = node.next;

            ++modCount; // 结构修改计数
            --size;     // 元素数量减一
            return node;
        }
    }
    // ⑧ 未找到节点
    return null;
}

1. 定位桶：根据 (n - 1) & hash 找到桶位置。

2. 查找目标节点

   • 桶首节点命中 → 直接删除

   • 否则遍历链表 / 树查找

3. 校验 value

4. 删除节点

   • 树节点 → removeTreeNode

   • 链表节点 → 修改 next 引用

5. 更新 modCount、size

6. 返回被删除的节点

查

get(Object key)

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;

    // ① table 不为空且长度 > 0
    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;
}

1. 直接按 hash 定位桶
2. 桶内查找链表或红黑树

再分配

/**
 * 扩容 & 初始化 table
 * 
 * 扩容场景：
 * 1. table 为空时（首次使用）
 * 2. put 时元素个数超过 threshold
 *
 * 返回：新的 table 数组
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 旧 table 引用
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量
    int oldThr = threshold; // 旧阈值
    int newCap, newThr = 0;  // 新容量、新阈值

    // ① 已初始化过
    if (oldCap > 0) {
        // 已经到最大容量（1 << 30），直接阈值设到 Integer.MAX_VALUE，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 否则容量 × 2（左移一位）
        // 注意：容量是 2 的幂时，扩容只需左移，且保证依然是 2 的幂
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值也翻倍
    }
    // ② 还没分配 table，但 threshold 已经被设置（例如通过构造方法传初始容量）
    else if (oldThr > 0)
        newCap = oldThr;
    // ③ 第一次初始化，设置默认容量和阈值
    else {
        newCap = DEFAULT_INITIAL_CAPACITY; // 默认 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75 = 12
    }

    // 如果新阈值没算出来，这里再算一遍
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 更新阈值

    // 创建新 table
    @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;
                // 如果是红黑树节点，则调用 TreeNode.split 拆分成两个树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 链表迁移
                else {
                    Node<K,V> loHead = null, loTail = null; // 低位链表头尾
                    Node<K,V> hiHead = null, hiTail = null; // 高位链表头尾
                    Node<K,V> next;
                    do {
                        next = e.next;
                        /**
                         * 核心位运算优化：
                         * oldCap 一定是 2 的幂，比如 16（二进制 10000）
                         * e.hash & oldCap 结果只可能是 0 或 oldCap
                         *
                         * - 0：表示扩容后索引不变（低位区）
                         * - oldCap：表示扩容后索引变为原索引 + oldCap（高位区）
                         *
                         * 这种巧妙的分配方式避免了重新计算 hash，只需一次按位与运算
                         */
                        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;
}

1. 为什么容量必须是 2 的倍数

   • 因为 index = hash & (length - 1)，当 length 是 2 的幂时，length - 1 的二进制低位全是 1，这样能充分利用 hash 的低位特征，分布更均匀。

   • 如果不是 2 的幂，按位与运算可能导致某些桶永远用不到，哈希分布不均匀。

2. 位运算的高效性

   • 扩容为两倍时，oldCap 的二进制只有一个 1，多出来的最高位直接决定了元素是否移动到 j + oldCap。

   • 不需要重新计算 hash，也不需要取模运算（% 很慢），性能极高。

3. 低位区 / 高位区迁移

   • (e.hash & oldCap) == 0 → 低位区：索引不变

   • (e.hash & oldCap) != 0 → 高位区：索引变为 原索引 + oldCap

4. 扩容代价

   • 扩容是 O(n) 的操作，因为需要重新分配桶并搬移节点。

   • 因此合理设置初始容量可以减少扩容次数，提高性能。

---

三、常见问题

为什么容量一定是 2 的幂？

• 目的：利用位运算 (n - 1) & hash 快速取模，代替 % 运算，提升性能。
• 如果容量不是 2 的幂，位运算取模会出现分布不均匀的问题，导致哈希冲突增加。
• 额外好处：在扩容时，只需要检查 hash 的某一位（oldCap 位）即可快速判断元素是留在原索引还是移动到 原索引 + oldCap。

为什么扩容时 e.hash & oldCap 结果只可能是 0 或 oldCap？

• 因为 oldCap 是 2 的幂，其二进制只有一个 bit 为 1（如 0001 0000）。
• 按位与运算结果只有两种：
  • 0：该位为 0 → 元素留在低位区（low bin）
  • oldCap：该位为 1 → 元素去高位区（high bin）
• 这让扩容迁移可以 O(1) 决定位置，不必重新计算 hash。

为什么需要同时重写 hashCode() 和 equals()？

• hashCode() 决定元素落在哪个桶（bucket）中。
• equals() 决定同一个桶里的元素是否相等。
• HashMap 在插入时：
  1. 先用 hashCode() 定位桶
  2. 桶内用 equals() 判断是否为同一元素
• 如果只重写一个，可能导致：
  • 两个相等的对象落在不同桶（hashCode 不一致）
  • 两个 hash 相同但 equals 不相等的对象覆盖了彼此（equals 没重写）

HashMap 线程安全问题

• JDK 7：在多线程 resize 时可能出现 死循环（链表形成环）。
• JDK 8+：改为尾插法+红黑树，避免了死循环问题，但依旧非线程安全。
• 多线程场景应使用：
  • Collections.synchronizedMap(new HashMap<>())（全局锁，性能低）
  • ConcurrentHashMap（分段锁/同步粒度更小）

头插法相当于对链表进行倒置 L->1->2->3 在resize时最终会变为L->3->2->1 当3变为首节点时 next指向2, 并发的情况下可能2的next在某一时刻仍然指向3 导致循环链表

JDK 8 为什么引入红黑树？

• 当某个桶中的链表长度超过 8 且容量超过 64 时，链表转为红黑树。
• 红黑树的查找复杂度为 O(log n)，链表查找是 O(n)。
• 这样在高冲突场景下，大幅降低了查询时间。

扩容触发条件

• 当元素数量 size > threshold 时触发扩容：
  • threshold = capacity * loadFactor
  • 默认 capacity = 16，loadFactor = 0.75 → threshold = 12
• 扩容时容量翻倍，threshold 也翻倍。

负载因子（Load Factor）为什么默认 0.75？

• 负载因子越大：
  • 空间利用率高，冲突几率大
• 负载因子越小：
  • 冲突少，空间浪费多
• 0.75 是空间与性能的折中选择。