文章目录
一、前言二、HashSet 的核心特性1. 元素唯一性2. 无序性3. 高效操作4. 允许 null 元素5. 非线程安全
三、HashSet 的底层实现原理1. 数据结构演进：JDK 7 vs JDK 8JDK 7：数组 + 链表JDK 8：数组 + 链表 + 红黑树
2. 核心数据结构：基于 HashMap3. 添加元素的流程详解4. 扩容机制示例代码
四、版本差异对比五、性能优化建议1. 选择合适的数据结构2. 控制初始容量和负载因子示例：
3. 避免 null 元素4. 多线程环境下的处理5. 遍历效率示例：
六、典型应用场景1. 去重操作示例：
2. 快速查找示例：
3. 集合运算示例：
4. 结合 Stream API示例：
七、自定义对象的注意事项1. 重写 `hashCode()` 和 `equals()`示例代码：
2. 哈希冲突的模拟示例代码：
八、常见问题与解决方案1. JDK 7 多线程扩容导致的死循环死循环示意图
2. 性能调优建议
九、总结十、常见问题解答1. HashSet底层链表是单链表还是双链表？有什么优点和缺点？2. 为什么 JDK 8 引入红黑树？红黑树相比链表有什么优势？3. 为什么 HashSet 不保证元素顺序？4. 如何避免 HashSet 中的哈希冲突？5. HashSet 是线程安全的吗？如何解决并发问题？6. 自定义对象未重写 `hashCode()` 和 `equals()` 会有什么后果？7. 为什么默认容量是 16？8. 为什么负载因子设置为 0.75？9. 为什么扩容时新数组容量是两倍？10. 如何避免扩容时的性能问题？
十一、哈希表存储数据的详细流程1. 初始化哈希表2. 添加元素流程步骤 1：计算哈希值步骤 2：确定数组索引步骤 3：处理哈希冲突步骤 4：检查元素唯一性
3. 扩容机制详解触发条件扩容步骤示例流程
4. 树化与链表化的动态平衡
一、前言
HashSet 是 Java 集合框架中最常用的数据结构之一，它基于 哈希表 实现，具有 元素唯一性 和 无序性 的特点。作为 Set 接口的典型实现类，HashSet 在去重、快速查找等场景中表现卓越。
二、HashSet 的核心特性
1. 元素唯一性
实现原理：通过 hashCode() 和 equals() 方法判断元素是否重复。关键规则：
若两个对象的 hashCode 相等且 equals 返回 true，则视为重复元素。自定义对象必须重写 hashCode() 和 equals() 方法，否则可能导致去重失败。
2. 无序性
存储顺序：元素在集合中的存储顺序与插入顺序无关。遍历顺序：遍历时返回的顺序是不确定的，可能与哈希值分布相关。
3. 高效操作
时间复杂度：
插入、删除、查找操作的平均时间复杂度为 O(1)。哈希冲突严重时，退化为 O(log n)（红黑树）或 O(n)（链表）。 空间复杂度：取决于初始容量和负载因子。
4. 允许 null 元素
唯一性：HashSet 允许存储一个 null 元素。限制性：TreeSet 不允许 null 元素。
5. 非线程安全
并发问题：HashSet 本身不是线程安全的。解决方案：使用 Collections.synchronizedSet() 或并发集合类（如 ConcurrentHashMap.newKeySet()）。
三、HashSet 的底层实现原理
1. 数据结构演进：JDK 7 vs JDK 8
JDK 7：数组 + 链表
哈希冲突处理：采用 链地址法（Chaining），每个数组位置存储一个链表。链表插入方式：头插法（Head Insertion），新节点插入到链表头部。问题：多线程扩容时可能导致链表成环，引发死循环。
JDK 8：数组 + 链表 + 红黑树
哈希冲突处理：引入 红黑树（Red-Black Tree），当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转换为红黑树。链表插入方式：尾插法（Tail Insertion），新节点插入到链表尾部，避免头插法导致的死循环。优势：红黑树将最坏时间复杂度从 O(n) 降至 O(log n)。
2. 核心数据结构：基于 HashMap
HashSet 的底层实现依赖于 HashMap，具体如下：
内部结构：HashSet 内部维护一个 HashMap
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 将元素作为 Key 存入 HashMap
}
3. 添加元素的流程详解
计算哈希值：
调用元素的 hashCode() 方法获取哈希值。通过 (n - 1) & hash 计算数组索引（n 为当前数组长度）。 处理哈希冲突：
JDK 7：采用链表解决冲突，新节点插入到链表头部。JDK 8：采用链表或红黑树解决冲突，链表插入到尾部，红黑树进行树化操作。 判断重复性：
若新元素与桶中已有元素的 hashCode 和 equals 均匹配，则视为重复元素，添加失败。 树化与链表化（JDK 8）：
树化条件：链表长度 ≥ 8 且数组长度 ≥ 64。链表化条件：红黑树节点数 ≤ 6。目的：在高冲突场景下通过红黑树降低查找时间。
4. 扩容机制
触发条件：当元素数量超过阈值（threshold = capacity * loadFactor）时，触发扩容。扩容过程：
创建一个容量为原数组两倍的新数组。重新计算所有元素的哈希值，并分布到新数组中。更新 threshold 为 newCapacity * loadFactor。 默认负载因子：0.75，平衡空间利用率和哈希冲突的概率。
示例代码
final Node
Node
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int newCap = oldCap << 1;
int newThr = (int)(oldCap * loadFactor);
Node
transfer(newTab);
return newTab;
}
四、版本差异对比
特性JDK 7JDK 8哈希冲突处理链地址法（链表）链地址法 + 红黑树链表插入方式头插法尾插法扩容时的链表处理头插法可能导致死循环尾插法避免死循环树化条件不支持链表长度 ≥ 8 且数组长度 ≥ 64查找性能最坏 O(n)最坏 O(log n)多线程安全性多线程扩容可能死锁多线程扩容更安全（尾插法避免死锁）
五、性能优化建议
1. 选择合适的数据结构
高频插入/查询：使用 HashSet（O(1) 时间复杂度）。需要有序性：使用 TreeSet（O(log n) 时间复杂度，按自然顺序或自定义顺序排序）。需要保持插入顺序：使用 LinkedHashSet（O(1) 时间复杂度，维护链表记录插入顺序）。
2. 控制初始容量和负载因子
初始容量：预估元素数量，设置合适的初始容量以减少扩容次数。负载因子：默认为 0.75，若哈希冲突较多，可适当降低负载因子。
示例：
Set
3. 避免 null 元素
HashSet 允许一个 null 元素，但过多的 null 可能导致性能问题或逻辑错误。
4. 多线程环境下的处理
使用 Collections.synchronizedSet(new HashSet<>()) 或 ConcurrentHashMap.newKeySet() 实现线程安全。
5. 遍历效率
使用 Iterator 遍历集合，避免在遍历过程中修改集合（否则可能抛出 ConcurrentModificationException）。
示例：
Set
set.add("A");
set.add("B");
for (Iterator
String item = it.next();
if (item.equals("B")) {
it.remove(); // 安全删除
}
}
六、典型应用场景
1. 去重操作
日志去重：过滤重复的日志条目。用户 ID 去重：确保用户 ID 的唯一性。
示例：
Set
logs.forEach(log -> uniqueLogs.add(parseLog(log)));
2. 快速查找
屏蔽词过滤：判断某个词是否在黑名单中。缓存系统：快速判断元素是否已缓存。
示例：
Set
void addToCache(String key) {
if (cache.size() >= MAX_ENTRIES) {
evictLRU(); // 需自行实现 LRU 策略
}
cache.add(key);
}
3. 集合运算
交集、并集、差集：通过 retainAll()、addAll()、removeAll() 实现。
示例：
Set
Set
Set
intersection.retainAll(set2); // 交集: [2, 3]
4. 结合 Stream API
利用 Java 8+ 的 Stream API 简化集合操作。
示例：
Set
.filter(s -> s.startsWith("A"))
.collect(Collectors.toSet());
七、自定义对象的注意事项
1. 重写 hashCode() 和 equals()
HashSet 依赖哈希值和 equals() 判断元素唯一性。若自定义对象未重写这两个方法，可能导致去重失败。
示例代码：
public class Person {
private String name;
private int age;
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person person = (Person) obj;
return age == person.age && name.equals(person.name);
}
}
2. 哈希冲突的模拟
假设两个对象的 hashCode() 返回相同值，但 equals() 返回 false，此时它们会被视为不同元素。
示例代码：
Set
Person p1 = new Person("Alice", 25);
Person p2 = new Person("Bob", 25); // 与 p1 的 age 相同，name 不同
set.add(p1);
set.add(p2);
System.out.println(set.size()); // 输出 2
八、常见问题与解决方案
1. JDK 7 多线程扩容导致的死循环
原因：头插法在并发扩容时可能导致链表成环。解决方案：使用 Collections.synchronizedSet() 或并发集合类（如 ConcurrentHashMap.newKeySet()）。
死循环示意图
初始链表：A → B → C
扩容后（头插法）：C → B → A
若并发操作导致链表成环：A → B → C → B → ...
2. 性能调优建议
预估容量：设置合理的初始容量和负载因子，减少扩容次数。避免过度树化：若数据量较小，链表性能可能优于红黑树。合理选择集合类型：需要有序性时使用 TreeSet，需要插入顺序时使用 LinkedHashSet。
九、总结
HashSet 作为 Java 集合框架的核心组件，其性能优化经历了从 链地址法 到 红黑树 的演进。JDK 8 通过引入红黑树显著提升了高冲突场景下的查找效率，同时尾插法解决了多线程扩容的死循环问题。开发者需注意以下几点：
正确重写 hashCode() 和 equals()，确保自定义对象的唯一性判断。理解树化与链表化的条件，避免性能陷阱。选择合适的集合类型，如需有序性使用 TreeSet，需保持插入顺序使用 LinkedHashSet。
十、常见问题解答
1. HashSet底层链表是单链表还是双链表？有什么优点和缺点？
答案： HashSet 底层的链表是 单链表（Singly Linked List），而非双链表。
单链表的特点：每个节点仅存储下一个节点的引用，没有前驱指针。优点：
内存占用小：单链表仅需存储一个指针，内存开销更小。插入效率高：在链表头部或尾部插入新节点时，操作复杂度为 O(1)。适合哈希冲突场景：哈希冲突通常发生在同一桶中，单链表足够满足冲突解决需求。 缺点：
查找效率低：最坏情况下需遍历整个链表（O(n)）。无法双向遍历：若需逆向查找，需额外维护指针或使用其他数据结构。 JDK 8 的优化： 当链表长度超过阈值（默认 8）且数组长度 ≥ 64 时，链表会转换为 红黑树（Red-Black Tree），将最坏时间复杂度从 O(n) 降至 O(log n)，显著提升高冲突场景下的性能。
2. 为什么 JDK 8 引入红黑树？红黑树相比链表有什么优势？
背景： 在哈希冲突严重时（如大量元素映射到同一桶），链表性能退化为 O(n)，影响整体效率。
JDK 7 的问题：链表查找效率低，且头插法在多线程扩容时可能引发死循环。JDK 8 的改进：引入红黑树，通过自平衡二叉搜索树特性，将查找复杂度降至 O(log n)。 红黑树的优势：
查找效率更高：红黑树的查找、插入、删除操作均为 O(log n)。自平衡特性：通过旋转和颜色调整保持树的平衡，避免链表的极端性能问题。适应高冲突场景：当哈希分布不均时，红黑树能有效缓解性能瓶颈。 树化的触发条件：
链表长度 ≥ 8（TREEIFY_THRESHOLD）。数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）。若数组长度 < 64，则优先扩容而非树化。
3. 为什么 HashSet 不保证元素顺序？
原因： HashSet 基于哈希表实现，元素存储位置由哈希值决定，而非插入顺序。
哈希值计算：int index = (n - 1) & hash，其中 n 为数组长度，hash 为元素的哈希值。无序性表现：
插入顺序与遍历顺序无关。哈希冲突可能导致元素分布在不同桶中，进一步打乱顺序。 对比有序集合：
TreeSet：基于红黑树，按自然顺序或自定义比较器排序。LinkedHashSet：维护插入顺序，通过双向链表记录元素顺序。
4. 如何避免 HashSet 中的哈希冲突？
哈希冲突的本质： 不同对象的哈希值可能相同，或映射到同一数组索引。
解决方案：
重写 hashCode() 和 equals()：
确保对象的哈希值能准确反映其内容。例如：Person 类根据 name 和 age 计算哈希值。 使用高质量哈希函数：
Java 内置的 Objects.hash() 方法可生成均匀分布的哈希值。 调整负载因子：
降低负载因子（如 0.5）可减少冲突概率，但增加内存开销。
5. HashSet 是线程安全的吗？如何解决并发问题？
线程安全性问题： HashSet 非线程安全，多线程并发操作可能导致数据不一致或死循环（如 JDK 7 的头插法扩容）。
解决方案：
使用线程安全集合：
ConcurrentHashMap.newKeySet()：基于 ConcurrentHashMap 实现的线程安全 Set。 手动同步：
使用 Collections.synchronizedSet(new HashSet<>()) 包装集合。 避免并发修改：
遍历时禁止修改集合，或使用迭代器的 remove() 方法。
6. 自定义对象未重写 hashCode() 和 equals() 会有什么后果？
后果：
去重失败：
若未重写 hashCode()，默认使用对象地址值，即使内容相同，哈希值不同导致元素被重复存储。 哈希冲突加剧：
默认 hashCode() 的分布不均，导致冲突概率增加。 示例：
class Person {
String name;
int age;
}
Set
set.add(new Person("Alice", 25));
set.add(new Person("Alice", 25)); // 会被视为不同元素，set.size() = 2
7. 为什么默认容量是 16？
设计考量：
16 是 2 的幂次，便于通过位运算（&）快速计算索引。初始容量过小会导致频繁扩容，过大会浪费内存。
8. 为什么负载因子设置为 0.75？
平衡点：
0.75 是时间和空间的折中：
高负载因子（如 0.8）：减少扩容次数，但增加哈希冲突概率。低负载因子（如 0.5）：降低冲突概率，但浪费内存。
9. 为什么扩容时新数组容量是两倍？
幂次扩展策略：
保持数组容量始终为 2 的幂次，便于位运算计算索引。优势：
扩容后，元素可能分布在原索引或 原索引 + 原容量，避免重新计算所有哈希值。
10. 如何避免扩容时的性能问题？
预分配容量：
若预知元素数量，可通过构造函数指定初始容量，减少扩容次数。示例：Set
十一、哈希表存储数据的详细流程
1. 初始化哈希表
默认容量： HashSet 底层基于 HashMap 实现，默认初始容量为 16（HashMap 的默认初始容量）。
代码示例：Set
负载因子： 默认负载因子为 0.75，表示当元素数量超过 容量 * 负载因子 时触发扩容。
阈值计算：threshold = capacity * loadFactor = 16 * 0.75 = 12
2. 添加元素流程
步骤 1：计算哈希值
哈希值计算： 调用元素的 hashCode() 方法获取哈希码，并通过 HashMap 的 hash() 方法进一步扰动。
扰动函数（JDK 8）：static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
目的：减少高位哈希冲突，提升分布均匀性。
步骤 2：确定数组索引
索引计算公式：int index = (n - 1) & hash;
n 为当前数组长度（初始为 16）。& 运算等价于取模运算（hash % n），但效率更高。示例： 若 hash = 20，n = 16，则 index = 20 & 15 = 4。
步骤 3：处理哈希冲突
链地址法（JDK 7 及以前）：
若当前桶已存在元素，则将新元素插入链表头部（头插法）。问题：多线程扩容时可能导致链表成环（死循环）。 红黑树（JDK 8 及以后）：
当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转换为红黑树。树化过程：
遍历链表，将每个节点转换为 TreeNode。调用 treeify() 方法构建红黑树。
步骤 4：检查元素唯一性
比较逻辑：
比较新元素与桶中已有元素的哈希值。若哈希值相同，调用 equals() 方法判断内容是否相等。若 equals() 返回 true，则视为重复元素，不添加；否则，添加到链表或红黑树中。
3. 扩容机制详解
触发条件
阈值计算：threshold = capacity * loadFactor
初始阈值：16 * 0.75 = 12。当前元素数量：当 size > threshold 时触发扩容。
扩容步骤
创建新数组：
新数组容量为原数组的 两倍（newCap = oldCap << 1）。示例：旧容量 16 → 新容量 32
重新计算索引：
对每个元素重新计算哈希值，并确定其在新数组中的位置。关键点：
扩容后，元素可能分布在 旧索引 或 旧索引 + 旧容量 两个位置。原因：newCap = oldCap * 2，(newCap - 1) & hash 的结果可能与旧索引相差 oldCap。 迁移数据：
链表迁移：
将原链表拆分为 高位链表 和 低位链表。示例：
若 hash & oldCap == 0，元素迁移到低位链表（旧索引）。否则，迁移到高位链表（旧索引 + oldCap）。 红黑树迁移：
将红黑树拆分为两个子树，分别迁移到高位和低位。目的：保持红黑树的平衡性。 更新阈值：
新阈值 = newCap * loadFactor。
示例流程
初始状态：
数组容量：16当前元素数量：12阈值：16 * 0.75 = 12 触发扩容：
插入第 13 个元素 → 触发扩容。新容量 = 32，新阈值 = 32 * 0.75 = 24.
4. 树化与链表化的动态平衡
树化条件：
链表长度 ≥ 8（TREEIFY_THRESHOLD）且 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）示例：
若数组长度 < 64，即使链表长度 ≥ 8，优先扩容而非树化。 链表化条件：
红黑树节点数 ≤ 6（UNTREEIFY_THRESHOLD）目的：减少内存开销，避免小规模树的维护成本。