---
title: "02-HashMap源码解析"
created: 2025-12-02
tags:
  - Java
---
# HashMap源码解析

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

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

### **一、存储结构**

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

```java
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 时转换为红黑树。

### **三、哈希计算**

1. **计算 key 的 hashCode**：

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

   - 通过异或高位和低位，减少哈希冲突。
2. **确定桶的位置**：

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

### **四、put 方法流程**

源码核心方法 **putVal()**：

```java
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()**：

1. **新容量**：旧容量的 2 倍（保持 2 的幂）。
2. **数据迁移**：

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

### **六、红黑树转换**

1. **树化条件**：

```java
   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 非线程安全，多线程操作可能导致：

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

### **八、性能优化建议**

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

### **源码设计亮点**

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

通过深入源码，可以更好地理解 HashMap 的高效设计与潜在风险，合理使用以优化性能。
---
⬅️ [[01-HashMap|HashMap]] 🏠 [[00-Java|00-Java]] ➡️ [[03-LinkedHashMap|LinkedHashMap]]