Set 这个东西，跟我一开始想的不太一样

学完 List 之后我自然就去看 Set 了。当时我心想不就是跟 List 差不多嘛都是存东西的容器。结果翻开文档一看第一句话就给我整不会了“Set 不允许包含重复元素。”我想了想那 List 允许重复对吧那这俩到底啥时候用 List、啥时候用 Set更让我困惑的是同样是 Set还有 HashSet、LinkedHashSet、TreeSet 三种它们到底有什么区别我花了不少时间一个一个搞清楚的。这篇就按我当时的学习顺序来写。开始之前先说一句Set 的学习路径跟 List 不太一样。List 的学习重点在不同的实现怎么选ArrayList 还是 LinkedList而 Set 的学习重点在三个 Set 的去重逻辑有什么区别。因为去重是 Set 的核心能力理解每种 Set 怎么判断重复就理解了它的大部分设计思路。List 和 Set到底差在哪要说清楚 Set得先把它跟 List 放在一起比。我当初列了一张表对比来看就清楚多了。List是有序的。这个有序指的是添加顺序——你先加A再加B取出来的时候A在前“B在后。而且 List 允许重复你加三个A进去它就存三个A”。还能通过下标直接访问list.get(0)拿第一个。Set的核心就两个字唯一。同一个元素你加多少次它都只存一份。没有下标不能通过索引访问只能遍历。至于有序还是无序得看具体是哪个 Set 实现。我当时写了个小例子试了一下ListStringlistnewArrayList();list.add(apple);list.add(banana);list.add(apple);// List 允许重复System.out.println(list);// [apple, banana, apple]SetStringsetnewHashSet();set.add(apple);set.add(banana);set.add(apple);// Set 不会加进去System.out.println(set);// [banana, apple] 顺序也不一定看到输出结果的时候我大概明白了。List 像购物车同样的商品你可以加好几份。Set 像已购清单每个商品只出现一次。后来在实际写代码的时候我慢慢形成了自己的判断如果你需要按顺序存东西而且可能要按索引取某个位置的元素用 List。如果你只是想把一堆数据存起来过滤掉重复的用 Set。比如从用户输入里收集标签你不想让用户重复提交同一个标签那用 Set 就天然去重了不用自己写判重逻辑。还有一个细节我当时觉得挺有意思的。List 能存多个 nulllist.add(null)可以来好几次。但 Set 最多只能存一个 nullHashSet 和 LinkedHashSet 是这样TreeSet 连 null 都不让存因为排序的时候拿 null 去比较会抛空指针。在我当时看来List 和 Set 的选择其实可以简化成一句话要不要重复要重复用 List不要重复用 Set。如果你的场景里数据天然不会有重复比如从数据库查出来的主键列表那用 List 还是 Set 差别不大看你要不要下标访问。但如果数据可能有重复而你不想自己写去重逻辑Set 就是最自然的选择。HashSet——最常用的那个 Set学 Set 的时候我第一个接触的就是 HashSet。当时我最想知道的是它怎么知道一个元素已经存在了后来看了原理才知道HashSet 底层用的是 HashMap。你没看错Set 的底层是个 Map。怎么做到的HashSet 存元素的时候实际上是把元素作为 HashMap 的 key 存进去value 统一用一个叫 PRESENT 的常量占位。这个 PRESENT 就是个new Object()没啥特别的就是占个位。// HashSet 的 add 方法大概长这样privatestaticfinalObjectPRESENTnewObject();publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}所以往 HashSet 里加一个apple实际上是在底层的 HashMap 里放了一对(apple - PRESENT)。因为 HashMap 的 key 不能重复所以 HashSet 自然也就不会重复了。知道这个之后我对Set 底层是 Map这句话的理解就深了一层。同时也明白了为什么 HashSet 的元素要重写 hashCode 和 equals 方法——因为 HashMap 判断 key 是否重复靠的就是这两个方法。我当时还特意写了一段代码来验证重复的判断过程publicclassPerson{Stringname;intage;Person(Stringname,intage){this.namename;this.ageage;}// 故意不重写 hashCode 和 equals}publicstaticvoidmain(String[]args){SetPersonsetnewHashSet();set.add(newPerson(张三,20));set.add(newPerson(张三,20));// 这两个张三会被当成不同的人System.out.println(set.size());// 输出 2不是 1}不重写 hashCode 和 equals 的话即使两个对象的字段值一模一样HashSet 也把它们当成两个不同的元素。因为 Object 默认的 hashCode 是根据内存地址算的两个new出来的对象地址肯定不一样。后来我把正确的写法补上之后去重就正常了publicclassPerson{Stringname;intage;Person(Stringname,intage){this.namename;this.ageage;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(onull||getClass()!o.getClass())returnfalse;Personperson(Person)o;returnageperson.ageObjects.equals(name,person.name);}OverridepublicinthashCode(){returnObjects.hash(name,age);}}加上之后两个字段一模一样的 Person 对象就有了相同的 hashCode 和 equals 为 true 的判断HashSet 就能正确去重了。这个坑我后来在代码里遇到过。当时从数据库里查了一批用户数据放到 HashSet 里去重结果发现去重失败了。排查了半天才意识到是没重写 hashCode 和 equals。加上之后就好了。另外因为 HashSet 底层是 HashMap所以 HashMap 的性能特点 HashSet 也有。比如初始容量和负载因子的概念也是一样的。如果你提前知道要存大量数据可以在创建 HashSet 的时候指定初始容量减少扩容次数。不过一般来说用默认值就行了只有数据量特别大的时候才需要关注这个。HashSet 的查找过程既然底层是 HashMap那 HashSet 判断元素重复的流程就跟 HashMap 判断 key 是否存在的流程一样先算元素的 hashCode定位到数组的某个桶如果桶是空的说明没有重复元素直接放进去如果桶里有元素再用 equals 挨个比一遍有任何一个 equals 返回 true就说明重复了不放了这个过程我第一次理解的时候花了点功夫。关键是搞明白 hashCode 和 equals 的分工hashCode 先筛一遍equals 最后拍板。hashCode 一样的不一定就是同一个元素可能哈希冲突但 hashCode 不一样的一定不是同一个元素。所以重写的时候原则上 hashCode 和 equals 要一起重写保证逻辑一致。不然可能出现两个对象 equals 返回 true但 hashCode 不一样——这样就违背了相等的对象必须有相同的 hashCode这个约定。HashMap 和 HashSet 的行为就会变得很奇怪。比如你放进去一个对象之后用另一个 equals 相等的对象去查可能因为 hashCode 不同而定位到不同的桶查不到。这种 bug 非常隐蔽我当时排查了很久才找到原因。LinkedHashSet——既能去重又能记住顺序HashSet 有个问题它不保证顺序。你加元素的顺序跟遍历出来的顺序可能完全不一样。有次我写一个功能需要把用户最近搜索的关键词去重同时保留搜索的时间顺序。用 HashSet 的话顺序就丢了。后来找到 LinkedHashSet正好解决这个问题。LinkedHashSet 继承自 HashSet底层用的是 LinkedHashMap。它比 HashSet 多了什么多了一条双向链表。这条链表把插入的每个元素按顺序串起来了。所以遍历的时候输出的顺序就是你插入的顺序。内部实现上LinkedHashSet 的构造方法调用了 HashSet 的一个特殊构造器这个构造器会初始化一个 LinkedHashMap 而不是普通的 HashMap。LinkedHashMap 在 HashMap 的基础上给每个节点增加了 before 和 after 两个指针指向插入顺序中的前一个和后一个节点。这个设计我以前觉得挺巧妙的——在完全不改变哈希表结构的前提下用一条额外的链表就把顺序记录下来了。LinkedHashSetStringsetnewLinkedHashSet();set.add(Java);set.add(Python);set.add(JavaScript);set.add(Java);// 重复不会加进去System.out.println(set);// [Java, Python, JavaScript] 保持插入顺序注意它保持的是插入顺序不是按值排序。Java 在最前面不是因为字母顺序是因为它最先被加进去。我当时有个疑问为什么 LinkedHashSet 既能去重又能保持顺序那 HashSet 还有什么用答案是性能。LinkedHashSet 因为要多维护一条链表插入和删除的时候多了一点开销。虽然这个开销通常不大但如果数据量特别大而且对顺序没要求HashSet 更合适。TreeSet——自动排序的 SetTreeSet 是三种 Set 里最特别的一个。它不靠 hashCode 和 equals 来判断重复而是靠比较器。TreeSet 底层是 TreeMap红黑树元素插入的时候会按照某种规则自动排序。这个规则可以有两种方式指定。方式一元素实现 Comparable 接口如果元素本身实现了 Comparable 接口TreeSet 就直接用它的 compareTo 方法来排序和去重。TreeSetIntegernumbersnewTreeSet();numbers.add(5);numbers.add(1);numbers.add(3);numbers.add(5);// 重复加不进去System.out.println(numbers);// [1, 3, 5] 自动升序Integer 和 String 这些常见的类都实现了 Comparable所以直接用就行。自定义对象如果想放到 TreeSet 里就得自己实现 ComparablepublicclassStudentimplementsComparableStudent{Stringname;intscore;// ... 构造方法啥的OverridepublicintcompareTo(Studentother){returnthis.score-other.score;// 按分数升序}}// 这样就能放进 TreeSet 了TreeSetStudentstudentsnewTreeSet();方式二传入 Comparator如果你不想改类本身或者想用跟类默认排序不一样的规则可以在创建 TreeSet 的时候传一个 ComparatorTreeSetStudentstudentsnewTreeSet((s1,s2)-s2.score-s1.score);// 按分数降序我当时觉得这种方式更灵活尤其是对已有的类做排序的时候不用去动原来的代码。两种方式各有适用场景。如果类是你自己写的而且这个类有一种天然的排序比如学生按分数排那实现 Comparable 更合适因为排序逻辑跟类本身绑定在一起不会忘掉。如果同一个类在不同的地方有不同的排序需求比如有时候按分数排、有时候按年龄排那就用 Comparator每次创建 TreeSet 的时候指定不同的规则。TreeSet 的去重逻辑跟 HashSet 不一样这个是我后来踩坑才发现的。HashSet 判断重复靠 hashCode equals。但 TreeSet 完全不看这两个方法它只看 compareTo 或 compare 的返回值。如果返回值是 0就认为是同一个元素不会加进去。这意味着什么如果你的 compareTo 方法只比较了分数那两个名字不同但分数相同的学生在 TreeSet 里会被当成同一个人。publicclassStudentimplementsComparableStudent{Stringname;intscore;OverridepublicintcompareTo(Studentother){returnthis.score-other.score;// 只看分数}}TreeSetStudentsetnewTreeSet();set.add(newStudent(张三,80));set.add(newStudent(李四,80));// 加不进去了因为分数一样System.out.println(set.size());// 输出 1我第一次遇到这个问题的时候真的很懵心想我明明加的是两个不同的人为什么 TreeSet 只存了一个后来才意识到 TreeSet 的去重逻辑跟 HashSet 不一样。如果你的比较器只覆盖了部分字段那相等的范围就比你想象的大。所以用 TreeSet 的时候一定要想清楚什么样的两个元素算相同这个定义要体现在 compareTo 或 compare 里。如果分数相同但名字不同也算不同的人那比较逻辑就得把名字也加进去。另外因为 TreeSet 底层是红黑树它提供了一些 HashSet 没有的有用方法。比如first()取最小元素last()取最大元素headSet(to)取比某个值小的所有元素tailSet(from)取比某个值大的所有元素。这些在做范围查询的时候特别好用。还有一个容易踩的坑compareTo 里直接用减法可能溢出。this.score - other.score这种写法在 score 是负数或者差值超过 Integer 范围的时候会出问题。更稳妥的做法是用Integer.compare(this.score, other.score)或者Integer.compareTo。虽然日常写代码遇到溢出的概率不大但知道了心里踏实一些。有序的 Set到底是什么意思学完这三个 Set 实现之后我有一段时间对有序这个概念很混乱。因为 LinkedHashSet 和 TreeSet 都说自己是有序的但它们的有序完全不是一回事。后来我是这么理解的LinkedHashSet 的有序是按插入顺序。你先加什么遍历的时候就先出什么。跟元素本身的值大小没关系。TreeSet 的有序是按值排序。不管你怎么加存进去之后再遍历元素一定是按从小到大或者你指定的 Comparator 规则的顺序输出。这两个有序面对的是完全不同的需求。你想保留操作顺序比如用户操作日志的去重展示用 LinkedHashSet。你需要元素自动排序比如成绩排行榜的去重用 TreeSet。我当时拿两个例子对比了一下思路就清楚了// LinkedHashSet——保留插入顺序LinkedHashSetStringlhsnewLinkedHashSet();lhs.add(C);lhs.add(A);lhs.add(B);System.out.println(lhs);// [C, A, B]// TreeSet——按值排序TreeSetStringtsnewTreeSet();ts.add(C);ts.add(A);ts.add(B);System.out.println(ts);// [A, B, C]同样的添加顺序两个 Set 输出的结果完全不一样。日常开发中常用的 Set 操作学完这三种 Set 之后我经常遇到的一个需求是在 Set 和 List 之间互相转换。比如从数据库查到的数据有重复先用 Set 去重再用 List 保持后续操作方便。Set 转 List 很简单把 Set 扔到 ArrayList 的构造方法里就行SetStringsetnewHashSet();// ... 加一些元素ListStringlistnewArrayList(set);反过来List 转 Set 也是同样的方式天然就去重了ListStringlistArrays.asList(a,b,a,c);SetStringsetnewHashSet(list);// [a, b, c]重复的去掉了如果你既要去重又要保留原来的顺序可以用 LinkedHashSetListStringlistArrays.asList(c,a,b,a,c);SetStringsetnewLinkedHashSet(list);// [c, a, b]去重且保持首次出现的顺序这个技巧我后来写代码的时候经常用尤其是在处理用户输入或者外部数据的时候。还有一个常用的操作是判断某个元素在不在 Set 里用contains方法。HashSet 的 contains 跟 HashMap 的 get 一样快O(1) 就能出结果。这个特性在某些场景下比 List 的 contains 好用得多——List 的 contains 是 O(n)要挨个比一遍。实际开发中怎么选学完之后我给自己整理了一个选择思路。如果只需要去重不需要顺序用 HashSet。这是最常用的情况性能也最好。HashSet 的查找、插入和删除操作在理想情况下都是 O(1)跟 ArrayList 的随机访问一样快。如果需要去重同时保留添加顺序用 LinkedHashSet。适合保留操作痕迹的场景比如关键词历史记录、操作日志。它的操作跟 HashSet 基本相同只是多维护了一条链表大部分操作仍然是 O(1)但常数项稍大一点。如果需要去重同时元素要自动排序用 TreeSet。适合排行榜、按序展示的去重数据。不过要注意 TreeSet 的插入和查找是 O(log n)比 HashSet 的 O(1) 慢一些。如果数据量很大而且不需要排序不要因为 TreeSet 看起来很酷就用它。还有一点容易忽略的是线程安全。HashSet、LinkedHashSet 和 TreeSet 都不是线程安全的。如果多个线程同时读写同一个 Set需要自己在外面加锁或者用 Collections.synchronizedSet 包装一下。Java 也提供了 CopyOnWriteArraySet 作为线程安全的 Set 实现它的底层是 CopyOnWriteArrayList适合读多写少的场景。另外还有一个选择标准数据量。如果数据量特别大HashSet 的性能优势会更明显。TreeSet 的插入成本比 HashSet 高因为红黑树的平衡操作有开销每次插入和删除都可能触发节点旋转和变色。LinkedHashSet 介于两者之间它的插入和 HashSet 一样快只是多了一点维护链表的指针操作。还有一个不太起眼但实际用得上的区别HashSet 的迭代顺序是不确定的甚至同一个 HashSet 在 JDK 不同版本下迭代顺序都可能不一样。所以如果你写了依赖 HashSet 迭代顺序的代码换了个 JDK 版本可能就跑出不同的结果了。但大多数时候数据量没大到需要纠结这个程度。我个人的习惯是默认用 HashSet有顺序需求再考虑另外两个。最后写这篇的时候我想起来学 Set 那几天我最大的困惑其实是为什么要有这么多 Set。后来想明白了不同的需求对应不同的实现没有哪个是最好的只有哪个最适合你当前的场景。如果你只需要去重HashSet 足够了。如果还想要顺序在 LinkedHashSet 和 TreeSet 之间选一个——先想清楚你要的是插入顺序还是值排序选错了用起来会很别扭。