HashSet 和 TreeSet 到底啥来头？你真搞懂它们在背后偷偷干了什么吗？

开篇语

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

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

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

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

摘要

说实话，刚学 Java 集合那会儿，我对 Set 的理解就一句话：“不重复的一堆东西”。简单，粗暴，也确实没错。但等到真的写业务、排 Bug、优化性能的时候，你会发现——

“这俩家伙到底怎么保证不重复啊？为啥 HashSet 乱序，TreeSet 却是排好序的？插个 null 行不行？性能差多少？”

今天咱就把 HashSet 和 TreeSet 这两位拆开了讲讲，不搞玄学，全是底层逻辑 + 代码示例，让你看完之后，不仅知道“怎么用”，还知道“为啥这么用”。

一、HashSet：表面是 Set，内心其实是个 HashMap

1.1 先别被骗了：HashSet 其实是“借壳上市”

HashSet 自己几乎不干什么复杂的事，它的大部分数据存储逻辑，直接丢给了 HashMap 来完成。

源码里最关键的一行（简化理解）就是：

public class HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E, Object> map;
    // 所有 key 对应的 value 都是同一个哑元对象
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) != null;
    }
}

核心点：

• HashSet 内部用 HashMap 存东西
• 元素值当作 key
• value 统一用一个固定的对象 PRESENT
• 判重逻辑完全靠 HashMap 的 key 唯一性 保障

一句话总结：

HashSet = 只有 key 的 HashMap（value 全是摆设）。

1.2 HashSet 如何判重？—— hashCode + equals 双保险

要搞懂 HashSet 判重，就得先看清 HashMap 的套路：

1. 调用元素的 hashCode()，算出 hash 值

2. 用 hash 值定位到某个“桶”（数组下标）

3. 如果桶是空的，直接放进去 ✅

4. 如果桶里已经有元素了：

   • 先比较 hash 值（快速过滤一批）
   • 再逐个比较 equals()（确认真正相等）

这就意味着：

• 只有当两个对象 hashCode() 相同且 equals() 返回 true 时，HashSet 才认为它们是“重复元素”
• hashCode() 实现不好会导致大量哈希冲突，性能会大幅下降
• 重写 equals() 一定要同时重写 hashCode()，不然会出大问题（看起来相等却加了两份）

来看个经典小坑例子👇

class User {
    String name;
    int age;

    User(String name, int age) { this.name = name; this.age = age; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return age == user.age &&
                Objects.equals(name, user.name);
    }

    // ❌ 故意不重写 hashCode()
}

public static void main(String[] args) {
    Set<User> set = new HashSet<>();
    set.add(new User("Tom", 18));
    set.add(new User("Tom", 18));

    System.out.println(set.size()); // 可能是 2，而不是你期望的 1
}

因为没重写 hashCode()，两个“长得一模一样”的 User 对象，hash 值可能不同，直接跑去不同的桶里，HashSet 完全不知道它们应该算“一个人”。

正确写法应该是：

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

1.3 HashSet 的性能：增删查改到底多快？

理论上，HashSet 大部分操作的时间复杂度：

注意两点：

1. 最坏情况下可能退化到 O(n)

   • 如果 hash 全撞一个桶里（比如 hashCode 实现奇葩）
   • JDK 8 之后，当链表太长会转为红黑树，降低最坏复杂度到 O(log n)，但树化也有开销

2. HashSet 不保证顺序

   • 插入顺序？不保证
   • 排序顺序？更不存在
   • 想要有插入顺序请用 LinkedHashSet

1.4 一个直观的 HashSet 例子

Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // 重复

System.out.println(set);       // [Java, Python]（顺序不一定）
System.out.println(set.size()); // 2
System.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 自定义 Comparator

TreeSet 最大的卖点就是：它是“有序集合”。
那问题来了：按什么排序？谁说了算？

TreeSet 有两种排序方式：

✅ 方式一：自然排序（元素自己实现 Comparable）

只要元素实现了 Comparable 接口，那么它就有“天然的排序规则”，比如：

• String：按字典序
• Integer：从小到大
• LocalDate：按日期排序

Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);

System.out.println(set); // [1, 3, 5]，已经自动有序

如果你写自己的类：

class User implements Comparable<User> {
    String name;
    int age;

    User(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(User other) {
        // 按年龄从小到大排，相等则按名字排
        int r = Integer.compare(this.age, other.age);
        if (r != 0) return r;
        return this.name.compareTo(other.name);
    }

    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

public static void main(String[] args) {
    Set<User> users = new TreeSet<>();
    users.add(new User("Tom", 18));
    users.add(new User("Jerry", 16));
    users.add(new User("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 来指定排序规则。

例子：按字符串长度排序，如果长度相同再按字典序：

Set<String> set = new TreeSet<>(
        (a, b) -> {
            int r = Integer.compare(a.length(), b.length());
            if (r != 0) return r;
            return a.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 一路从根节点比较下去
• 找到插入位置
• 做红黑树的“旋转 + 染色”等平衡操作

因此，时间复杂度：

相比之下：

• HashSet 在散列均匀时是 平均 O(1)，但是 无序
• TreeSet 操作偏慢一点（log n），但带来的是 天然排序 + 可做范围查询

2.4 TreeSet 特有的一些“好用小技能”

由于 TreeSet 是基于 NavigableSet 的，你可以做很多“按顺序检索”的事情：

TreeSet<Integer> set = new TreeSet<>();
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()); // 5
System.out.println(set.last());  // 20

System.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：到底该选谁？

我们来拉个对照表，一眼看穿它俩的定位👇

一句话总结选择建议：

• 只要你不关心顺序、只在乎“有没有” → 用 HashSet
• 只要你想要“有序的 Set”、范围查询、排序输出 → 用 TreeSet
• 如果你既想要顺序，又想要接近 O(1) 插入查找 → 可以看看 LinkedHashSet 或配合其他结构

四、收个尾：别再把 Set 当“会去重的 List”用了 😏

很多人刚开始写 Java 的时候，对 Set 的理解就是：“我有一堆数据，想去重，就丢到 Set 里再拿出来。”
——这没错，但如果你一直只这么用，那就有点可惜了。

• HashSet 代表的是：高效的、不关心顺序的“元素去重 + 查找”结构
• TreeSet 代表的是：有序的、可做区间操作的“排序集合”

下一次你再写业务逻辑时，不如问问自己一句：

“我现在要的是纯粹的去重，还是其实还偷偷想要‘排序’和‘范围操作’？”

… …

文末

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

… …

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

wished for you successed ！！！

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

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

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