`HashMap` 哈希表源码

概述

HashMap 是 Java 中使用最广泛的哈希表实现，基于数组 + 链表 + 红黑树（JDK 8+）实现。它通过键的 hashCode() 计算存储位置，并提供 O(1) 的平均查找性能。

HashMap 支持 null 键和 null 值，不保证元素顺序，非线程安全。在 JDK 8+ 中引入了红黑树优化，当链表长度超过阈值时自动转换为红黑树，将最坏情况时间复杂度从 O(n) 优化到 O(log n)。

本文基于 OpenJDK 21 源码，从内部数据结构开始，逐层深入到哈希计算、插入、扩容、树化、查找等核心机制。

本文基于 OpenJDK 21 源码分析，关键实现会对比 JDK 7 到 JDK 21 的版本差异。

核心源码解析

① `HashMap` 内部结构

java

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

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node<K,V>[] table;
    transient int size;
    int threshold;
    final float loadFactor;
}

核心数据结构：

Node<K,V>[] table — 哈希桶数组
Node<K,V> — 链表节点
TreeNode<K,V> — 红黑树节点（继承自 LinkedHashMap.Entry）

Node 定义：

java

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

② `hash(Object)` 的扰动函数

java

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

h >>> 16 将高 16 位右移到低 16 位
h ^ (h >>> 16) 异或操作，将高位信息混入低位
目的是在 (n-1) & hash 定位时，让高位也参与索引计算，降低碰撞概率
null 键的 hash 值固定为 0，即 HashMap 允许 null 作为键

JDK 7 中使用了更复杂的 4 次扰动（hash() → indexFor()），JDK 8+ 简化为 1 次异或，性能更好且足够有效。

③ `put(K, V)` 的 `putVal()` 流程

java

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;
    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;
        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); // 尾插（JDK 7 头插）
                    if (binCount >= TREEIFY_THRESHOLD - 1)    // ≥7 即链表长度 8
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

完整流程：

table 为空 → resize() 懒加载初始化
(n-1) & hash 定位桶，空桶直接插入
非空 → 判断键是否相同（hash + == / equals()）
不同 → 红黑树则 putTreeVal()，链表则尾插遍历
链表长度 ≥ 8 → treeifyBin() 尝试树化（还需容量 ≥ 64）
键已存在 → 替换值
插入后 size > threshold → resize() 扩容

④ `resize()` 的 2 倍扩容

java

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;
        }
        newCap = oldCap << 1;        // 2 倍扩容
        newThr = oldThr << 1;        // 阈值翻倍
    } else if (oldThr > 0)
        newCap = oldThr;             // 指定初始容量
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // ... 创建新数组
    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;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e; // 单节点直接 rehash
                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;
                        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;
                        }
                        e = next;
                    } while (e != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

核心优化：不需要重新计算 hash，只需要看 (e.hash & oldCap) == 0：

== 0 → 低位链，索引不变
!= 0 → 高位链，索引 = 原索引 + oldCap

⑤ 红黑树的转换条件

java

static final int TREEIFY_THRESHOLD = 8;    // 链表 → 红黑树
static final int UNTREEIFY_THRESHOLD = 6;  // 红黑树 → 链表
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量

treeifyBin() 方法：

java

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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);
        tab[index] = hd.treeify(tab);  // 树化
    }
}

⑥ `MIN_TREEIFY_CAPACITY = 64`

当 table.length < 64 时，即使链表 ≥ 8 也不树化，而是优先 resize() 扩容
扩容后链表节点会分散到两个桶中，自然缩短链表长度
避免在容量很小时创建红黑树，减少维护开销

⑦ 负载因子 `DEFAULT_LOAD_FACTOR = 0.75f`

java

public HashMap(int initialCapacity, float loadFactor) {
    // ...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

扩容阈值 threshold = capacity * loadFactor
0.75f 是时间和空间成本的权衡：太高（如 1）碰撞概率大，太低（如 0.5）浪费空间
首次使用 tableSizeFor() 初始化阈值，首次 put 后 resize() 重新计算

⑧ `tableSizeFor(int)` 的 5 次移位

java

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    // 等同于以下展开：
    // int n = cap - 1;
    // n |= n >>> 1;
    // n |= n >>> 2;
    // n |= n >>> 4;
    // n |= n >>> 8;
    // n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

返回 ≥ cap 的最小 2 的幂（如 cap=13 → n=15 → n+1=16）。

⑨ `get(Object)` 的 `getNode()`

java

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

final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != 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;
}

⑩ `keySet()` / `values()` / `entrySet()` 的视图

java

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

KeySet / EntrySet / Values 都是内部视图类
迭代器使用统一的 HashIterator 遍历
视图上的修改（如 Set.remove()）直接映射到 HashMap

总结

HashMap 是 Java 中最精妙的集合实现之一，其设计在时间和空间复杂度之间取得了优秀的平衡：

O(1) 平均查找：通过 hashCode() + 扰动函数 + 桶数组
自动扩容：懒加载初始化 + 2 倍扩容 + 高低位链表拆分
红黑树优化：链表 ≥ 8 且容量 ≥ 64 时树化，最坏情况 O(log n)
null 支持：hash(null) = 0，null 键存储在桶 0
Fail-Fast 迭代器：modCount 并发修改检测

HashMap 哈希表源码 ​

概述 ​

核心源码解析 ​

① HashMap 内部结构 ​

② hash(Object) 的扰动函数 ​

③ put(K, V) 的 putVal() 流程 ​

④ resize() 的 2 倍扩容 ​

⑤ 红黑树的转换条件 ​

⑥ MIN_TREEIFY_CAPACITY = 64 ​

⑦ 负载因子 DEFAULT_LOAD_FACTOR = 0.75f ​

⑧ tableSizeFor(int) 的 5 次移位 ​

⑨ get(Object) 的 getNode() ​

⑩ keySet() / values() / entrySet() 的视图 ​

总结 ​

`HashMap` 哈希表源码

概述

核心源码解析

① `HashMap` 内部结构

② `hash(Object)` 的扰动函数

③ `put(K, V)` 的 `putVal()` 流程

④ `resize()` 的 2 倍扩容

⑤ 红黑树的转换条件

⑥ `MIN_TREEIFY_CAPACITY = 64`

⑦ 负载因子 `DEFAULT_LOAD_FACTOR = 0.75f`

⑧ `tableSizeFor(int)` 的 5 次移位

⑨ `get(Object)` 的 `getNode()`

⑩ `keySet()` / `values()` / `entrySet()` 的视图

总结