HashMap 详细解析

HashMap 是 Java 里最常见的键值对容器。它的底层结构在 JDK 8 之后变成了"数组 + 链表 + 红黑树"的组合，是理解 Java 集合框架的核心之一。

可以把它的核心字段抽象成这样：

Java

        public class HashMap<K, V> {
    transient Node<K, V>[] table;  // 哈希桶数组
    transient int size;            // 当前键值对数量
    int threshold;                 // 扩容阈值
    final float loadFactor;        // 负载因子
}

其中每个桶里放的是链表节点或红黑树节点：

Java

        static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

哈希桶是什么

可以把 table 想象成一排格子，每个格子就是一个"桶"。

当你 put(key, value) 时，HashMap 会：

对 key 求哈希值
根据哈希值找到对应的桶下标
把键值对放到那个桶里

找桶下标的公式大概是：

Java

        int index = hash & (table.length - 1);

这里用位运算代替取模，前提是 table.length 必须是 2 的幂次方，这也是 HashMap 容量始终是 2 的幂次方的原因。

hash() 方法做了什么

HashMap 不是直接用 key.hashCode()，而是做了一步"扰动"：

Java

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

高 16 位与低 16 位做异或，目的是让哈希值的高位也参与到桶下标计算中，减少哈希碰撞。

如果直接用 hashCode()，很多时候高位信息会被 & (n-1) 丢掉，导致碰撞增多。

哈希冲突如何解决

不同的 key 可能映射到同一个桶，这就是哈希冲突。

HashMap 的处理策略是"链地址法"：

同一个桶里的多个元素，用链表串起来
JDK 8 之后，当链表长度超过 8 且数组长度 >= 64 时，链表会转成红黑树

这样做的好处：

链表简单，冲突少时开销低
链表过长时，查询是 O(n)，红黑树能把查询压缩到 O(log n)

红黑树退化回链表的条件是节点数 <= 6。

put 是怎么工作的

map.put(key, value) 的大体流程：

Java

        public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal 内部逻辑大致如下：

如果 table 为空，先扩容初始化
根据 hash 找到桶下标 i = (n-1) & hash
如果桶是空的，直接新建节点放入
如果桶不为空：
- 如果第一个节点的 key 相同，直接覆盖 value
- 如果是红黑树节点，走树的插入逻辑
- 否则遍历链表：找到 key 相同的就覆盖，遍历到末尾没找到就追加
如果追加后链表长度 >= 8，考虑转成红黑树
size 超过 threshold 时触发扩容

get 是怎么工作的

map.get(key) 的大体流程：

Java

        public V get(Object key) {
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode 内部逻辑：

根据 hash 找到桶下标
先检查桶里第一个节点的 key 是否匹配
如果不匹配，再看是红黑树还是链表，分别走对应查找逻辑

所以在哈希分布均匀、没有严重冲突时，get 的时间复杂度接近 O(1)。

默认容量和负载因子

Java

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认初始容量是 16
默认负载因子是 0.75

扩容阈值（threshold）= 容量 × 负载因子。

也就是说，当 size 超过 16 × 0.75 = 12 时，就会触发扩容。

负载因子为什么是 0.75？

这是一个经验值，是时间和空间的权衡：

负载因子太小（比如 0.5）：冲突少，但数组空间浪费多
负载因子太大（比如 1.0）：空间利用率高，但冲突多，性能下降

0.75 综合考虑了这两个因素，是个比较平衡的默认值。

扩容是怎么做的

当 size > threshold 时，触发 resize()。

扩容的核心逻辑：

Java

        // 新容量是原来的 2 倍
int newCap = oldCap << 1;
int newThr = oldThr << 1;

扩容后需要对所有已有节点重新分配桶位置（rehash）。

JDK 8 优化了 rehash 的方式：

Java

        // 节点在新数组的位置只有两种可能：
// 1. 原下标不变
// 2. 原下标 + 旧容量
if ((e.hash & oldCap) == 0) {
    // 放到低位链表（原下标）
} else {
    // 放到高位链表（原下标 + oldCap）
}

这个优化利用了容量是 2 的幂次方的特性，只需要判断 hash 值的一个特定 bit，就能决定节点新位置，不需要重新计算完整的哈希映射。

null key 怎么处理

HashMap 允许 key 为 null，它会被固定放到下标 0 的桶：

Java

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

当 key 为 null 时，hash 返回 0，对应桶下标也是 0。

线程安全问题

HashMap 是线程不安全的。

在多线程并发 put 时，可能出现：

数据覆盖（两个线程同时写同一个桶）
JDK 7 中的环形链表死循环（JDK 8 已修复）

如果需要线程安全的 HashMap，有以下选择：

Collections.synchronizedMap(map)：把所有操作加 synchronized，简单但性能低
ConcurrentHashMap：JDK 8 用 CAS + synchronized 锁细化到桶级别，性能更好

实际开发中，并发场景下推荐直接用 ConcurrentHashMap。

Fonnpo

Spring 核心详解

LinkedList 详细解析

ArrayList 详细解析