HashMap底层实现与源码分析

约 1864 字大约 6 分钟

javahashmap

2025-03-02

概述

HashMap 是Java中使用最广泛的Map实现，基于哈希表提供常数时间的 put/get 操作。从 Java 8 开始，其底层数据结构从「数组 + 链表」演进为「数组 + 链表 + 红黑树」，在哈希冲突严重时依然能保持良好性能。

数据结构总览

核心属性

public class HashMap<K,V> extends AbstractMap<K,V> {
    // 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 链表→红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    // 红黑树→链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    // 树化最小表容量（小于64时优先扩容而非树化）
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node<K,V>[] table;     // 桶数组
    transient int size;              // 键值对总数
    int threshold;                   // 扩容阈值 = capacity × loadFactor
    final float loadFactor;          // 负载因子
    transient int modCount;          // 结构修改计数（fail-fast）
}

Node节点结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // 经过扰动函数处理的哈希值
    final K key;
    V value;
    Node<K,V> next;    // 链表后继
}

// 红黑树节点，继承自LinkedHashMap.Entry → Node
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;    // unlink时使用
    boolean red;
}

哈希函数（扰动函数）

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

将高16位与低16位异或，使得高位信息也能参与索引计算，减少哈希碰撞。

桶位计算：index = hash & (table.length - 1)。因为 table.length 始终是2的幂，所以 length - 1 的二进制全为1，与运算等价于取模但效率更高。

put操作流程

源码简析

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;
    // 1. 懒初始化
    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);
        // 5. 链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度达到8
                        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); // LinkedHashMap回调
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // LinkedHashMap回调
    return null;
}

扩容机制（resize）

核心规则：扩容为原来的2倍。对于旧桶中每个节点，只需判断 hash & oldCap 是0还是1：

0：留在原位 index
1：移到新位 index + oldCap

这是 Java 8 的优化，避免了重新计算所有元素的索引。

// resize 中链表拆分的关键逻辑
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);

树化与退化

条件	操作
链表长度 >= 8 且 table.length >= 64	链表 → 红黑树
链表长度 >= 8 且 table.length < 64	扩容（而非树化）
树节点数 <= 6（扩容/删除后）	红黑树 → 链表

为什么阈值是8？ 根据泊松分布，在负载因子0.75下，单个桶中出现8个元素的概率约为 0.00000006，属于极端情况。树化机制是对极端碰撞的防御措施。

Java 7 vs Java 8 对比

特性	Java 7	Java 8
底层结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法	尾插法
哈希函数	4次位运算 + 5次异或	1次位运算 + 1次异或
扩容链表迁移	反转顺序（并发致死循环）	保持顺序
最坏查找	O(n)	O(log n)

线程安全问题

HashMap 不是线程安全的。并发操作可能导致：

数据丢失：两个线程同时 put 到同一个桶位，后者覆盖前者
死循环（Java 7）：头插法扩容时链表成环，get 时无限循环
size 不准确：++size 非原子操作

// 错误：多线程共享HashMap
Map<String, Integer> unsafeMap = new HashMap<>();
// 多线程同时put → 数据不一致

// 正确方案
Map<String, Integer> safeMap = new ConcurrentHashMap<>();
// 或
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());