「Java 进阶之路」系列 Day24写在前面这三个Set实现类经常被放在一起问选型但很多人不知道的是——它们其实都不是从零实现的底层都是套用了前面讲过的Map实现。这篇把这层套壳关系讲清楚选型问题自然就迎刃而解了。一、是什么三者底层分别套的是哪个 MapHashSet内部持有一个HashMapadd进来的元素作为keyvalue统一是一个固定的Object占位常量HashSet内部就是一个HashMap调用add(e)本质是执行map.put(e, PRESENT)PRESENT是一个共享的固定占位对象Day22 讲过的HashMap底层结构、扩容机制HashSet全盘照搬。LinkedHashSet继承自HashSet内部套的是LinkedHashMap——在HashMap基础上多维护了一条双向链表记录元素的插入顺序或者访问顺序取决于构造参数。TreeSet内部套的是TreeMap底层是红黑树元素按照自然顺序实现Comparable或者传入的Comparator规则自动排序。一句话理解三者的选型逻辑HashSet只关心去重、不关心顺序LinkedHashSet在去重的基础上还想要记住插入顺序TreeSet在去重的基础上还想要元素始终有序排列。二、为什么需要三种顺序需求不同天然对应不同底层结构底层结构是否有序add/contains 时间复杂度HashSetHashMap数组链表/红黑树无序遍历顺序取决于哈希分布不能依赖O(1)LinkedHashSetLinkedHashMapHashMap双向链表有序按插入顺序排列O(1)比HashSet多一点链表维护的开销TreeSetTreeMap红黑树有序按排序规则自动排列O(log n)为什么TreeSet的操作是O(log n)而不是O(1)红黑树是一种自平衡二叉搜索树插入、查找都需要沿着树的层级往下比较操作耗时和树的高度成正比树的高度是O(log n)级别天然比数组链表这种结构慢一些——这是始终保持有序必须付出的代价天下没有免费的午餐。三、怎么用两个容易踩的坑坑一往 TreeSet 里放自定义对象忘了告诉它怎么排序classPerson{Stringname;intage;Person(Stringname,intage){this.namename;this.ageage;}}SetPersonsetnewTreeSet();set.add(newPerson(Tom,20));// 运行时抛出ClassCastExceptionTreeSet要维护有序性每次插入都要知道新元素和已有元素比谁大谁小如果元素本身没有实现Comparable接口、构造TreeSet时也没传Comparator它压根不知道该怎么比较运行时直接抛出ClassCastException。正确做法是让Person实现ComparablePerson或者构造时传入一个ComparatorPersonSetPersonsetnewTreeSet(Comparator.comparingInt(p-p.age));坑二TreeSet 判断重复靠的是 compareTo不是 equals/hashCode这是最容易被面试问倒的细节——HashSet判断两个元素是否重复用的是Day20讲过的equalshashCode那套机制但TreeSet完全不看这两个方法它认为比较结果为0的两个元素就是重复的classPersonimplementsComparablePerson{Stringname;intage;Person(Stringname,intage){this.namename;this.ageage;}OverridepublicintcompareTo(Persono){returnInteger.compare(this.age,o.age);// 只按年龄比较}// 没有重写equals/hashCode用的是Object默认的比较引用地址}SetPersonsetnewTreeSet();set.add(newPerson(Tom,20));set.add(newPerson(Jerry,20));// 年龄一样compareTo返回0System.out.println(set.size());// 1Jerry被当成重复元素直接丢弃了尽管equals认为他们不是同一个人Tom和Jerry是两个完全不同的人equals按引用判断显然不相等但因为compareTo只比较了age、两人年龄一样TreeSet认为这是重复元素第二次add直接被无声丢弃。这条规则的官方说法是compareTo应该和equals保持一致如果不一致TreeSet/TreeMap的行为会和equals定义的相等语义产生偏差实际写compareTo的时候一定要想清楚这个排序规则是不是也隐含了判断两个对象是否算作同一个的语义如果不是就要在比较逻辑里加上足够多的字段来避免误判比如年龄相同再比较姓名姓名也相同再退化成用某个唯一id兜底。四、面试追问Q1HashSet、LinkedHashSet、TreeSet 底层分别是基于什么实现的HashSet内部持有一个HashMap元素作为key存进去LinkedHashSet继承自HashSet内部换成了LinkedHashMap多维护一条双向链表记录插入顺序TreeSet内部持有一个TreeMap底层是红黑树按照排序规则自动排列元素。Q2为什么说 HashSet 是无序的实际测试时看到的遍历顺序是随机的吗不是真正随机遍历顺序完全由元素哈希值落在哪个桶、以及桶内链表/树的组织方式决定同样的元素、同样的插入顺序多次运行结果通常是一致的。但这个顺序不是插入顺序也不保证在不同JDK版本、不同哈希值分布下保持稳定所以不能依赖这个顺序做任何业务逻辑需要保证遍历顺序应该用LinkedHashSet。Q3往 TreeSet 里添加没有实现 Comparable 的自定义对象会发生什么如果构造TreeSet时也没有传入Comparator运行时调用add会抛出ClassCastException。因为TreeSet需要在插入时确定新元素和已有元素的大小关系来维持有序性如果元素既没实现Comparable、又没有外部传入的比较规则它没有任何依据去做这个比较。Q4TreeSet 是怎么判断两个元素是否重复的和 HashSet 一样吗不一样。HashSet依赖equals和hashCode判断重复TreeSet依赖compareTo或者传入的Comparator的比较结果只要两个元素比较结果是0就会被认为是重复元素即使它们的equals判断并不相等后添加的那个也会被无声丢弃。这也是为什么写compareTo时要注意让排序逻辑和相等的业务语义保持一致避免出现这种和直觉不符的丢弃行为。Q5TreeSet 的操作为什么比 HashSet 慢具体慢在哪个环节TreeSet底层是红黑树插入、查找、删除都需要沿着树的高度逐层比较时间复杂度是O(log n)HashSet底层是哈希表正常情况下直接通过哈希值定位到桶时间复杂度接近O(1)。TreeSet慢的代价换来的是元素始终保持有序这个HashSet不具备的能力如果不需要排序HashSet的性能通常更好。下一篇预告Day25 讲Iterator与fail-fast机制——为什么用普通for循环遍历集合时删除元素会抛异常Iterator自己删除又为什么没事。