HashSet与TreeSet底层原理深度解析！-北京尧图网络

全文目录开篇语摘要一、HashSet表面是 Set内心其实是个 HashMap1.1 先别被骗了HashSet 其实是“借壳上市”1.2 HashSet 如何判重—— hashCode equals 双保险1.3 HashSet 的性能增删查改到底多快1.4 一个直观的 HashSet 例子二、TreeSet自带排序功能的“有序集合”2.1 TreeSet 底层不是树自己而是 TreeMap2.2 TreeSet 的排序机制自然排序 vs 自定义 Comparator✅ 方式一自然排序元素自己实现 Comparable✅ 方式二自定义 Comparator外部指定排序规则2.3 TreeSet 的时间复杂度2.4 TreeSet 特有的一些“好用小技能”三、HashSet vs TreeSet到底该选谁四、收个尾别再把 Set 当“会去重的 List”用了文末开篇语哈喽各位小伙伴们你们好呀我是喵手。运营社区C站/掘金/腾讯云/阿里云/华为云/51CTO欢迎大家常来逛逛今天我要给大家分享一些自己日常学习到的一些知识点并以文字的形式跟大家一起交流互相学习一个人虽可以走的更快但一群人可以走的更远。我是一名后端开发爱好者工作日常接触到最多的就是Java语言啦所以我都尽量抽业余时间把自己所学到所会的通过文章的形式进行输出希望以这种方式帮助到更多的初学者或者想入门的小伙伴们同时也能对自己的技术进行沉淀加以复盘查缺补漏。小伙伴们在批阅的过程中如果觉得文章不错欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持摘要说实话刚学 Java 集合那会儿我对Set的理解就一句话“不重复的一堆东西”。简单粗暴也确实没错。但等到真的写业务、排 Bug、优化性能的时候你会发现——“这俩家伙到底怎么保证不重复啊为啥 HashSet 乱序TreeSet 却是排好序的插个 null 行不行性能差多少”今天咱就把HashSet和TreeSet这两位拆开了讲讲不搞玄学全是底层逻辑代码示例让你看完之后不仅知道“怎么用”还知道“为啥这么用”。一、HashSet表面是 Set内心其实是个 HashMap1.1 先别被骗了HashSet 其实是“借壳上市”HashSet自己几乎不干什么复杂的事它的大部分数据存储逻辑直接丢给了HashMap来完成。源码里最关键的一行简化理解就是publicclassHashSetEimplementsSetE,Cloneable,java.io.Serializable{privatetransientHashMapE,Objectmap;// 所有 key 对应的 value 都是同一个哑元对象privatestaticfinalObjectPRESENTnewObject();publicHashSet(){mapnewHashMap();}publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;}publicbooleancontains(Objecto){returnmap.containsKey(o);}publicbooleanremove(Objecto){returnmap.remove(o)!null;}}核心点HashSet内部用HashMap存东西元素值当作keyvalue统一用一个固定的对象PRESENT判重逻辑完全靠HashMap的key 唯一性保障一句话总结HashSet 只有 key 的 HashMapvalue 全是摆设。1.2 HashSet 如何判重—— hashCode equals 双保险要搞懂 HashSet 判重就得先看清HashMap的套路调用元素的hashCode()算出 hash 值用 hash 值定位到某个“桶”数组下标如果桶是空的直接放进去 ✅如果桶里已经有元素了先比较hash 值快速过滤一批再逐个比较equals()确认真正相等这就意味着只有当两个对象hashCode()相同且equals()返回 true 时HashSet 才认为它们是“重复元素”hashCode()实现不好会导致大量哈希冲突性能会大幅下降重写equals()一定要同时重写hashCode()不然会出大问题看起来相等却加了两份来看个经典小坑例子classUser{Stringname;intage;User(Stringname,intage){this.namename;this.ageage;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(!(oinstanceofUser))returnfalse;Useruser(User)o;returnageuser.ageObjects.equals(name,user.name);}// ❌ 故意不重写 hashCode()}publicstaticvoidmain(String[]args){SetUsersetnewHashSet();set.add(newUser(Tom,18));set.add(newUser(Tom,18));System.out.println(set.size());// 可能是 2而不是你期望的 1}因为没重写hashCode()两个“长得一模一样”的User对象hash 值可能不同直接跑去不同的桶里HashSet 完全不知道它们应该算“一个人”。正确写法应该是OverridepublicinthashCode(){returnObjects.hash(name,age);}1.3 HashSet 的性能增删查改到底多快理论上HashSet大部分操作的时间复杂度操作理论平均复杂度说明add(E e)O(1)假设哈希分布均匀冲突少contains(Object o)O(1)用hashCodeequals判定remove(Object o)O(1)定位桶后从链或树中删除遍历O(n)对内部结构顺序无保证注意两点最坏情况下可能退化到 O(n)如果 hash 全撞一个桶里比如 hashCode 实现奇葩JDK 8 之后当链表太长会转为红黑树降低最坏复杂度到 O(log n)但树化也有开销HashSet 不保证顺序插入顺序不保证排序顺序更不存在想要有插入顺序请用LinkedHashSet1.4 一个直观的 HashSet 例子SetStringsetnewHashSet();set.add(Java);set.add(Python);set.add(Java);// 重复System.out.println(set);// [Java, Python]顺序不一定System.out.println(set.size());// 2System.out.println(set.contains(Java));// true你看到的只是“有 or 没有”在底层它大概干了这些事每次add(Java)都算 hash → 找桶 → 查当前桶中是否存在“同样 equals 的元素”存在则拒绝添加不存在才放进去二、TreeSet自带排序功能的“有序集合”2.1 TreeSet 底层不是树自己而是 TreeMap跟 HashSet 一样TreeSet也走了一条“站在别人肩膀上”的路线底层用的是TreeMap元素存在TreeMap的 key 里value 一样用一个哑元对象你大概可以把它想象成TreeSet 只有 key 的 TreeMap内部是红黑树结构。红黑树的好处天生有序按 key 排序插入、删除、查找都是O(log n)2.2 TreeSet 的排序机制自然排序 vs 自定义 ComparatorTreeSet最大的卖点就是它是“有序集合”。那问题来了按什么排序谁说了算TreeSet 有两种排序方式✅ 方式一自然排序元素自己实现 Comparable只要元素实现了Comparable接口那么它就有“天然的排序规则”比如String按字典序Integer从小到大LocalDate按日期排序SetIntegersetnewTreeSet();set.add(5);set.add(1);set.add(3);System.out.println(set);// [1, 3, 5]已经自动有序如果你写自己的类classUserimplementsComparableUser{Stringname;intage;User(Stringname,intage){this.namename;this.ageage;}OverridepublicintcompareTo(Userother){// 按年龄从小到大排相等则按名字排intrInteger.compare(this.age,other.age);if(r!0)returnr;returnthis.name.compareTo(other.name);}OverridepublicStringtoString(){returnname(age);}}publicstaticvoidmain(String[]args){SetUserusersnewTreeSet();users.add(newUser(Tom,18));users.add(newUser(Jerry,16));users.add(newUser(Mary,18));System.out.println(users);// [Jerry(16), Tom(18), Mary(18)]}这里特别重要的一点在TreeSet眼里“重复元素” 的判断是基于compareTo/Comparator返回 0而不是基于equals。也就是说如果compareTo返回 0 但equals是 false那TreeSet仍然会认为它们是“同一个元素”不会再存第二份。✅ 方式二自定义 Comparator外部指定排序规则如果你不想或者不能修改类本身比如第三方类那就可以在构造TreeSet的时候传入一个Comparator来指定排序规则。例子按字符串长度排序如果长度相同再按字典序SetStringsetnewTreeSet((a,b)-{intrInteger.compare(a.length(),b.length());if(r!0)returnr;returna.compareTo(b);});set.add(java);set.add(c);set.add(python);set.add(go);set.add(rust);System.out.println(set);// [c, go, java, rust, python]// 先按长度从小到大再按字典序这种方式的特点是一个集合可以随构造时的 Comparator 决定排序方式同一个类型可以在不同的TreeSet中用不同的排序逻辑2.3 TreeSet 的时间复杂度TreeSet基于红黑树结构每次插入都会根据compareTo/Comparator一路从根节点比较下去找到插入位置做红黑树的“旋转染色”等平衡操作因此时间复杂度操作时间复杂度add(E e)O(log n)contains(Object o)O(log n)remove(Object o)O(log n)遍历升序O(n)相比之下HashSet 在散列均匀时是平均 O(1)但是无序TreeSet 操作偏慢一点log n但带来的是天然排序可做范围查询2.4 TreeSet 特有的一些“好用小技能”由于 TreeSet 是基于NavigableSet的你可以做很多“按顺序检索”的事情TreeSetIntegersetnewTreeSet();set.add(10);set.add(5);set.add(20);set.add(15);System.out.println(set);// [5, 10, 15, 20]System.out.println(set.first());// 5System.out.println(set.last());// 20System.out.println(set.lower(15));// 10 15 最大的System.out.println(set.floor(15));// 15 15 最大的System.out.println(set.higher(15));// 20 15 最小的System.out.println(set.ceiling(15));// 15 15 最小的System.out.println(set.subSet(10,20));// [10, 15)左闭右开System.out.println(set.subSet(10,true,20,true));// [10, 15, 20]这些方法在做区间查找、范围过滤、排序数据分析等场景特别好用HashSet是完全做不到的。三、HashSet vs TreeSet到底该选谁我们来拉个对照表一眼看穿它俩的定位对比项HashSetTreeSet底层结构HashMap数组链表/红黑树TreeMap红黑树元素是否有序❌ 无序✅ 有序自然顺序或 Comparator判重依据hashCodeequalscompareTo/Comparator返回 0增删查复杂度平均O(1)最坏 O(n)O(log n)是否支持范围查询❌ 不支持✅ 支持subSet、headSet、tailSet 等适用场景只关心“有没有”不在意顺序追求性能需要有序集合、按范围检索、按排序输出是否允许 null通常允许 1 个 null取决于实现与版本通常不建议/不允许 null比较时会 NPE一句话总结选择建议只要你不关心顺序、只在乎“有没有” → 用 HashSet只要你想要“有序的 Set”、范围查询、排序输出 → 用 TreeSet如果你既想要顺序又想要接近 O(1) 插入查找 → 可以看看LinkedHashSet或配合其他结构四、收个尾别再把 Set 当“会去重的 List”用了很多人刚开始写 Java 的时候对Set的理解就是“我有一堆数据想去重就丢到 Set 里再拿出来。”——这没错但如果你一直只这么用那就有点可惜了。HashSet代表的是高效的、不关心顺序的“元素去重查找”结构TreeSet代表的是有序的、可做区间操作的“排序集合”下一次你再写业务逻辑时不如问问自己一句“我现在要的是纯粹的去重还是其实还偷偷想要‘排序’和‘范围操作’”… …文末好啦以上就是我这期的全部内容如果有任何疑问欢迎下方留言哦咱们下期见。… …学习不分先后知识不分多少事无巨细当以虚心求教三人行必有我师焉wished for you successed ⭐️若喜欢我就请关注我叭。⭐️若对您有用就请点赞叭。⭐️若有疑问就请评论留言告诉我叭。版权声明本文由作者原创转载请注明出处谢谢支持

HashSet与TreeSet底层原理深度解析！

相关推荐

Maven 从入门到实战：项目管理与构建工具完全指南

impress.js 演讲者控制台（impressConsole）插件实战指南：P 键唤起、演讲备注与双屏导航

SVN 版本控制从入门到实战：安装、配置与日常使用指南

更多资讯

段式内存管理地址变换与越界检查：课堂练习4.1复盘

基于YOLOv8的舰船目标检测系统：从数据集标注到PyQt5界面集成

JMeter实战入门：以飞致云平台为靶标快速掌握接口测试核心技能

Mac读写NTFS移动硬盘的三种实用方案：从驱动到exFAT

逐行拆解one-skill-to-rule-them-all的bash脚本：ID推导、归档扫描，以及你必须防住的三种静默失败

银河麒麟v10 SP1安装Docker：前置问题、内核参数与离线部署指南

今日更新

MATLAB+Yalmip+CPLEX实战：综合能源系统优化调度全流程解析

I3C比I2C快10倍？RK3576实战：速率、DTS配置与混合总线避坑指南

字符串转对象：JSON.parse、new Function与URLSearchParams

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？