Java Set 常用集合 HashSet、LinkedHashSet、TreeSet

2022-09-02 08:17:11

Java 中的 Set 是非常常用的数据类型。Set 是无序的 Collection，Java Set 有三个常用的实现类，分别是：HashSet、LinkedHashSet、TreeSet

本文基于 JDK8 分析

HashSet

HashSet 继承自 AbstractSet，实现了 Set 接口。底层基于 HashMap 实现，是一个不允许有重复元素的无序集合。允许 null 元素，非线程安全。HashSet 还实现了 Cloneable、Serializable 接口，所以 HashSet 是支持复制、序列化的

所以说，HashMap 是替 HashSet 打工的。就像老板手下的员工，任劳任怨，做牛做马，像极了被剥削的我们（小声哔哔）

// 用于存储元素的 HashMap
private transient HashMap<E,Object> map;
// 凑数的值元素，
private static final Object PRESENT = new Object();

HashSet 有五个构造函数，解释下第二个构造函数：默认加载因子为 0.75 的情况下，假设 c 的元素个数就是 map 此时的最大阈值，最大阈值为 (int) (c.size()/.75f)，再加一，通过 HashMap 的扩容机制（取大于当前容量的最小二次幂），就可以取得最适合的容量大小

// 构造一个默认容量为 16 的 HashMap
public HashSet()  {
    map = new HashMap<>();
}
// 将 Collection 中的元素赋给 HashMap
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
// 指定 HashMap 的初始容量和加载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// 指定 HashMap 的初始容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// 供 LinkedHashSet 使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet 常用方法

第一个是 add 方法。HashSet 使用 HashMap 保证元素不重复，熟悉 HashMap 的都知道，HashMap 的 Key 是不允许重复的，所以可以把要添加的元素作为 HashMap 的 Key 保存，但 Value 还是要有的，所以 HashSet 又定义了一个静态常量对象 PRESENT 来凑数，实际上并没有什么意义

private static final Object PRESENT = new Object();

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

到这里就一目了然了，HashSet 中添加元素的方法其实就是调用 HashMap 的 put 方法，如果 put 方法的返回值为 null，证明以 e 为键的元素不存在，则可以添加；否则会把原有的值删除并覆盖，并返回原来的值。所以当 add 方法中的条件判断成立，则证明添加成功，反之则失败。如果不了解 HashMap 的机制，可以看一下下面这张图

![](G:\SSS\Java\Java SE\博客\HashMap add.png)

至于其他的 remove、contains 就更不用说了，全是 HashMap 的知识，不再赘述

LinkedHashSet

LinkedHashSet 是 HashSet 的子类，实现了 Set 接口，Set 有的特点它都有。既然 HashSet 靠 HashMap 干活，那是否 LinkedHashSet 也有自己的小弟呢？（没错，说的就是你 LinkedHashMap）

还记得之前提到在 HashSet 有一个专供 LinkedHashSet 使用的构造方法吗？这个构造方法只能由 LinkedHashSet 调用，参数 dummy 并没有实际意义，只是为了和 HashSet 中其他参数区分开罢了（重载原理）

LinkedHashMap 基于双向链表实现，相比于 HashMap 最大的不同就是有序。LinkedHashSet 中除了四个构造器以外再无其他方法，全部继承自 HashSet。如果想了解更多，就去看看 LinkedHashMap 吧

// HashSet 中专供 LinkedHashSet 使用的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// LinkedHashSet 的构造方法
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

TreeSet

在此之前先了解一下 SortedSet，SortSet 扩展了 Set 并提供其元素的总排序，要求所有元素都必须实现 Comparable 接口，而且所有元素都必须是可比较的，即两个对象可以互相作为 compareTo 方法的参数。从这里可以看出，SortedSet 所谓的有序并不是我们通常认为的先后插入顺序，而是根据对象的比较函数对元素排序。SortSet 接口的方法如下：

// 返回用于对此集合中的元素进行排序的比较器，如果此集合使用其元素的自然顺序，则返回 null
Comparator<? super E> comparator();
// 返回此集合的部分元素，元素范围从 fromElement（包括）到 toElement（不包括）
SortedSet<E> subSet(E fromElement, E toElement);
// 返回此集合的部元素，其中元素全部小于 toElement
SortedSet<E> headSet(E toElement);
// 返回此集合的部分元素，其中元素全部大于或等于 fromElement
SortedSet<E> tailSet(E fromElement);
// 返回此集合中当前的第一个（最低）元素
E first();
// 返回此集合中当前的最后一个（最高）元素
E last();

NavigableSet 实现了 Sorted 接口，其本身也是一个接口，对 SortedHash 进行了扩展，支持导航方法，例如查找与指定目标最匹配项等。TreeSet 继承自 AbstractSet，实现了 NavigableSet 接口。TreeSet 基于 TreeMap 实现，其构造方法如下：

private transient NavigableMap<E,Object> m;

// 构造一个指定的 NavigableMap 的集合
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 默认方法，根据元素的自然排序进行排序
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定比较器进行排序
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 构造一个包含指定集合中元素的集合，根据元素的自然排序进行排序
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 构造一个包含相同元素的集合，并使用与指定排序集相同的排序
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

TreeSet 也是基于 TreeMap 工作的，TreeMap 也是一个可排序的 Map，排序原理也是依靠比较器，更多的细节请了解 TreeMap

码农公寓

HashSet

HashSet 常用方法

LinkedHashSet

TreeSet

相关文章