正在准备互联网大厂 Java 开发面试的小伙伴们，是不是也被这道题难住过：“请简述 HashSet 与 TreeSet 的区别与联系？” 要是回答得不够全面，很可能就与心仪的 offer 失之交臂！别慌，今天就带大家通过剖析源码，全方位攻克这一面试难题。

HashSet 与 TreeSet：面试常客

在 Java 开发领域，HashSet 和 TreeSet 堪称最常用的集合类，也是大厂面试的高频考点。面试官通过这类题目，不仅考查求职者对基础知识的掌握程度，更看重其能否将知识灵活运用到实际开发场景中。虽说 HashSet 和 TreeSet 都实现了 Set 接口，但它们在原理、特性和应用场景上，有着天壤之别。

特性大揭秘：无序与有序的碰撞

存储顺序：无序与有序的分野

HashSet 就像一个杂乱无章的储物箱，是无序的。从源码来看，HashSet 底层由 HashMap 实现，其 add 方法本质上是调用 HashMap 的 put 方法。在 HashMap 里，元素的存储位置由哈希值和容量经过特定算法计算得出，这就导致添加元素的顺序和遍历输出的顺序不一致。举个例子，大家依次向 HashSet 中添加数字 1、2、3，遍历输出时，顺序可能变成 2、3、1。

public HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{ static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT)==null; }}

TreeSet 则像一个精心整理的书架，所有书籍都按特定顺序摆放，是有序的。TreeSet 底层基于 TreeMap 实现，TreeMap 是一个自平衡的二叉搜索树，默认按元素的自然顺序排列，当然，也能通过自定义比较器定制排序规则。以向 TreeSet 添加元素为例，实际上是调用 TreeMap 的 put 方法，TreeMap 会根据元素的大小或自定义的比较规则，将元素插入到合适的位置，确保集合有序。

public TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{ private transient NavigableMap<E,Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public TreeSet() { this(new TreeMap<>()); } public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } public boolean add(E e) { return m.put(e, PRESENT)==null; }}

底层实现：哈希表与红黑树的较量

HashSet 底层基于哈希表实现，哈希表本质上是一个数组加链表（在 JDK1.8 后，链表长度超过 8 时会转化为红黑树）的数据结构。当我们向 HashSet 中添加元素时，首先会计算元素的哈希值，通过哈希值与数组长度进行取模运算，得到元素在数组中的存储位置。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //后续处理哈希冲突 } //省略部分代码 return null;}

上述代码展示了 HashMap 的 putVal 方法，当计算出的位置为空时，直接将新元素放入该位置；若该位置已有元素，就会发生哈希冲突，此时会通过链表或红黑树来解决冲突。在查找元素时，同样先计算哈希值定位到数组位置，再遍历链表或红黑树，快速找到目标元素，这种特性让 HashSet 在海量数据处理时查找效率超高。

TreeSet 底层基于红黑树实现，这种数据结构保证了元素的有序性。不过，在插入和删除操作时，比 HashSet 复杂一些。因为红黑树在插入和删除元素后，需要通过旋转和变色等操作，重新平衡树结构，以维持其有序性和平衡性。比如，在向 TreeSet 插入一个新元素时，TreeMap 会执行一系列操作确保树的平衡，这也导致 TreeSet 的插入操作相对耗时。

public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; //后续确定插入位置和平衡树结构}

在上述代码中，TreeMap 会根据元素大小或自定义比较规则，找到合适的插入位置。插入完成后，通过左旋、右旋和变色等操作，维持红黑树的平衡，保证元素有序。不过，这些操作也使得 TreeSet 在插入和删除时，比 HashSet 复杂，消耗更多时间。

数据唯一性保证机制

HashSet 判断元素唯一性时，先计算元素的哈希值，若哈希值不同，直接认定为不同元素；若哈希值相同，再通过 equals 方法进一步比较。这意味着，要正确使用 HashSet，需合理重写 hashCode 和 equals 方法，否则可能出现重复元素。

TreeSet 则通过比较元素大小来保证唯一性。若两个元素比较结果为 0，TreeSet 会认为它们相同，不会重复添加。因此，使用 TreeSet 时，元素需实现 Comparable 接口，或者在创建 TreeSet 时提供自定义比较器。

迭代器特性

HashSet 的迭代器没有固定顺序，迭代过程依赖哈希表的存储结构。由于哈希表在扩容等操作时可能改变结构，因此 HashSet 的迭代器在迭代过程中，不支持对集合结构的修改，否则会抛出 ConcurrentModificationException 异常。

TreeSet 的迭代器按元素的排序顺序进行迭代，在迭代过程中，可以安全地删除当前迭代的元素，这得益于红黑树结构的稳定性。

适用场景

当应用场景需要快速查找和插入操作，且对元素顺序没有要求时，HashSet 是更好的选择，如缓存系统、数据去重等场景。当应用场景对元素顺序有严格要求，如实现排行榜、调度系统时，TreeSet 则更为合适，它能确保元素始终有序。

二、面试通关秘籍

当面试官抛出这道题时，咱们可以这样回答：首先点明二者都实现了 Set 接口，具备 Set 接口不允许重复元素的特性。比如，向 Set 集合中添加两个相同的元素，最终集合中只会保留一个。这一特性在 HashSet 和 TreeSet 的源码中，通过 Map 的键唯一性得以保证，毕竟 HashSet 和 TreeSet 底层分别基于 HashMap 和 TreeMap 实现。

接着，阐述二者在存储顺序、底层实现、数据唯一性保证机制、迭代器特性和适用场景等方面的差异，并举例说明。在处理需要快速查找的场景，如电商系统中查找商品信息，HashSet 更合适；在对元素顺序有要求的场景，如排行榜系统，TreeSet 更具优势。

要是面试官进一步追问，大家还能提到二者在性能方面的差异。HashSet 的插入、删除和查找操作平均时间复杂度为 O (1)，TreeSet 的这些操作时间复杂度为 O (log n)。这意味着，当数据量较小时，两者性能差异不明显；但当数据量庞大时，HashSet 在查找操作上的性能优势就会凸显出来，而 TreeSet 在需要有序遍历数据的场景中更胜一筹。

小伙伴们，掌握 HashSet 和 TreeSet 的区别，不仅能助力大家顺利通过面试，在实际开发中，合理选择这两种集合，还能显著提升程序的性能和效率。希望大家在学习和面试的过程中，对这类基础知识理解透彻，早日拿下心仪的大厂 offer！如果大家还有其他面试难题，欢迎在评论区留言讨论。