讲完 List 三兄弟今天轮到 Set。很多人对 HashSet、LinkedHashSet、TreeSet 的区别只会背无序、有序、排序一追到底层就卡壳。这篇用三个收纳盒的故事把 Set 的去重原理、底层结构、排序机制和高频坑一次讲透。开场一个反直觉的事实模拟面试时面试官问“HashSet 是怎么保证元素不重复的”我答“它会自动去重重复的元素放不进去。”面试官继续追“它凭什么判断两个元素重复底层用什么存的为什么自定义对象放进 HashSet 经常去重失效LinkedHashSet 凭什么能记住插入顺序TreeSet 又凭什么能自动排序”一连串问题下来我发现自己对 Set 的理解全是黑盒。等我翻开源码才发现一个特别反直觉、也特别省事的真相——Set 三兄弟底层根本不是什么新东西它们全都是 Map 套了层壳。今天就把这层壳剥开给你看。第一幕三个收纳盒三种整理方式Set 接口下最常用的三个实现就像三个整理习惯不同的收纳盒角色底层一句话性格HashSetHashMap随手往里扔的收纳盒不保证顺序但存取最快LinkedHashSetLinkedHashMap额外贴了编号条记得你放进去的先后顺序TreeSetTreeMap红黑树强迫症收纳盒自动按大小排得整整齐齐最关键的认知先记住Set 三兄弟本质都是套壳 Map——把元素当成 Map 的key而 value 统一用一个固定的占位对象。所以你只要把 Map 的 key 那套规则搞懂Set 就懂了一大半。第二幕HashSet 扒开源码就是个 HashMap我们直接看 JDK 里 HashSet 的源码核心字段和 add 方法长这样publicclassHashSetEimplementsSetE{// 内部持有一个 HashMapprivatetransientHashMapE,Objectmap;// 所有 key 共用同一个 value一个静态常量占位就行privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){// 元素当 keyvalue 永远是同一个 PRESENTreturnmap.put(e,PRESENT)null;}}看明白了吗你每次调用add(e)底层其实是在执行map.put(e, PRESENT)你 add 的元素成了 HashMap 的 keyvalue 毫无业务意义全部指向同一个静态常量PRESENT纯粹占位、还省内存而 HashMap 的 key 天生就不允许重复同一个 key 再 put 会覆盖旧 value于是 HashSet 也就天然具备了去重能力。这就是复用的设计智慧——HashMap 已经把哈希桶、链表转红黑树、扩容全实现好了HashSet 没必要再写一遍。同理LinkedHashSet 复用 LinkedHashMapTreeSet 复用 TreeMap一个套路。第三幕去重原理——hashCode 先定位equals 再拍板那 HashMap 的 key 到底怎么判断重复分两步走这也是 Set 去重的灵魂先调用元素的hashCode()算出哈希值决定它放进哪个桶如果这个桶是空的直接存入如果桶里已经有元素再调用equals()逐个比较一旦equals()返回 true就判定为重复元素不再存入所以 HashSet 判重同时依赖hashCode()和equals()缺一不可。为什么自定义对象经常去重失效来看一段真实踩坑代码。先定义一个 Student 类故意不重写两个方法classStudent{Stringname;Student(Stringname){this.namename;}// 故意不重写 equals / hashCode}SetStudentsetnewHashSet();set.add(newStudent(张三));set.add(newStudent(张三));// 业务上明明是同一个人System.out.println(set.size());输出结果2 // 去重失败原因是没重写hashCode()时两个对象用的是 Object 的本地方法算出来的哈希值不同被分配到了不同的桶里根本走不到 equals 比较那一步自然就被当成两个元素了。正确做法是两个方法一起重写IDEA/IDEA 一键生成即可classStudent{Stringname;Student(Stringname){this.namename;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(!(oinstanceofStudent))returnfalse;returnname.equals(((Student)o).name);}OverridepublicinthashCode(){returnnamenull?0:name.hashCode();}}再跑一次1 // hashCode 相同进同一个桶equals 返回 true去重成功这个规则和 HashMap 的 key完全一致重写 equals 就必须重写 hashCode这是一条铁律。第四幕LinkedHashSet——多贴一条顺序链HashSet 有个让人不爽的点遍历顺序不可预测跟你插入的顺序没关系由哈希桶的位置决定。如果你既想去重、又想保留第一次放进去的顺序就用 LinkedHashSet。它继承自 HashSet构造时把内部的 Map 换成了 LinkedHashMap——在哈希结构之外额外用一条双向链表按插入先后把元素串了起来。// HashSet遍历顺序不保证SetStringhsnewHashSet(Arrays.asList(A,B,C,D));System.out.println(hs);// 顺序随机不保证// LinkedHashSet严格按插入顺序遍历SetStringlhsnewLinkedHashSet(Arrays.asList(A,B,C,D));System.out.println(lhs);// [A, B, C, D]永远如此输出HashSet 顺序不保证由哈希桶位置决定 LinkedHashSet [A, B, C, D]它的代价是多维护一条链表增删比 HashSet 略慢、占内存略多但遍历时只沿链表走有效元素、不用扫空桶迭代反而可能更快。典型用途是保留首次出现顺序的去重。第五幕TreeSet——红黑树帮你自动排好序TreeSet 底层是 TreeMap也就是一棵红黑树。它既不按插入顺序、也不按哈希而是按元素的大小自动排序增删查都是 O(log n)。两种排序方式第一种叫自然排序要求元素实现Comparable接口String、Integer 这些包装类都已经实现好了SetIntegertsnewTreeSet();ts.add(30);ts.add(10);ts.add(20);System.out.println(ts);// [10, 20, 30] 自动升序第二种叫定制排序构造时直接传一个Comparator优先级高于自然排序// 用 Lambda 传一个降序比较器SetIntegerdescnewTreeSet((a,b)-b-a);desc.addAll(Arrays.asList(30,10,20));System.out.println(desc);// [30, 20, 10]输出[10, 20, 30] [30, 20, 10]必考点往 TreeSet 放自定义对象时要么对象实现Comparable要么构造时给Comparator。否则红黑树插入时要不断比较大小却比不了直接抛ClassCastException。有序带来的导航超能力正因为排好了序TreeSet 还能做 HashSet 做不到的事——取最值、找相邻、查区间TreeSetIntegertnewTreeSet(Arrays.asList(10,20,30,40));t.first();// 10最小t.last();// 40最大t.ceiling(25);// 30大于等于 25 的最小元素t.floor(25);// 20小于等于 25 的最大元素t.subSet(20,true,40,false);// [20, 30]区间视图t.headSet(30);// [10, 20]小于 30 的部分面试里一旦出现排行榜、区间查询、找最接近的值这类需求就该条件反射想到 TreeSet / TreeMap。第六幕三兄弟到底怎么选维度HashSetLinkedHashSetTreeSet底层HashMapLinkedHashMapTreeMap红黑树顺序无序插入顺序按大小排序增删查复杂度O(1)O(1)O(log n)null 值允许 1 个允许 1 个默认不允许NPE元素要求重写 hashCode equals同 HashSet实现 Comparable 或传 Comparator性能最快略慢、略占内存最慢但有序选型只去重首选去重 保序去重 排序/区间一句话决策只去重选 HashSet要保序选 LinkedHashSet要排序选 TreeSet。第七幕那些年踩过的坑坑 1对象放进 HashSet 后又改了参与哈希的字段这是一个非常隐蔽的内存泄漏陷阱SetStudentsetnewHashSet();StudentsnewStudent(张三);set.add(s);s.name李四;// 修改了参与 hashCode 的字段set.remove(s);// 删不掉System.out.println(set.size());// 仍然是 1为什么删不掉因为存入时是按张三算的桶位置修改后remove却按李四重新算桶两个桶根本不是同一个自然找不到原对象。结论放进 HashSet / HashMap 的 key不要修改参与 hashCode 和 equals 的字段实际开发尽量用 String 这种不可变对象当 key。坑 2三个 Set 都线程不安全多线程并发写可能丢数据、或抛ConcurrentModificationException要用并发版本// 方式一包装成同步集合方法级加锁SetStringsafe1Collections.synchronizedSet(newHashSet());// 方式二写时复制适合读多写少底层是 CopyOnWriteArrayListSetStringsafe2newCopyOnWriteArraySet();// 方式三要排序又要线程安全用跳表实现SetStringsafe3newConcurrentSkipListSet();坑 3遍历的时候别直接删// 错误for-each 里直接 remove触发 fail-fast抛异常for(Strings:set){set.remove(s);}// 正确用迭代器自己的 removeIteratorStringitset.iterator();while(it.hasNext()){it.next();it.remove();}总结口诀表知识点核心结论HashSet 底层就是 HashMap元素当 keyvalue 是固定常量 PRESENT去重原理先 hashCode 定位桶桶非空再 equals 判重两者都要重写LinkedHashSet 底层LinkedHashMap多一条双向链表维护插入顺序TreeSet 底层TreeMap 红黑树按大小自动排序复杂度 O(log n)TreeSet 排序自然排序 Comparable或构造传 Comparator否则 ClassCastExceptionTreeSet 特长first/last/ceiling/floor/subSet 取最值与区间选型去重 HashSet、保序 LinkedHashSet、排序 TreeSet隐蔽坑key 改了参与哈希的字段会导致 remove 不掉线程安全synchronizedSet / CopyOnWriteArraySet / ConcurrentSkipListSet一句话记住Hash 无序 O(1)元素当 key value 占位去重先看 hashCode 定桶、再让 equals 拍板两个方法一起写Link 保序加链表插入先后不会乱Tree 排序红黑树log n 复杂度最值区间它最行key 字段别乱改改完删除找不到。这篇如果帮你把 Set 三兄弟彻底理清了点个赞、关注一下Java 集合框架系列会持续更新下一篇讲 Iterator 与 fail-fast 机制。有疑问欢迎评论区交流我会逐条回复。#Java#java面试#后端开发#HashSet#集合框架#程序员#面试题#数据结构 面试官问 HashSet 怎么去重，我打开源码发现：它居然就是个 HashMap
讲完 List 三兄弟今天轮到 Set。很多人对 HashSet、LinkedHashSet、TreeSet 的区别只会背无序、有序、排序一追到底层就卡壳。这篇用三个收纳盒的故事把 Set 的去重原理、底层结构、排序机制和高频坑一次讲透。开场一个反直觉的事实模拟面试时面试官问“HashSet 是怎么保证元素不重复的”我答“它会自动去重重复的元素放不进去。”面试官继续追“它凭什么判断两个元素重复底层用什么存的为什么自定义对象放进 HashSet 经常去重失效LinkedHashSet 凭什么能记住插入顺序TreeSet 又凭什么能自动排序”一连串问题下来我发现自己对 Set 的理解全是黑盒。等我翻开源码才发现一个特别反直觉、也特别省事的真相——Set 三兄弟底层根本不是什么新东西它们全都是 Map 套了层壳。今天就把这层壳剥开给你看。第一幕三个收纳盒三种整理方式Set 接口下最常用的三个实现就像三个整理习惯不同的收纳盒角色底层一句话性格HashSetHashMap随手往里扔的收纳盒不保证顺序但存取最快LinkedHashSetLinkedHashMap额外贴了编号条记得你放进去的先后顺序TreeSetTreeMap红黑树强迫症收纳盒自动按大小排得整整齐齐最关键的认知先记住Set 三兄弟本质都是套壳 Map——把元素当成 Map 的key而 value 统一用一个固定的占位对象。所以你只要把 Map 的 key 那套规则搞懂Set 就懂了一大半。第二幕HashSet 扒开源码就是个 HashMap我们直接看 JDK 里 HashSet 的源码核心字段和 add 方法长这样publicclassHashSetEimplementsSetE{// 内部持有一个 HashMapprivatetransientHashMapE,Objectmap;// 所有 key 共用同一个 value一个静态常量占位就行privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){// 元素当 keyvalue 永远是同一个 PRESENTreturnmap.put(e,PRESENT)null;}}看明白了吗你每次调用add(e)底层其实是在执行map.put(e, PRESENT)你 add 的元素成了 HashMap 的 keyvalue 毫无业务意义全部指向同一个静态常量PRESENT纯粹占位、还省内存而 HashMap 的 key 天生就不允许重复同一个 key 再 put 会覆盖旧 value于是 HashSet 也就天然具备了去重能力。这就是复用的设计智慧——HashMap 已经把哈希桶、链表转红黑树、扩容全实现好了HashSet 没必要再写一遍。同理LinkedHashSet 复用 LinkedHashMapTreeSet 复用 TreeMap一个套路。第三幕去重原理——hashCode 先定位equals 再拍板那 HashMap 的 key 到底怎么判断重复分两步走这也是 Set 去重的灵魂先调用元素的hashCode()算出哈希值决定它放进哪个桶如果这个桶是空的直接存入如果桶里已经有元素再调用equals()逐个比较一旦equals()返回 true就判定为重复元素不再存入所以 HashSet 判重同时依赖hashCode()和equals()缺一不可。为什么自定义对象经常去重失效来看一段真实踩坑代码。先定义一个 Student 类故意不重写两个方法classStudent{Stringname;Student(Stringname){this.namename;}// 故意不重写 equals / hashCode}SetStudentsetnewHashSet();set.add(newStudent(张三));set.add(newStudent(张三));// 业务上明明是同一个人System.out.println(set.size());输出结果2 // 去重失败原因是没重写hashCode()时两个对象用的是 Object 的本地方法算出来的哈希值不同被分配到了不同的桶里根本走不到 equals 比较那一步自然就被当成两个元素了。正确做法是两个方法一起重写IDEA/IDEA 一键生成即可classStudent{Stringname;Student(Stringname){this.namename;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(!(oinstanceofStudent))returnfalse;returnname.equals(((Student)o).name);}OverridepublicinthashCode(){returnnamenull?0:name.hashCode();}}再跑一次1 // hashCode 相同进同一个桶equals 返回 true去重成功这个规则和 HashMap 的 key完全一致重写 equals 就必须重写 hashCode这是一条铁律。第四幕LinkedHashSet——多贴一条顺序链HashSet 有个让人不爽的点遍历顺序不可预测跟你插入的顺序没关系由哈希桶的位置决定。如果你既想去重、又想保留第一次放进去的顺序就用 LinkedHashSet。它继承自 HashSet构造时把内部的 Map 换成了 LinkedHashMap——在哈希结构之外额外用一条双向链表按插入先后把元素串了起来。// HashSet遍历顺序不保证SetStringhsnewHashSet(Arrays.asList(A,B,C,D));System.out.println(hs);// 顺序随机不保证// LinkedHashSet严格按插入顺序遍历SetStringlhsnewLinkedHashSet(Arrays.asList(A,B,C,D));System.out.println(lhs);// [A, B, C, D]永远如此输出HashSet 顺序不保证由哈希桶位置决定 LinkedHashSet [A, B, C, D]它的代价是多维护一条链表增删比 HashSet 略慢、占内存略多但遍历时只沿链表走有效元素、不用扫空桶迭代反而可能更快。典型用途是保留首次出现顺序的去重。第五幕TreeSet——红黑树帮你自动排好序TreeSet 底层是 TreeMap也就是一棵红黑树。它既不按插入顺序、也不按哈希而是按元素的大小自动排序增删查都是 O(log n)。两种排序方式第一种叫自然排序要求元素实现Comparable接口String、Integer 这些包装类都已经实现好了SetIntegertsnewTreeSet();ts.add(30);ts.add(10);ts.add(20);System.out.println(ts);// [10, 20, 30] 自动升序第二种叫定制排序构造时直接传一个Comparator优先级高于自然排序// 用 Lambda 传一个降序比较器SetIntegerdescnewTreeSet((a,b)-b-a);desc.addAll(Arrays.asList(30,10,20));System.out.println(desc);// [30, 20, 10]输出[10, 20, 30] [30, 20, 10]必考点往 TreeSet 放自定义对象时要么对象实现Comparable要么构造时给Comparator。否则红黑树插入时要不断比较大小却比不了直接抛ClassCastException。有序带来的导航超能力正因为排好了序TreeSet 还能做 HashSet 做不到的事——取最值、找相邻、查区间TreeSetIntegertnewTreeSet(Arrays.asList(10,20,30,40));t.first();// 10最小t.last();// 40最大t.ceiling(25);// 30大于等于 25 的最小元素t.floor(25);// 20小于等于 25 的最大元素t.subSet(20,true,40,false);// [20, 30]区间视图t.headSet(30);// [10, 20]小于 30 的部分面试里一旦出现排行榜、区间查询、找最接近的值这类需求就该条件反射想到 TreeSet / TreeMap。第六幕三兄弟到底怎么选维度HashSetLinkedHashSetTreeSet底层HashMapLinkedHashMapTreeMap红黑树顺序无序插入顺序按大小排序增删查复杂度O(1)O(1)O(log n)null 值允许 1 个允许 1 个默认不允许NPE元素要求重写 hashCode equals同 HashSet实现 Comparable 或传 Comparator性能最快略慢、略占内存最慢但有序选型只去重首选去重 保序去重 排序/区间一句话决策只去重选 HashSet要保序选 LinkedHashSet要排序选 TreeSet。第七幕那些年踩过的坑坑 1对象放进 HashSet 后又改了参与哈希的字段这是一个非常隐蔽的内存泄漏陷阱SetStudentsetnewHashSet();StudentsnewStudent(张三);set.add(s);s.name李四;// 修改了参与 hashCode 的字段set.remove(s);// 删不掉System.out.println(set.size());// 仍然是 1为什么删不掉因为存入时是按张三算的桶位置修改后remove却按李四重新算桶两个桶根本不是同一个自然找不到原对象。结论放进 HashSet / HashMap 的 key不要修改参与 hashCode 和 equals 的字段实际开发尽量用 String 这种不可变对象当 key。坑 2三个 Set 都线程不安全多线程并发写可能丢数据、或抛ConcurrentModificationException要用并发版本// 方式一包装成同步集合方法级加锁SetStringsafe1Collections.synchronizedSet(newHashSet());// 方式二写时复制适合读多写少底层是 CopyOnWriteArrayListSetStringsafe2newCopyOnWriteArraySet();// 方式三要排序又要线程安全用跳表实现SetStringsafe3newConcurrentSkipListSet();坑 3遍历的时候别直接删// 错误for-each 里直接 remove触发 fail-fast抛异常for(Strings:set){set.remove(s);}// 正确用迭代器自己的 removeIteratorStringitset.iterator();while(it.hasNext()){it.next();it.remove();}总结口诀表知识点核心结论HashSet 底层就是 HashMap元素当 keyvalue 是固定常量 PRESENT去重原理先 hashCode 定位桶桶非空再 equals 判重两者都要重写LinkedHashSet 底层LinkedHashMap多一条双向链表维护插入顺序TreeSet 底层TreeMap 红黑树按大小自动排序复杂度 O(log n)TreeSet 排序自然排序 Comparable或构造传 Comparator否则 ClassCastExceptionTreeSet 特长first/last/ceiling/floor/subSet 取最值与区间选型去重 HashSet、保序 LinkedHashSet、排序 TreeSet隐蔽坑key 改了参与哈希的字段会导致 remove 不掉线程安全synchronizedSet / CopyOnWriteArraySet / ConcurrentSkipListSet一句话记住Hash 无序 O(1)元素当 key value 占位去重先看 hashCode 定桶、再让 equals 拍板两个方法一起写Link 保序加链表插入先后不会乱Tree 排序红黑树log n 复杂度最值区间它最行key 字段别乱改改完删除找不到。这篇如果帮你把 Set 三兄弟彻底理清了点个赞、关注一下Java 集合框架系列会持续更新下一篇讲 Iterator 与 fail-fast 机制。有疑问欢迎评论区交流我会逐条回复。#Java#java面试#后端开发#HashSet#集合框架#程序员#面试题#数据结构