8-Set 集合

发表于 | 更新于 | 分类于

Set集合

Set 集合不允许包含相同的元素，主要介绍 HashSet、TreeSet 和 EnumSet。

HashSet类

  • 不保证元素的排列顺序。
  • HashSet不是同步的，如果多个线程同时访问一个 HashSet，假设有两个或以上的线程同时修改了 HashSet 集合，则必须通过代码来保证同步。
  • HashSet 集合元素可以是 null。

当向 HashSet 集合存入一个元素时，HashSet 会调用该对象的 hashCode() 方法得到该对象的 hashCode 值，然后根据该 hashCode 值决定该对象在 HashSet 中的存储位置。如果有两个元素通过 equals() 方法比较返回 true，但它们的 hashCode() 方法返回值不相等，HashSet 将会把它们存储在不同位置，依然可以添加成功。

也就是说，HashSet 集合判断两个元素相等的标准是两个对象通过 equals() 方法比较得出相等，并且两个对象的 hashCode() 方法返回值也相等。

当需要把某个类的对象保存到 HashSet 集合中，重写这个类的 equals() 和 hashCode() 方法时，应该尽量保证两个对象通过 equals() 方法比较返回 true 时，它们的 hashCode() 也会相等。

HashSet 访问元素集合是根据元素的 HashCode 值来快速定位的。

当程序把可变对象添加到 HashSet 中之后，尽量不要去修改该集合元素中参与计算 hashCode()、equals() 的实例变量，否则将会导致 HashSet 无法正确操作这些集合元素。

HashSet 中每个能存储元素的 “槽位(slot)” 通常称为 “桶(bucket)”，如果有多个元素的 hashCode 值相同，但它们通过 equals() 方法比较返回 true，就需要在一个 “桶” 里放多个元素，通常是用链表实现。

LinkedHashSet 类

HashSet 类还有一个子类 LinkedHashSet，它使用链表来维护元素的次序，这样使得元素看起来是以插入的顺序保存的。当遍历 LinkedHashSet 集合里的元素时，LinkedHashSet 将会按元素的添加顺序来访问集合里的元素。

LinkedHashSet 需要维护元素的插入顺序，因此性能略低于 HashSet 的性能，但是在迭代访问 Set 里的全部元素时性能很好，因为它以链表来维护内部顺序。

TreeSet 类

TreeSet 是 SortedSet 接口的实现类，它可以确保集合元素处于排序状态。也就是说，TreeSet 并不是根据元素的插入顺序进行排序的，而是根据元素实际值的大小来进行排序的。

TreeSet 采用红黑树的数据结构来存储集合元素。TreeSet 支持两种排序方法：自然排序 和 定制排序：

  • 自然排序

TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按 升序 排列。

Java 提供了一个 Comparable 接口，里面定义了一个 compareTo(Object obj) 方法，该方法返回一个整数值。当一个对象调用该方法与另一个对象进行比较时，例如 obj1.compareTo(obj2)，若相等则返回 0，若 obj1 大于 obj2，则返回一个正整数，若 obj1 小于 obj2，则返回一个负整数。

如果把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口，否则会抛出异常。并且，TreeSet 只能添加同一种类型的对象。

当把一个对象加入 TreeSet 集合中时，TreeSet 调用该对象的 compareTo(Object obj) 方法与容器中的其他对象比较大小，然后根据红黑树结构找到它的存储位置。如果两个对象通过 compareTo(Object obj) 方法比较相等，新对象将无法添加到 TreeSet 集合中。

对于 TreeSet 集合来说，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较是否返回 0。

  • 定制排序

如果要实现定制排序，例如以降序排列，则可以通过 Comparator 接口。该接口包含一个 int compare(T o1,T o2) 方法，该方法用于比较 o1 和 o2 的大小。

当需要实现定制排序时，要在创建 TreeSet 集合对象时，提供一个 Comparator 对象与该 TreeSet 集合关联，由该 Comparator 对象负责集合元素的排列逻辑。由于 Comparator 是一个函数式接口，所以可以使用 Lambda表达式代替 Comparator 对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class M
{
    int age;
    public M(int age) { this.age = age; }

    public String toString() { return "M[age:" + age + "]" }
}

public class TreeSetTest
{
    public static void main(String[] args)
    {
        TreeSet ts=new TreeSet( (o1,o2)->{
            M m1=(M)o1;
            M m2=(M)o2;
            //根据 M 对象的 age 属性来决定大小，age 越大，M 对象反而越小
            return m1.age > m2.age ? -1:m1.age<m2.age ? 1:0;};

        ts.add(new M(5));
        ts.add(new M(-3));
        ts.add(new M(9));
        System.out.println(ts);
    }
}

与 HashSet 集合相比，TreeSet 还提供了几个额外的方法：

  • Comparator comparator()：如果 TreeSet 采用了定制排序，则该方法返回定制排序所使用的 Comparator；如果 TreeSet 采用了自然排序，则返回 null。
  • Object first()：返回集合中的第一个元素。
  • Object last()：返回集合中的最后一个元素。
  • Object lower(Object e)：返回集合中小于指定元素的最大元素，参考元素不需要是 TreeSet 集合里的元素。
  • Object higher(Object e)：返回集合中大于指定元素的最小元素，参考元素不需要是 TreeSet 集合里的元素。
  • SortedSet subSet(Object fromElement,Object toElement)：返回此 Set 的子集合，范围从 fromElement（包含）到 toElement（不包含）。
  • SortedSet headSet(Object toElement)：返回此 Set 的子集合，由小于 toElement 的元素组成。
  • SortedSet tailSet(Object fromElement)：返回此 Set 的子集合，由大于或等于 fromElement 的元素组成。

EnumSet 类

EnumSet 类是一个专为枚举类设计的集合类，EnumSet 中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建 EnumSet 时显式或隐式指定。EnumSet 以枚举值在 Enum 类的定义顺序来决定集合元素的顺序。

EnumSet 在内部以 位向量 的形式存储，占用内存很小，运行效率高，尤其是进行批量操作时。EnumSet 集合不允许加入 null 元素，否则将抛出 NullPointerException。

EnumSet 类没有暴露任何构造器来创建该类的实例，通过它提供的静态方法来创建 EumSet 对象：

  • EnumSet allOf(Class elemetnType)：创建一个包含指定枚举类里所有枚举值的 EnumSet 集合。
  • EnumSet complementOf(EnumSet s)：创建一个其元素类型与指定 EnumSet 里元素类型相同的 EnumSet 集合，新 EnumSet 集合包含原 EnumSet 集合所不包含的、此枚举类剩下的枚举值。
  • EnumSet copyOf(Collection c)：使用一个普通集合来创建 EnumSet 集合。
  • EnumSet copyOf(EnumSet s)：创建一个与指定 EnumSet 具有相同元素类型、相同集合元素的 EnumSet 集合。
  • EnumSet noneOf(Class elementType)：创建一个元素类型为指定枚举类型的空 EnumSet。
  • EnumSet of(E first,E…rest)：创建一个包含一个或多个枚举值的 EnumSet 集合，传入的多个枚举值必须属于同一个枚举类。
  • EnumSet range(E from,E to)：创建一个包含从 from 枚举值到 to 枚举值范围内所有枚举值的 EnumSet 集合。

各 Set 实现类的性能分析

HashSet 的性能总是比 TreeSet 好(特别是最常用的添加、查询元素等操作)，因为 TreeSet 需要额外的红黑树算法来维护集合元素的次序。

HashSet 还有一个子类：LinkedHashSet，对于普通的插入、删除操作，LinkedHashSet 比 HashSet 要略微慢一点，但是遍历 LinkedHashSet 会更快。

EnumSet 是所有 Set 实现类中性能最好的，但它只能保存同一个枚举类的枚举值作为集合元素。

Set 的三个实现类，HashSet、TreeSet 和 EnumSet 都是线程不安全的。可以通过 Collections 工具类的 **synchronizedSortedSet() 方法来包装该 Set 集合，并最好在创建 Set 集合时进行。

1
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));