HashMap解析

HashMap解析

本质上，HashMap 通过一个长度为 2 的次幂的数组 table 维护所有条目，解决哈希冲突采用“数组 + 链表”或“数组 + 红黑树”混合结构。当链表长度超过阈值（TREEIFY_THRESHOLD = 8）且表容量不小于 MIN_TREEIFY_CAPACITY = 64 时，会将该链表转化为红黑树，以确保最坏情况下的查询性能由 O(n) 降至 O(log n)；反之，在扩容时若红黑树节点数低于 UNTREEIFY_THRESHOLD = 6，则会“退化”回链表结构。HashMap 的默认初始容量为 16，默认加载因子为 0.75，**每次扩容都会将容量翻倍**，并更新阈值 threshold = capacity * loadFactor，以保证空间与时间开销的平衡。以上设计使得 HashMap 在大多数应用场景中既能保持常数级别的平均时间复杂度，又能在极端冲突情况下依然提供可接受的性能保证。

底层数据结构

数组与链表 / 红黑树

HashMap 的主体是一个 Node<K,V>[] table 数组，每个 Node 包含 key、value、hash 以及指向下一个节点的 next 引用，用于链表结构的实现
在 JDK 1.8 之前，所有冲突均以链表形式存储；从 JDK 1.8 开始，当某个桶（数组索引）处的链表长度达到 8 且表容量至少为 64 时，该链表会被转换为红黑树节点（TreeNode），查询效率从 O(n) 提升到 O(log n)

哈希计算与索引定位

hash 函数

插入或查找时，HashMap 会先对 key 的原生 hashCode() 值进行扰动（高位与低位异或），以减少低位比特不均匀带来的冲突：

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

此操作将低 16 位的信息扩散到高 16 位，然后通过 index = (n - 1) & hash 定位到数组下标，其中 n 为当前表的长度（始终为 2 的幂）

put 操作流程

  1. 初始化：如果 table == null 或长度为 0，则调用 resize() 初始化为默认容量（16）
  2. 定位桶：计算 key 的扰动哈希并映射到数组下标 i；
  3. 空位直接插入：若 table[i] 为空，直接创建新节点；否则进入冲突处理；
  4. 冲突处理：
    • 若首节点与待插入 key 相同（hash 和 equals 均匹配），直接覆盖旧值；
    • 若当前首节点为红黑树节点，调用 putTreeVal() 在树中插入；
    • 否则遍历链表，若遍历中发现已有匹配节点则覆盖并退出；若遍历完毕还没有匹配节点则添加到最后面，添加完毕后，判断链表长度 + 1 ≥ 8 且数组长度 ≥ 64，则调用 treeifyBin() 将链表树化；否则，就是只是对数组扩容
  1. 检查并触发扩容：插入后若总节点数超过 threshold，调用 resize() 扩容（容量翻倍，重新分配、迁移所有节点）

get 操作流程

  1. 空表或空桶：若 table == null 或对应桶 table[i] 为空，直接返回 null；
  2. 定位节点：若首节点匹配，立即返回；否则：
    • 若该桶为红黑树节点，调用 getTreeNode() 在树中查找；
    • 否则遍历链表，依次比较 hash 与 equals，直到找到或链表末尾返回 null

扩容（resize()）

  • 触发时机：首次初始化和每次插入后节点数超过阈值时；
  • 核心逻辑：新容量 = 旧容量 × 2；新阈值 = 新容量 × 加载因子；分配新数组后，遍历旧表中所有节点并根据新哈希高位对它们进行“低位不变 / 高位索引偏移”双路分配，以减少全部重新哈希的开销（“高位”拆分优化）
  • 红黑树退化：在迁移过程中，若某棵树节点数低于 UNTREEIFY_THRESHOLD = 6，则再将树转换为链表节点，以减少树结构的过度维护成本

树化与退化阈值

  • TREEIFY_THRESHOLD = 8（链表 → 红黑树）
  • UNTREEIFY_THRESHOLD = 6（红黑树 → 链表）
  • MIN_TREEIFY_CAPACITY = 64（触发树化的最小表容量）
    这些常量保证了树化仅在真正有必要时发生，同时在扩容后又可避免树化带来的额外平衡维护开销

性能与特性

  • 平均时间复杂度：插入、查询、删除均为 O(1)；在极端冲突（链表）情况下最坏 O(n)，但树化后最坏 O(log n)
  • 空间开销：维护链表与红黑树节点会带来不同内存开销；红黑树节点需额外维护父、左右子指针与颜色标志。
  • 线程安全：非线程安全，多线程写入可能导致死循环或数据丢失；推荐使用 ConcurrentHashMap 或外部加锁来替代