跳到主要内容

HashMap 源码解析

问题​

HashMap 的底层数据结构是什么？put 流程是怎样的？扩容机制是怎样的？JDK 7 和 JDK 8 有什么区别？

答案​

底层数据结构​

JDK 8 的 HashMap 采用 数组 + 链表 + 红黑树：

结构条件时间复杂度
数组默认存储位置O(1)O(1)
链表哈希冲突，节点数 ≤ 8O(n)O(n)
红黑树链表长度 > 8 且数组长度 ≥ 64O(log⁡n)O(\log n)

核心参数​

HashMap 关键参数
static final int DEFAULT_INITIAL_CAPACITY = 16;    // 默认初始容量（必须是 2 的幂）
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;        // 树化的最小数组容量
static final int MAXIMUM_CAPACITY = 1 << 30;       // 最大容量
为什么负载因子是 0.75？

这是时间和空间的折中：

  • 太大（如 1.0）：空间利用率高，但碰撞增多，查找变慢
  • 太小（如 0.5）：碰撞少，但浪费空间，频繁扩容
  • 0.75 在泊松分布下，链表长度达到 8 的概率约为千万分之六，是统计上的最优平衡

hash 扰动函数​

HashMap.hash()（JDK 8）
static final int hash(Object key) {
    int h;
    // 将高 16 位与低 16 位异或，让高位参与定位
    // 减少只有低位不同时的碰撞
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 定位数组下标（取模运算优化为位运算）
// index = hash & (capacity - 1)
// 等价于 hash % capacity（capacity 是 2 的幂时）

put 流程​

HashMap.put() 简化流程
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

扩容机制（resize）​

扩容时容量翻倍（newCap = oldCap << 1），每个节点重新计算位置：

扩容时的位置分配（JDK 8 优化）
// JDK 8 的优化：不需要重新计算 hash
// 扩容后，每个节点要么在原位置，要么在「原位置 + oldCap」
// 判断依据：hash & oldCap 是 0 还是 1

// 例：oldCap = 16（10000），扩容后 newCap = 32（100000）
// hash = 17 (10001):  17 & 16 = 10000 ≠ 0 → 移到 index + 16
// hash = 1  (00001):   1 & 16 = 00000 = 0 → 留在原位置

JDK 7 vs JDK 8​

维度JDK 7JDK 8
数据结构数组 + 链表数组 + 链表 + 红黑树
插入方式头插法尾插法
扩容死循环多线程下可能出现尾插法解决了此问题
hash 扰动4 次位运算 + 5 次异或1 次位运算 + 1 次异或
扩容位置计算重新 hashhash & oldCap 判断
JDK 7 的并发死循环

JDK 7 使用头插法，多线程扩容时可能导致链表出现环，后续 get() 操作会陷入死循环。虽然 JDK 8 用尾插法解决了死循环问题，但 HashMap 仍然不是线程安全的，多线程环境必须使用 ConcurrentHashMap。

常见面试问题​

Q1: HashMap 允许 null key 和 null value 吗？​

答案：

允许一个 null key 和多个 null value。null key 的 hash 值固定为 0，存储在数组的第 0 个位置。ConcurrentHashMap 不允许 null key 和 null value。

Q2: 为什么容量必须是 2 的幂？​

答案：

  1. 位运算取模：hash & (capacity - 1) 等价于 hash % capacity，位运算更快
  2. 均匀分布：2 的幂减 1 后所有位都是 1（如 15 = 01111），与 hash 做 & 运算能利用 hash 的所有低位，分布更均匀
  3. 扩容优化：扩容时只需判断 hash & oldCap 新增的那一位是 0 还是 1

Q3: 链表什么时候转红黑树？红黑树什么时候退化？​

答案：

  • 链表 → 红黑树：链表长度大于 TREEIFY_THRESHOLD（8）且数组长度大于等于 MIN_TREEIFY_CAPACITY（64）。如果数组太小，优先扩容而非树化
  • 红黑树 → 链表：扩容时红黑树节点数小于等于 UNTREEIFY_THRESHOLD（6）

为什么是 8？泊松分布下，桶中 8 个元素的概率约为 0.00000006，几乎不会发生。设为 8 是为了避免频繁在链表和红黑树之间转换。

Q4: HashMap 线程不安全体现在哪些方面？​

答案：

  1. 数据覆盖：两个线程同时 put，hash 到同一个桶，可能一个线程的数据被覆盖
  2. size 不准确：size++ 非原子操作
  3. 死循环（仅 JDK 7）：多线程扩容时头插法导致链表成环
  4. 数据丢失：扩容时并发操作可能丢失节点

Q5: HashMap 的 key 需要满足什么条件？​

答案：

  1. 必须正确重写 equals() 和 hashCode()，且保持一致（equals 相等则 hashCode 必须相等）
  2. 最好是不可变对象（如 String、Integer），否则对象状态改变会导致 hashCode 变化，无法正确查找
  3. 允许为 null（只能有一个 null key）

Q6: 为什么 String 适合作为 HashMap 的 key？​

答案：

  1. 不可变：hashCode 不会变化，保证能正确查找
  2. hashCode 缓存：String 内部缓存了 hashCode，不需要每次重新计算
  3. equals 已正确重写：按字符内容比较
  4. 广泛使用：开发者对其行为非常熟悉

Q7: HashMap 和 Hashtable 的区别？​

答案：

维度HashMapHashtable
线程安全不安全安全（全表 synchronized）
null 支持允许 null key/value不允许 null key/value
性能更快较慢
继承关系AbstractMapDictionary（已废弃）
迭代器fail-fastfail-fast
推荐替代—ConcurrentHashMap

Hashtable 现在不推荐使用，线程安全场景用 ConcurrentHashMap。

相关链接​