leetcode副产品:Deepseek老师讲HashSet（待阅读）
·
HashSet 源码级详解
1. 什么是HashSet？
HashSet 是基于 HashMap 实现的 不重复元素集合，底层实际上就是封装了一个 HashMap。
// HashSet的核心源码（简化版）
public class HashSet<E> {
private transient HashMap<E, Object> map; // 底层使用HashMap
// 虚拟值，所有key共享同一个value
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>(); // 初始化HashMap
}
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 元素作为key存入
}
public boolean contains(Object o) {
return map.containsKey(o); // 调用HashMap的containsKey
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT; // 移除key
}
}
2. HashSet的工作原理
当你添加元素时：
add("apple")
→ 作为key存入HashMap: {"apple" → PRESENT}
→ HashMap计算"apple"的hashCode() → 索引位置
→ 存入数组对应位置
当你检查是否存在：
contains("apple")
→ HashMap查找key是否存在
→ 计算hashCode() → 定位到数组位置
→ 检查该位置是否有"apple"
3. HashSet的源码分析（Java 8）
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
// 1. 核心属性
private transient HashMap<E,Object> map; // 底层HashMap
private static final Object PRESENT = new Object(); // 虚拟值
// 2. 构造函数
public HashSet() {
map = new HashMap<>(); // 默认容量16，负载因子0.75
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity); // 指定初始容量
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor); // 指定容量和负载因子
}
// 3. 添加元素
public boolean add(E e) {
// put方法返回旧的value，如果是新key返回null
return map.put(e, PRESENT) == null;
}
// 4. 删除元素
public boolean remove(Object o) {
// 移除成功返回true
return map.remove(o) == PRESENT;
}
// 5. 检查是否存在
public boolean contains(Object o) {
return map.containsKey(o); // O(1)时间复杂度
}
// 6. 获取大小
public int size() {
return map.size();
}
// 7. 清空集合
public void clear() {
map.clear();
}
// 8. 迭代器
public Iterator<E> iterator() {
return map.keySet().iterator(); // 返回key的迭代器
}
}
4. 核心特性详解
| 特性 | 说明 | 源码体现 |
|---|---|---|
| 无序 | 元素顺序不保证 | 基于HashMap的keySet，哈希表无序 |
| 唯一性 | 元素不能重复 | 通过equals()和hashCode()判断 |
| 允许null | 允许一个null元素 | map允许null key |
| 非线程安全 | 多线程需外部同步 | 没有同步锁 |
| 快速失败 | 并发修改抛出异常 | modCount机制 |
5. 去重原理
// HashSet如何保证元素唯一？
public class HashSetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
// 添加过程
set.add("apple");
// 1. 计算"apple".hashCode() → 哈希值
// 2. 找到对应桶位置
// 3. 如果位置为空，直接放入
// 4. 如果不为空，用equals()比较
set.add("apple");
// 1. 计算hashCode相同
// 2. 找到相同桶位置
// 3. equals()比较发现相同
// 4. 不放入，返回false
System.out.println(set); // [apple]
}
}
6. 自定义对象去重
// 必须在自定义类中重写hashCode()和equals()
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age); // 根据name和age生成哈希值
}
}
// 使用
Set<Person> set = new HashSet<>();
set.add(new Person("Alice", 20));
set.add(new Person("Alice", 20)); // 不会重复添加
set.add(new Person("Alice", 21)); // 会添加，因为age不同
7. 性能优化参数
// 1. 初始容量（Initial Capacity）
Set<String> set1 = new HashSet<>(100); // 预计存100个元素
Set<String> set2 = new HashSet<>(1000); // 预计存1000个元素
// 2. 负载因子（Load Factor）
Set<String> set3 = new HashSet<>(16, 0.5f); // 负载因子0.5
// 默认0.75，值越小，空间换时间
// 值越大，时间换空间
// 3. 预估容量公式
// 初始容量 = (预计元素个数 / 负载因子) + 1
int expectedSize = 1000;
int initialCapacity = (int)(expectedSize / 0.75f) + 1;
Set<String> set4 = new HashSet<>(initialCapacity);
8. 时间复杂度详解
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 说明 |
|---|---|---|---|
| add() | O(1) | O(n) | 哈希冲突严重时退化为链表 |
| remove() | O(1) | O(n) | 同上 |
| contains() | O(1) | O(n) | 同上 |
| size() | O(1) | O(1) | 直接返回计数 |
| iterator() | O(n) | O(n) | 遍历所有元素 |
9. 与其它Set的对比
| 特性 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层 | HashMap | LinkedHashMap | TreeMap |
| 顺序 | 无序 | 插入顺序 | 排序顺序 |
| 时间复杂度 | O(1) | O(1) | O(log n) |
| 允许null | 允许 | 允许 | 不允许（可配置） |
| 线程安全 | 否 | 否 | 否 |
10. 常见使用场景
public class HashSetUseCases {
// 1. 去重
public static List<Integer> removeDuplicates(List<Integer> list) {
return new ArrayList<>(new HashSet<>(list));
}
// 2. 快速查找
public static boolean isBlacklisted(String ip) {
Set<String> blacklist = new HashSet<>();
blacklist.add("192.168.1.1");
blacklist.add("10.0.0.1");
return blacklist.contains(ip); // O(1)
}
// 3. 集合运算
public static void setOperations() {
Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> set2 = new HashSet<>(Arrays.asList(2, 3, 4));
// 交集
set1.retainAll(set2); // [2, 3]
// 并集
set1.addAll(set2); // [1, 2, 3, 4]
// 差集
set1.removeAll(set2); // [1]
}
// 4. 缓存存在性检查
public static class Cache {
private Set<String> cacheKeys = new HashSet<>();
public boolean isCached(String key) {
return cacheKeys.contains(key);
}
public void addToCache(String key) {
cacheKeys.add(key);
}
}
}
11. 源码面试题
// Q1: HashSet如何保证元素不重复？
// A: 基于HashMap，元素作为key存入，value是虚拟对象。
// 添加时调用HashMap的put方法，如果key已存在，返回旧value，add返回false
// Q2: HashSet允许null吗？
// A: 允许一个null，因为HashMap允许一个null key
// Q3: HashSet是线程安全的吗？
// A: 不是，多线程环境下需要使用Collections.synchronizedSet()
// Q4: 为什么重写equals()时必须重写hashCode()？
// A: HashSet先比较hashCode()，再比较equals()
// 如果只重写equals()，相同对象可能hashCode不同，导致无法去重
12. 线程安全解决方案
// 1. 使用同步包装器
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
// 2. 使用CopyOnWriteArraySet（适合读多写少）
Set<String> copyOnWriteSet = new CopyOnWriteArraySet<>();
// 3. 使用ConcurrentHashMap.newKeySet()
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
总结
- HashSet = 阉割版的HashMap，只关心key，不关心value
- 核心优势：O(1)的增删改查
- 核心限制：无序、非线程安全
- 使用建议：只需要判断元素是否存在时，首选HashSet
致谢/参考资料：
尊敬的力扣老师和尊敬的Deepseek老师！
声明：
本文内容仅用于个人学习记录，不用于任何商业用途。部分代码、技术观点或示例可能来源于网络或其他公开资源，如有侵权，请联系我删除。加粗样式
这里是“一人公司”的成长家园。我们提供从产品曝光、技术变现到法律财税的全栈内容，并连接云服务、办公空间等稀缺资源，助你专注创造，无忧运营。
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)