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

举报
喵手 发表于 2025/04/29 10:43:00 2025/04/29
【摘要】 开篇语哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云/阿里云/华为云/51CTO;欢迎大家常来逛逛  今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。  我是一名后端开发爱好者,工作日常接触到最多的就是Java语言啦,所以我都尽量抽业余时间把自己所学到所会的,通过文章的形式进行输出,...

开篇语

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

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

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

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

前言

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

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

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 的对比

特性 HashSet TreeSet
底层实现 哈希表(HashMap) 红黑树(Red-Black Tree)
元素顺序 无序,元素的顺序不可预测 有序,元素按自然顺序或指定比较器排序
时间复杂度 O(1)(查找、插入、删除,平均情况下) O(log n)(查找、插入、删除)
是否允许重复 不允许重复元素 不允许重复元素
使用场景 需要去重且不关心元素顺序的情况 需要去重并且按顺序访问元素的情况

4. 总结

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

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

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

… …

文末

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

… …

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

wished for you successed !!!


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

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


版权声明:本文由作者原创,转载请注明出处,谢谢支持!

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。