HashSet 与 TreeSet 的底层实现原理，差别竟然这么大？

开篇语

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

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

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

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

前言

说到 HashSet 和 TreeSet，很多人可能都会习惯性地认为它们是差不多的：都是 Set 的实现类，都会去重、不允许重复元素。但如果你真这么认为，那你可就大错特错了！在它们的底层实现上，HashSet 和 TreeSet 其实差异巨大，理解它们的实现原理，能帮助你在开发中做出更精准的选择，避免踩坑。

今天就让我们来深入探讨一下 HashSet 和 TreeSet 的底层实现原理，拆解它们是如何高效地操作数据的，别眨眼哦！

1. HashSet 的底层实现

1.1 HashSet 的实现结构

HashSet 是基于 哈希表（HashMap） 实现的。它内部实际使用的是一个 HashMap，并通过 HashMap 的 键（key）来存储元素，值（value）则是一个固定的常量对象。每次向 HashSet 添加元素时，都会通过元素的哈希值来决定存储的位置。

• 底层结构：HashSet 实际上是一个封装了 HashMap 的集合，所有元素都作为 HashMap 的键来存储，而值都是一个固定的常量 PRESENT（即一个占位符）。

1.2 哈希冲突处理

• 哈希冲突：当不同的元素有相同的哈希值时，它们会被存储在同一个桶里，HashSet 会使用链表或红黑树来解决哈希冲突。
  • 如果冲突的元素较少，HashMap 会采用链表结构。
  • 如果冲突的元素过多，HashMap 会将链表转换为红黑树，以提高查询效率。

1.3 HashSet 的操作流程

1. 添加元素：HashSet 会计算元素的哈希值，然后通过哈希值决定元素的存储位置。如果该位置没有元素，则直接插入；如果该位置已经有元素，使用链表或红黑树来处理冲突。

2. 查找元素：通过计算元素的哈希值，快速定位元素所在的桶，再通过桶内的链表或红黑树来查找具体的元素。

3. 删除元素：同样先定位元素所在的桶，再删除链表或红黑树中的节点。

1.4 优点与缺点

• 优点：查询、插入和删除操作的时间复杂度平均为 O(1)，在没有哈希冲突的情况下非常高效。
• 缺点：元素的顺序不保证，无法按照插入顺序或任何其他顺序遍历集合。

1.5 使用示例

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // 添加重复元素不会生效

        for (String fruit : set) {
            System.out.println(fruit);  // 输出顺序不确定
        }
    }
}

2. TreeSet 的底层实现

2.1 TreeSet 的实现结构

TreeSet 是基于 红黑树（Red-Black Tree） 实现的。红黑树是一种自平衡的二叉搜索树，能保证数据的有序性，支持高效的查找、插入和删除操作。

• 底层结构：TreeSet 通过红黑树来存储元素，树中的每个节点存储一个元素，节点之间通过父子关系和树的平衡规则进行连接。

2.2 红黑树的性质

红黑树是一种平衡的二叉搜索树，它的核心特点是：

• 每个节点要么是红色的，要么是黑色的。
• 根节点是黑色的。
• 叶节点是黑色的（NIL）。
• 每个红色节点的子节点必须是黑色的（即没有两个红色节点相邻）。
• 从任一节点到其所有叶子节点的路径上，必须包含相同数量的黑色节点。

这些特性保证了红黑树的平衡性，使得查找、插入、删除操作的时间复杂度始终为 O(log n)。

2.3 TreeSet 的操作流程

1. 添加元素：TreeSet 会将元素插入到红黑树中，按照元素的自然顺序或者指定的比较器顺序进行排序。

2. 查找元素：通过红黑树的查找算法，能够以 O(log n) 的时间复杂度找到指定的元素。

3. 删除元素：同样，删除元素时，红黑树会进行旋转操作来保持平衡，确保操作的时间复杂度为 O(log n)。

2.4 优点与缺点

• 优点：TreeSet 保证元素有序，支持根据元素的顺序进行遍历，时间复杂度是 O(log n)，比哈希表结构的 HashSet 稍慢。
• 缺点：由于需要维护红黑树的平衡，插入和删除操作的性能相对较差。

2.5 使用示例

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // 添加重复元素不会生效

        for (String fruit : set) {
            System.out.println(fruit);  // 输出：Apple, Banana，按照自然顺序排序
        }
    }
}

3. HashSet 与 TreeSet 的对比

4. 总结

• HashSet：基于哈希表实现，适用于那些不关心元素顺序、需要高效查找、插入和删除的场景。它的查询、插入和删除操作通常是常数时间复杂度，但不保证顺序。

• TreeSet：基于红黑树实现，适用于需要保证元素有序的场景。它的查询、插入和删除操作的时间复杂度为 O(log n)，但能保证元素按照顺序排列。

选择哪个，取决于你是否需要元素排序以及性能需求。理解了它们的底层实现原理，你就能在项目中更加高效地选择和应用这些集合类。

… …

文末

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

… …

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

wished for you successed ！！！

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

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

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