HashMap 底层原理详解

HashMap 是 Java 中最常用的键值对存储容器，JDK 1.8 采用数组 + 链表 + 红黑树的混合结构。

一、核心结构解析

1.1 数据结构

JDK 1.8 及之后采用数组 + 链表 + 红黑树的混合实现：

HashMap
└── Node[] table (数组)
    ├── Node → Node → Node (链表)
    └── TreeNode → TreeNode (红黑树)

1.2 关键参数

// 默认初始容量（必须是 2 的幂次）
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;

二、关键机制

2.1 哈希值计算

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

二次哈希：将高 16 位与低 16 位异或，增强哈希值的随机性，减少冲突。

索引计算：

index = (n - 1) & hash  // 等价于 hash % n，但更快

2.2 扩容机制（resize）

当 size > 负载因子 × 容量 时触发扩容：

// 1. 新容量 = 旧容量 × 2
newCap = oldCap << 1;

// 2. 重新计算索引（JDK 1.8 优化）
// 高位 = (e.hash & oldCap) == 0 ? 原位置 : 原位置 + oldCap
if ((e.hash & oldCap) == 0)
    newTab[j] = e;
else
    newTab[j + oldCap] = e;

优化：无需重新计算哈希，通过hash & oldCap判断元素在新数组的位置。

2.3 put 操作流程

public V put(K key, V value) {
    // 1. 计算哈希值
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    
    // 2. 遍历链表/红黑树
    for (Node<K,V> e = table[i]; e != null; e = e.next) {
        // 3. 键已存在，更新值
        if (e.hash == hash && key.equals(e.key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    
    // 4. 插入新节点（尾插法）
    addNode(hash, key, value, i);
    
    // 5. 检查是否需要扩容
    if (++size > threshold)
        resize();
    
    return null;
}

三、JDK 1.7 vs 1.8 核心区别

3.1 头插法 vs 尾插法

JDK 1.7 头插法问题：

扩容时多线程可能导致链表成环 → 死循环
A → B → C  扩容后变成  B → A → C

JDK 1.8 尾插法：保持原有顺序，避免成环。

四、常见面试题

4.1 为什么容量是 2 的幂次？

// 2 的幂次：(n-1) & hash 等价于 hash % n
// 例如：15 & hash = hash % 16

// 非 2 的幂次：分布不均匀，冲突增加

4.2 负载因子为什么是 0.75？

• 太大：冲突增加，查询性能下降
• 太小：空间浪费，频繁扩容
• 0.75：时空权衡的最佳选择

4.3 如何线程安全？

// 方案 1：Collections.synchronizedMap
Map<String, Object> map = Collections.synchronizedMap(new HashMap<>());

// 方案 2：ConcurrentHashMap（推荐）
Map<String, Object> map = new ConcurrentHashMap<>();

// 方案 3：Hashtable（不推荐，性能差）
Map<String, Object> map = new Hashtable<>();

五、最佳实践

5.1 初始化容量设置

// 已知需要存储 100 个元素
// 容量 = 100 / 0.75 + 1 = 135，向上取 2 的幂次 = 256
Map<String, Object> map = new HashMap<>(256);

5.2 Key 的选择

// ✅ 推荐：不可变类（String、Integer）
Map<String, Object> map = new HashMap<>();

// ❌ 避免：可变对象作为 Key
class MutableKey {
    int value; // 可变字段
}

5.3 遍历方式

// ✅ 推荐：entrySet 遍历
for (Map.Entry<K, V> entry : map.entrySet()) {
    K key = entry.getKey();
    V value = entry.getValue();
}

// ❌ 不推荐：keySet 遍历（多一次查找）
for (K key : map.keySet()) {
    V value = map.get(key);
}

六、总结

HashMap 核心要点：

1. 数据结构：数组 + 链表 + 红黑树
2. 扩容机制：容量翻倍，高低位拆分
3. 哈希计算：二次哈希，减少冲突
4. 版本差异：JDK 1.8 尾插法避免死循环
5. 使用注意：初始容量、Key 选择、遍历方式

HashMap 适用于单线程、无需排序的场景，多线程请用ConcurrentHashMap。