大家好，我是程序员强子。

又来刷英雄熟练度咯～

今天该轮到一对出场率超高的 黄金搭档 ：HashMap 和 HashSet

今天咱们就钻进练习场，把这对搭档的底层逻辑拆透

Hash

• 数据结构：底层数据结构（JDK8 前后差异）；引入红黑树的原因；链表与红黑树互转条件；红黑树查询复杂度及优势，哈希函数实现及二次处理原因；索引计算方式，key 能否为 null 及存储方式；

• 扩容机制：扩容机制；负载因子作用；初始容量及扩容后容量；JDK7 与 JDK8 扩容元素迁移区别，初始容量需为 2 的幂及不满足的问题

• 线程安全：线程安全性及并发问题

HashSet

• 底层实现：底层依赖的数据结构；与 HashMap 的关系；add () 方法本质及添加成功判断

• 元素特性：保证元素唯一的方式；是否允许 null 元素；有序性；迭代顺序是否固定及原因

那接下来我们开始逐帧拆解 它们的 技能机制 ~

Hash 的数据结构

• JDK7 及以前：数组+链表。

• JDK8 及以后：数组+链表+红黑树。

JDK7 及以前

是数组+链表。

数组是 主货架（长度默认 16），每个格子（索引）下挂着链表，链表用来存 哈希冲突的元素

比如两个 key 计算后落到同一个格子

JDK8 及以后

是数组+链表+红黑树。

为什么加红黑树？

举个例子：如果某个格子的链表长度达到 8，像一串乱麻，查数据时得从头摸到尾（时间复杂度 O (n)）；

换成红黑树后，就像把乱麻按规则分层，查数据时按层级找（时间复杂度 O (logn)）

比如 16 个元素，链表最多查 16 次，红黑树只需 4 次

他们的转换条件是怎么样的？

• 链表转红黑树：链表长度≥8 且 数组容量≥64（避免数组太小就转树，浪费空间）。

• 红黑树转回链表：元素减少到≤6 时（留缓冲，避免频繁转换）

那如何给元素 找格子呢？

第一步：计算元素 hash 值

首先，key 得非空。

如果 key 为空，直接放在数组索引 0 的位置（特殊处理，无需计算 hash）

接着，

给元素（key）分配格子（索引）的过程，就像给快递贴编号 —— 得让编号尽量分散，避免都堆在一个格子里。

先取 key 的 hashCode()（相当于初步编号），再通过 二次处理（高低位异或）让高位参与运算。

比如两个 key 的 hashCode 低位相同但高位不同，二次处理后能分散到不同格子，减少冲突。

第二步：计算 元素应该放哪个格子

公式：(n-1) & hash ,其中 n 是 数组长度，hash 是元素的 hash 值

比如数组长度 16（2 的 4 次方），16-1=15（二进制 1111），和 hash 值做 & 运算，相当于取 hash 值的低 4 位，刚好对应 0-15 的索引。

TIP

(n-1) & hash = hash % n

这个公式的前提：

• HashMap 的数组长度 n 一定是 2 的幂（比如 16、32、64，默认初始容量 16）；

• 处理后的 hash 值 是对 key 的 hashCode 二次处理后的结果（目的是让 hash 值更分散，之前提到过）

为什么必须 n 是 2 的幂 才能这么玩？

• 只有当 n 是 2 的幂时，n-1 的二进制才是 全 1 的形式（比如 n=16→15=1111，n=32→31=11111）。

• 这时候，hash & (n-1) 的结果 完全等价于 hash % n。

如果数组长度不是 2 的次幂，hashmap 如何调整的？

• HashMap 中有一个核心方法 tableSizeFor(int cap)，专门负责把非 2 的幂容量 修正 为 2 的幂。

• 原理很简单：通过位运算把给定容量的 二进制最高位后面的所有位都变成 1，最后加 1，就得到了最小的 2 的幂

• 即 自动 向上取整 到最近的 2 的幂，就像去买货架，想要 10 层的，但货架只有 8、16、32 层的规格，这个时候买 16 层的是最优解

看完就知道，这个公式本质就是在求余

为什么用 & 而不是 %（取余）？

原因很简单：位运算（&）比取余运算（%）效率高得多。

HashMap 作为高频使用的集合，必须追求极致性能，所以用 & 代替 %；

Hash 的扩容机制

当储物架快放满时，就得换个更大的 ~~ HashMap 的 扩容 就是这个逻辑。

触发时机

元素数量 > 数组长度 × 负载因子（默认 0.75）。

比如默认长度 16，16×0.75=12，当元素超过 12 就扩容。

负载因子像 预警线：设 0.5 太保守（频繁扩容浪费空间），设 0.9 太激进（冲突太多），0.75 是平衡选择。

扩容后容量

原容量 ×2（保证还是 2 的幂），比如 16→32→64。

元素迁移

• JDK7 用 头插法：迁移时把链表元素倒序插入新数组，多线程下可能形成 环形链表（查数据时死循环），本质是 ：头插法 + 并发修改导致 指针互指

• JDK8 用尾插法：保持原链表顺序，避免环形问题，且新索引可通过 **原索引 **或 原索引 + 旧容量 快速计算（不用重新 hash）

Hash 的线程安全问题

HashMap 是 单线程专属货架，多线程同时操作会出乱子：

• 并发 put 可能导致数据覆盖（两个线程同时计算到同一个索引，后插入的覆盖前一个）

• JDK7 中并发扩容可能产生环形链表，导致 get 时无限循环

HashSet 的底层实现

依赖关系

HashSet 内部维护一个 HashMap，添加元素时，把元素作为 HashMap 的 key，value 固定为一个静态空对象（new Object()）

add 方法本质

调用 HashMap 的 put(key, 空对象)。

如果返回 null（表示之前没有这个 key），则 add () 返回 true（添加成功）；

如果返回旧 value（表示已有这个 key），则 add () 返回 false（添加失败）

HashSet 的元素特性

如何保证唯一？

和 HashMap 的 key 一样，依赖 hashCode()和 equals()

两个元素 hashCode 相同且 equals 返回 true，就认为是重复元素，无法添加

举例子

往 HashSet 里加两个 new String("a")

因为它们的 hashCode 相同且 equals 为 true，第二次 add 会返回 false

允许 null 元素吗？

允许（因为 HashMap 允许 null key），但只能存 1 个（重复添加会失败）

有序吗？迭代顺序固定吗？

无序

和 HashMap 一样，元素位置由 hash 决定；

迭代顺序不固定，会随元素增删、扩容而变化

比如扩容后元素可能迁移到新索引，顺序就变了

总结

今天这对黄金搭档的熟练度算是刷到位了 ~~

HashMap 的底层结构（JDK8 前后差异、红黑树逻辑）、扩容机制（负载因子、容量迁移）、线程安全坑点，还有 HashSet 的底层依赖关系、元素唯一性原理，全拆得明明白白。

下一场该练集合里的 ConcurrentHashMap 了~ 拆解 JDK7-8 版本迭代、扩容协同、红黑树转换等核心机制~

熟练度刷不停，知识点吃透稳，下期接着练～