JavaSE:集合部分----Set接口方法的学习

--黎--

718人浏览 · 2026-01-27 22:58:21

--黎-- · 2026-01-27 22:58:21 发布

在这里插入图片描述

引言：什么是Set？

在Java编程中，我们经常需要处理一组不重复的元素。比如统计一篇文章中的不同词汇、管理系统中唯一的用户ID、过滤重复数据等场景。Set接口正是为处理这种"唯一性"需求而设计的，它是Java集合框架中用于存储不重复元素的核心接口。

如果说List是有序可重复的集合，那么Set就是无序（或有序）不可重复的集合。Set接口基于数学中的集合概念，确保了元素的唯一性，这在实际开发中对于数据去重、成员关系判断等场景具有重要意义。理解Set的不同实现类及其底层机制，对于编写高效、正确的Java程序至关重要。

基本介绍

无序，添加取出顺序不一致，无索引。
不允许重复元素，最多有一个null
实现set接口的主要类有 HashSet，TreeSet

HashSet

底层机制

HashSet底层是 HashMap，HashMap底层是（数组+链表+红黑树）

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

元素顺序取决于hash后确定索引的结果。

其中的 key-value，key为传入的值，value为present常量，不变

添加一个元素时，先得到hash值转成->索引值
*hash值取得：^ 按位异或

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)；

使hash值更随机，提高了分布均匀性。

找到存储数据表table，看这个索引位置是否已经存放的有元素
如果没有，直接加入
如果有，调用 equals 比较，如相同，就放弃添加，如果不相同，则对哈希值进行运算，得出一个索引添加到最后
*这里通常需要对equals与HashCode方法进行重写，自定义"相同"的标准
在Java8中，如果一条链表的元素个数到达 TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)。

在这里插入图片描述

扩容机制

HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是 16*加载因子(loadFactor)是0.75=12
如果table数组使用到了临界值12，就会扩容到162=32，新的临界值就是320.75=24，依此类推
在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制

LinkedHashSet

是HashSet的子类，底层是一个LinkedHashMap，维护了一个数组 + 双向链表。

根据元素的hashCode值来决定元素的存储位置，并使用双向链表维护元素次序（每个节点有pre与next属性），使元素看起来以输入顺序保存。遍历顺序与插入顺序一致。

TreeSet

底层是TreeMap

实现了compare接口，通过使用提供的一个构造器，可以传入一个比较器（用匿名内部类重写）并指定排序规则。

构造器把传入的比较器对象，赋给了 TreeSet 的底层的 TreeMap 的属性 this.comparator

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

在调用 treeSet.add(“tom”) 时，在底层会执行到：

if (cpr != null) { // cpr 就是我们的匿名内部类(对象)
    do {
        parent = t;
        // 动态绑定到我们的匿名内部类(对象)compare
        cmp = cpr.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else // 如果相等，即返回 0,这个 Key 就没有加入
            return t.setValue(value);
    } while (t != null);
}

题目

试分析HashSet和TreeSet分别如何实现去重的

HashSet的去重机制：
hashCode() + equals()，底层先通过存入对象，进行运算得到一个hash值，通过hash值得到对应的索引，如果发现table索引所在的位置，没有数据，就直接存放，如果有数据，就进行equals比较[遍历比较]，如果比较后，不相同，就加入，否则就不加入。
TreeSet的去重机制：
如果你传入了一个Comparator匿名对象，就使用实现的compare去重，如果方法返回0，就认为是相同的元素/数据，就不添加，如果没有传入一个Comparator匿名对象，则以添加的对象实现的Compareable接口的compareTo去重。