leetcode副产品:Deepseek老师讲HashSet（待阅读）
HashSet 源码级详解
1. 什么是HashSet？
HashSet是基于HashMap实现的不重复元素集合，底层实际上就是封装了一个 HashMap。
// HashSet的核心源码（简化版）publicclassHashSet<E>{privatetransientHashMap<E,Object>map;// 底层使用HashMap// 虚拟值，所有key共享同一个valueprivatestaticfinalObjectPRESENT=newObject();publicHashSet(){map=newHashMap<>();// 初始化HashMap}publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;// 元素作为key存入}publicbooleancontains(Objecto){returnmap.containsKey(o);// 调用HashMap的containsKey}publicbooleanremove(Objecto){returnmap.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）
publicclassHashSet<E>extendsAbstractSet<E>implementsSet<E>,Cloneable,java.io.Serializable{// 1. 核心属性privatetransientHashMap<E,Object>map;// 底层HashMapprivatestaticfinalObjectPRESENT=newObject();// 虚拟值// 2. 构造函数publicHashSet(){map=newHashMap<>();// 默认容量16，负载因子0.75}publicHashSet(intinitialCapacity){map=newHashMap<>(initialCapacity);// 指定初始容量}publicHashSet(intinitialCapacity,floatloadFactor){map=newHashMap<>(initialCapacity,loadFactor);// 指定容量和负载因子}// 3. 添加元素publicbooleanadd(Ee){// put方法返回旧的value，如果是新key返回nullreturnmap.put(e,PRESENT)==null;}// 4. 删除元素publicbooleanremove(Objecto){// 移除成功返回truereturnmap.remove(o)==PRESENT;}// 5. 检查是否存在publicbooleancontains(Objecto){returnmap.containsKey(o);// O(1)时间复杂度}// 6. 获取大小publicintsize(){returnmap.size();}// 7. 清空集合publicvoidclear(){map.clear();}// 8. 迭代器publicIterator<E>iterator(){returnmap.keySet().iterator();// 返回key的迭代器}}4. 核心特性详解
| 特性 | 说明 | 源码体现 |
|---|---|---|
| 无序 | 元素顺序不保证 | 基于HashMap的keySet，哈希表无序 |
| 唯一性 | 元素不能重复 | 通过equals()和hashCode()判断 |
| 允许null | 允许一个null元素 | map允许null key |
| 非线程安全 | 多线程需外部同步 | 没有同步锁 |
| 快速失败 | 并发修改抛出异常 | modCount机制 |
5. 去重原理
// HashSet如何保证元素唯一？publicclassHashSetDemo{publicstaticvoidmain(String[]args){Set<String>set=newHashSet<>();// 添加过程set.add("apple");// 1. 计算"apple".hashCode() → 哈希值// 2. 找到对应桶位置// 3. 如果位置为空，直接放入// 4. 如果不为空，用equals()比较set.add("apple");// 1. 计算hashCode相同// 2. 找到相同桶位置// 3. equals()比较发现相同// 4. 不放入，返回falseSystem.out.println(set);// [apple]}}6. 自定义对象去重
// 必须在自定义类中重写hashCode()和equals()classPerson{Stringname;intage;Person(Stringname,intage){this.name=name;this.age=age;}@Overridepublicbooleanequals(Objecto){if(this==o)returntrue;if(o==null||getClass()!=o.getClass())returnfalse;Personperson=(Person)o;returnage==person.age&&Objects.equals(name,person.name);}@OverridepublicinthashCode(){returnObjects.hash(name,age);// 根据name和age生成哈希值}}// 使用Set<Person>set=newHashSet<>();set.add(newPerson("Alice",20));set.add(newPerson("Alice",20));// 不会重复添加set.add(newPerson("Alice",21));// 会添加，因为age不同7. 性能优化参数
// 1. 初始容量（Initial Capacity）Set<String>set1=newHashSet<>(100);// 预计存100个元素Set<String>set2=newHashSet<>(1000);// 预计存1000个元素// 2. 负载因子（Load Factor）Set<String>set3=newHashSet<>(16,0.5f);// 负载因子0.5// 默认0.75，值越小，空间换时间// 值越大，时间换空间// 3. 预估容量公式// 初始容量 = (预计元素个数 / 负载因子) + 1intexpectedSize=1000;intinitialCapacity=(int)(expectedSize/0.75f)+1;Set<String>set4=newHashSet<>(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. 常见使用场景
publicclassHashSetUseCases{// 1. 去重publicstaticList<Integer>removeDuplicates(List<Integer>list){returnnewArrayList<>(newHashSet<>(list));}// 2. 快速查找publicstaticbooleanisBlacklisted(Stringip){Set<String>blacklist=newHashSet<>();blacklist.add("192.168.1.1");blacklist.add("10.0.0.1");returnblacklist.contains(ip);// O(1)}// 3. 集合运算publicstaticvoidsetOperations(){Set<Integer>set1=newHashSet<>(Arrays.asList(1,2,3));Set<Integer>set2=newHashSet<>(Arrays.asList(2,3,4));// 交集set1.retainAll(set2);// [2, 3]// 并集set1.addAll(set2);// [1, 2, 3, 4]// 差集set1.removeAll(set2);// [1]}// 4. 缓存存在性检查publicstaticclassCache{privateSet<String>cacheKeys=newHashSet<>();publicbooleanisCached(Stringkey){returncacheKeys.contains(key);}publicvoidaddToCache(Stringkey){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(newHashSet<>());// 2. 使用CopyOnWriteArraySet（适合读多写少）Set<String>copyOnWriteSet=newCopyOnWriteArraySet<>();// 3. 使用ConcurrentHashMap.newKeySet()Set<String>concurrentSet=ConcurrentHashMap.newKeySet();总结
- HashSet = 阉割版的HashMap，只关心key，不关心value
- 核心优势：O(1)的增删改查
- 核心限制：无序、非线程安全
- 使用建议：只需要判断元素是否存在时，首选HashSet
致谢/参考资料：
尊敬的力扣老师和尊敬的Deepseek老师！
声明：
本文内容仅用于个人学习记录，不用于任何商业用途。部分代码、技术观点或示例可能来源于网络或其他公开资源，如有侵权，请联系我删除。加粗样式