Set 去重效率对比：HashSet、LinkedHashSet 和 TreeSet，到底谁是“去重之王”？

开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

  今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

  我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言

嘿，你是不是也在纠结，为什么Set集合能够做到“去重”呢？它到底是怎么在代码的世界里悄悄把重复的元素清除掉的？
但是等你开始思考时，HashSet、LinkedHashSet、TreeSet这三个“兄弟”又在你面前晃悠了，它们各自背后隐藏的秘密太多，到底哪个才是去重效率之最呢？

别担心，今天我就带你深入剖析这三种集合的背后故事。就让我们一起，探索一下它们在去重时的底层结构、效率和使用场景，最后给你一个明确的答案！

---

一、基础知识：Set 集合如何做到“去重”？

首先，咱们来了解一下，Set为什么能去重。

Set 接口的设计保证了其中的元素是唯一的。如果你把一个已存在的元素再次加入到 Set 中，它会自动忽略重复元素，这样就达到了“去重”的目的。

但为什么这三种 Set 看起来差不多，但在底层结构和效率上却有所不同呢？我们得先从它们的“根基”开始。

---

二、三兄弟的背景：底层结构和设计理念

1. HashSet：基于哈希表的集合

• 底层结构：HashSet 底层使用了 哈希表（HashMap），也就是说它通过计算元素的哈希值（hashCode()）来决定元素存储的位置。
• 去重原理：HashSet 会通过计算元素的哈希值来判断是否已存在相同元素。由于哈希表的特性，如果两个元素的哈希值相同（哈希冲突），那么它们就会被存放在同一个桶里，进一步通过 equals() 方法来确认是否是同一个元素。
• 时间复杂度：查找、添加、删除的时间复杂度平均是 O(1)，但是在极端情况下，如果发生大量哈希冲突，可能会退化为 O(n)。

2. LinkedHashSet：保留插入顺序的 HashSet

• 底层结构：LinkedHashSet 继承自 HashSet，在 HashSet 的基础上增加了一个 双向链表，来保持元素的插入顺序。
• 去重原理：与 HashSet 相同，LinkedHashSet 使用哈希表来存储元素，去重原理也一样。唯一不同的是，它还会维护一个链表来记录元素的插入顺序。
• 时间复杂度：由于多了链表结构，性能略低于 HashSet，但是在查找和添加元素时依然保持 O(1)。

3. TreeSet：基于红黑树的有序集合

• 底层结构：TreeSet 基于 红黑树 实现，红黑树是一种自平衡的二叉搜索树，能够保证数据的有序性。
• 去重原理：TreeSet 通过 compareTo() 或 compare() 方法来判断元素是否相等（即去重）。它不仅去重，还保证元素按自然顺序或指定顺序排列。
• 时间复杂度：由于是红黑树，插入、删除、查找的时间复杂度是 O(log n)，这比 HashSet 和 LinkedHashSet 慢。

---

三、效率对比：谁才是去重的“王者”？

让我们通过实际代码和对比分析，看看这三种 Set 在不同场景下的表现：

1. 时间效率对比：基础去重测试

我们先做一个简单的去重测试，看看这三者在大规模数据处理时的性能表现。

测试场景：

• 插入 100,000 个随机数字；
• 测试去重效率。

import java.util.*;

public class SetEfficiencyTest {
    public static void main(String[] args) {
        int size = 100000;

        // 生成随机数
        Random random = new Random();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            numbers.add(random.nextInt(size));
        }

        // HashSet
        long startTime = System.nanoTime();
        Set<Integer> hashSet = new HashSet<>(numbers);
        long endTime = System.nanoTime();
        System.out.println("HashSet去重耗时：" + (endTime - startTime) + "ns");

        // LinkedHashSet
        startTime = System.nanoTime();
        Set<Integer> linkedHashSet = new LinkedHashSet<>(numbers);
        endTime = System.nanoTime();
        System.out.println("LinkedHashSet去重耗时：" + (endTime - startTime) + "ns");

        // TreeSet
        startTime = System.nanoTime();
        Set<Integer> treeSet = new TreeSet<>(numbers);
        endTime = System.nanoTime();
        System.out.println("TreeSet去重耗时：" + (endTime - startTime) + "ns");
    }
}

运行结果（典型情况）：

HashSet去重耗时：2300000ns
LinkedHashSet去重耗时：2600000ns
TreeSet去重耗时：3500000ns

结论：

• HashSet：去重速度最快，时间复杂度 O(1)，非常适合大规模数据去重。
• LinkedHashSet：比 HashSet 慢一点，因为它需要维护插入顺序，但差距不大，时间复杂度 O(1)。
• TreeSet：去重效率最慢，时间复杂度 O(log n)，因为它需要保证元素的有序性。

---

四、使用场景：根据需求选择

那么，哪种 Set 更适合你的应用呢？下面是一些常见的使用场景，你可以根据需求选择：

1. HashSet：超高速去重，随便用

• 场景：你需要快速去重，并且不在乎元素的顺序。比如，大数据量的无序去重、缓存处理等。
• 优势：速度最快，查找和添加都很快，适合对性能要求高的场景。

2. LinkedHashSet：去重+顺序，完美的插入顺序

• 场景：你需要保持元素的插入顺序同时去重。比如，记录用户输入的历史记录，需要保证顺序。
• 优势：保持元素插入的顺序，性能稍慢于 HashSet，但依然较快。

3. TreeSet：去重+排序，保持有序性

• 场景：你需要去重同时又需要保持元素的排序。比如，处理一些需要排序的集合数据，像优先级队列。
• 优势：去重并且元素有序，适用于需要排序的场景，但性能较差。

---

五、总结：谁才是去重的“王者”？

• 如果你只关心去重速度，而不关心元素的顺序和排序，HashSet 无疑是最佳选择。
• 如果你需要保持插入顺序，那么 LinkedHashSet 是一个不错的选择，虽然性能稍微逊色于 HashSet，但依然高效。
• 如果你需要有序集合，并且可以接受一定的性能开销，TreeSet 将是你的最佳选择。

总结语：

“做去重，就像做饭，手上有很多工具，选对工具，效率飞起，选错工具，慢慢就成了“水煮三小时”的烦恼。”
对了！在大数据量的去重操作中，别忘了优先考虑 HashSet，因为它的速度简直是“秒杀”对手啊！

… …

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

… …

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

---

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。

---

版权声明：本文由作者原创，转载请注明出处，谢谢支持！