HashMap 作为 Java 集合框架中最常用的键值对存储实现，几乎是所有 Java 开发者日常开发的 “标配”。但你真的了解它的底层逻辑吗？为什么 JDK 1.8 要引入红黑树？扩容时的高低位分离有什么优势？本文将从数据结构、核心算法、关键方法到性能优化，全方位拆解 HashMap 的设计精髓。

一、底层数据结构：从 “数组 + 链表” 到 “数组 + 链表 + 红黑树”

HashMap 的性能核心依赖于底层数据结构的设计，JDK 1.7 到 1.8 的演进是其性能跃升的关键。

1.1 JDK 1.7 vs 1.8 核心差异

特性	JDK 1.7	JDK 1.8
底层结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法（易死循环）	尾插法（避免死循环）
扩容链表处理	重新计算 Hash，顺序混乱	高低位分离，保持原有顺序
性能优化	无	链表转红黑树（阈值 8）

1.2 核心结构定义

HashMap 的底层由哈希桶数组、链表节点、红黑树节点三部分组成（JDK 1.8）：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    // 哈希桶数组：核心存储容器
    transient Node<K,V>[] table;
    // 实际元素个数
    transient int size;
    // 扩容阈值 = 容量 × 负载因子（默认 0.75）
    int threshold;
    // 负载因子：平衡空间与时间的核心参数
    final float loadFactor;

    // 链表节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    // Key 的 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;           // 节点颜色（红/黑）
    }
}

1.3 结构可视化

一、整体结构总览（HashMap 核心形态）

+-------------------------- 哈希桶数组 (table) -------------------------+
| 下标0 | 下标1 | 下标2 | 下标3 | 下标4 | 下标5 | ... | 下标15 (默认容量) |
+-------+-------+-------+-------+-------+-------+-----+----------------+
        |               |               |
        |               |               v
        |               |  +----------+    +----------+    +----------+
        |               |  | 链表节点 | -> | 链表节点 | -> | 红黑树头 | -> 红黑树节点...
        |               |  +----------+    +----------+    +----------+
        |               v
        |         +----------+
        |         | 空 (null) |
        |         +----------+
        v
+----------------+
| 红黑树节点 (根) | -> 红黑树子节点...
+----------------+

二、哈希算法：如何精准定位元素？

HashMap 能实现 O (1) 级别的查询，核心依赖哈希值计算和索引定位的高效设计。

2.1 完整 Hash 计算流程

// 1. 计算 Key 的原始 HashCode
int h = key.hashCode();
// 2. 扰动函数：高位参与运算，减少冲突
h = h ^ (h >>> 16);
// 3. 计算数组索引（与运算代替取模，性能更高）
int index = h & (table.length - 1);

2.2 扰动函数的核心作用

JDK 1.8 内置的扰动函数：

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

为什么需要扰动？

• 原始 HashCode 是 32 位整数，数组长度通常较小（如 16），直接取模会导致仅低位参与运算，冲突率极高；

• 扰动函数将 HashCode 的高 16 位与低 16 位异或，让高位特征也参与索引计算，分布更均匀。

扰动效果对比

步骤	无扰动函数	有扰动函数
原始 Hash	1111 1111 0000 0001	1111 1111 0000 0001
数组长度 - 1	0000 1111 1111 1111 (1023)	0000 1111 1111 1111 (1023)
最终索引	0000 0000 0000 0001 (1)	0000 1111 0000 0000 (256)

2.3 哈希冲突示例

某些 Key 的 HashCode 经过扰动后仍会落在同一桶，形成链表：

public class HashCollisionDemo {
    public static void main(String[] args) {
        // "Aa"、"BB"、"C#" 的 HashCode 相同，会触发冲突
        String key1 = "Aa";
        String key2 = "BB";
        String key3 = "C#";
        
        System.out.println("key1 hash: " + hash(key1)); // 2112
        System.out.println("key2 hash: " + hash(key2)); // 2112
        System.out.println("key3 hash: " + hash(key3)); // 2112
    }
    
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

三、核心方法：put () 的完整执行链路

put方法是时序图:

put () 是 HashMap 最复杂的方法，涵盖了初始化、冲突处理、扩容、树化等核心逻辑：

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. 初始化：数组为空则调用 resize() 创建
    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. 桶首节点匹配：直接复用节点（替换值）
        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);
                    // 链表长度≥8，触发树化（需数组容量≥64）
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到相同 Key，跳出循环（后续替换值）
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 6. 替换已有 Key 的值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 7. 修改次数+1（fail-fast 机制）
    ++modCount;
    // 8. 元素数超过阈值，触发扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put () 核心步骤总结

1. 计算 Key 的 Hash 值，定位哈希桶；

2. 桶为空 → 直接插入新节点；

3. 桶非空 → 匹配首节点 / 红黑树 / 链表；

4. 链表长度≥8 → 转红黑树；

5. 元素数超阈值 → 扩容。

四、扩容机制：resize () 的优化设计

扩容时序图:

扩容是 HashMap 性能的关键环节，JDK 1.8 对其做了大幅优化。

4.1 扩容核心逻辑

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. 计算新容量和新阈值
    if (oldCap > 0) {
        // 超过最大容量（2^30），不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量 = 旧容量 × 2（≤ 最大容量）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 新阈值 = 旧阈值 × 2
    }
    // 首次初始化：容量 16，阈值 12（16×0.75）
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 2. 迁移数据：高低位分离（核心优化）
    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;
                // 红黑树节点：拆分树
                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; // 高位（原索引+oldCap）
                    do {
                        Node<K,V> next = e.next;
                        // 核心判断：hash & oldCap == 0 → 低位，否则高位
                        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;
                    }
                    // 高位链表放入新索引（j+oldCap）
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

4.2 高低位分离的优势

• 无需重新计算 Hash：仅通过 hash & oldCap 判断节点归属，效率提升；

• 保持链表顺序：避免 JDK 1.7 头插法导致的死循环；

• 负载更均衡：节点均匀分布在原索引和新索引，减少冲突。

五、性能优化：链表与红黑树的转换

当链表长度超过阈值（8）且数组容量≥64 时，HashMap 会将链表转为红黑树，将查询时间复杂度从 O (n) 降至 O (log n)。

5.1 核心阈值

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 转树最小数组容量（不足则优先扩容）
static final int MIN_TREEIFY_CAPACITY = 64;

5.2 链表转红黑树流程

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 数组容量<64 → 优先扩容而非转树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 1. 将链表节点转为 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);
        // 2. 构建红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

六、读取元素：get () 方法逻辑

get () 方法是 put () 的逆过程，逻辑更简洁：

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;
    // 1. 检查数组和桶是否有效
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 2. 匹配首节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 3. 遍历后续节点
        if ((e = first.next) != null) {
            // 3.1 红黑树：二分查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 3.2 链表：顺序遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

七、性能调优与最佳实践

理解底层原理后，合理使用 HashMap 能大幅提升程序性能。

7.1 合理设置初始容量

预估元素数量，避免频繁扩容（公式：初始容量 = 预估数量 / 负载因子 + 1）：

// 反例：无预估容量，触发多次扩容
Map<String, User> badMap = new HashMap<>();

// 正例：预估容量，减少扩容次数
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75f) + 1;
Map<String, User> goodMap = new HashMap<>(initialCapacity);

7.2 选择合适的负载因子

负载因子	扩容频率	空间利用率	冲突概率	适用场景
0.5	高	低	低	空间充足、追求低冲突
0.75	中	中	中	通用场景（默认）
1.0	低	高	高	空间敏感、查询频率低

7.3 避免使用可变对象作为 Key

Key 的 HashCode 若发生变化，会导致无法找到对应值：

// 反例：可变 Key（有 setter 方法）
class BadKey {
    private String id;
    public void setId(String id) { this.id = id; } // 危险！
    @Override
    public int hashCode() { return id.hashCode(); }
}

// 正例：不可变 Key（final 修饰）
class GoodKey {
    private final String id; // 不可变
    public GoodKey(String id) { this.id = id; }
    @Override
    public int hashCode() { return id.hashCode(); }
}

7.4 线程安全选型

特性	HashMap	Hashtable	ConcurrentHashMap
线程安全	❌ 否	✅ 是（全表锁）	✅ 是（分段锁 / CAS）
null 键 / 值	✅ 支持	❌ 不支持	✅ 支持（JDK 1.8）
性能	高	低	高
推荐场景	单线程	不推荐	多线程

八、核心要点总结

1. 数据结构：JDK 1.8 引入红黑树，解决链表过长导致的查询性能下降问题；

2. 哈希算法：扰动函数让高位参与索引计算，降低冲突率；与运算代替取模，提升性能；

3. 扩容优化：高低位分离避免重新计算 Hash，尾插法解决死循环问题；

4. 性能调优：预估初始容量、选择合适负载因子、使用不可变 Key 是核心最佳实践。

HashMap 的设计充分体现了 “空间换时间” 的思想，理解其底层原理不仅能帮你写出更高效的代码，也能在面试和问题排查中占据优势。希望本文能让你对 HashMap 有更深入的理解！