一文学会Set集合

Set集合与Collection基本相同，具有一些不同的行为。Set集合中的元素是无序的，不可以重复添加元素。

1 HashSet类

集合值可以为null，不是同步的，元素是无序的，通过哈希算法计算元素存储的位置，因而可以自动增加其容量。HashSet中元素使用的槽位是“桶‘，如果两个对象的equals()方法返回值是true，会放在一个桶里，通过链式方法存储。因此最好避免出现不同对象equals方法返回true的情况，防止性能下降。

如果把一个对象放入HashSet集合中，重写equals()方法时，也应该重写hashcode()方法。规则是：如果两个对象的equals()返回值是true，则hashcode值应该相同。重写hashcode()方法的步骤是：1.根据规则计算每个实例变量的hashcode值 2.各个实例变量乘以一个质数加权相加。

如果是可变对象，后面的Java程序改变该对象，使该对象中实例变量与另一个对象相同，就可能导致两个对象的hashcode值相同。这会导致HashSettings发生混乱，这个被修改了的对象无法访问了(无法计算hashcode找到它的真实位置了)。当我们把一个元素装入HashSet集合中后，尽量不要修改参与计算hashcode值的实例变量。

LinkedHashSet类是HashSet类的子类，在物理上是根据hash算法存储元素，但是还通过链表方式来维护其元素顺序。

2 TreeSet类

TreeSet类是SorttedSet接口的实现类。其元素是排序(按大小)的。

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet nums = new TreeSet();
        nums.add(5);
        nums.add(2);
        nums.add(10);
        nums.add(-9);
        // [-9, 2, 5, 10]
        System.out.println(nums);
        System.out.println(nums.first());
        // 返回小于4的子集 [-9, 2]
        System.out.println(nums.headSet(4));
        // [5, 10]
        System.out.println(nums.tailSet(5));
        //[2]
        System.out.println(nums.subSet(-3, 4));
    }
}

TreeSet是通过调用集合元素的commpareTo(Object obj)方法比较元素的大小关系。如果试图把一个对象添加到TreeSet时，则该对象必须实现Comparable接口，否则会抛出异常。

class Err {
}

public class TreeSetErrorTest {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
        ts.add(new Err());
        //添加第二个元素时自动调用compareTo()反复，引发ClassCastException
        ts.add(new Err());
    }
}

TreeSet中元素的比较完全是基于compareTo()方法来进行的。

class Z implements Comparable {
    int age;

    public Z(int age) {
        this.age = age;
    }

    public int compareTo(Object o) {
        return 1;
    }

    public boolean equals(Object o) {
        return true;
    }

    @Override
    public String toString() {
        return "Z [age=" + age + "]";
    }
}

public class TreeSetTest2 {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
        Z z1 = new Z(6);
        ts.add(z1);
        // 打印true，即使是同一个对象，但由于compareTo()方法的返回值是1，仍然可以添加
        System.out.println(ts.add(z1));
        // [Z [age=6], Z [age=6]]
        System.out.println(ts);
        ((Z) ts.first()).age = 9;
        //[Z [age=9], Z [age=9]]
        System.out.println(ts);
    }
}

TreeSet中的对象存储可参考下图

但是如果一个可变的对象放入TreeSet中后，该对象的实例变量如果在后续代码中改变了，TreeSet不会再调整它们的顺序。该元素也无法被删除了(甚至与该元素值相同的未被修改的元素也无法被删除)。

可以通过Coparator自定义TreeSet的比较规则。

class M {
    int age;

    public M(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "M [age=" + age + "]";
    }

}

public class TreeSetTest3 {
    public static void main(String[] args) {
        // 此处Lambda表达式的目标类型是comparator
        TreeSet ts = new TreeSet((o1, o2) -> {
            M m1 = (M) o1;
            M m2 = (M) o2;
            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(4));
        //[M [age=5], M [age=4], M [age=-3]]
        System.out.println(ts);
    }
}

3 EnumSet类

EnumSet类专门为枚举类型数据设计，在内部以位向量形式存储数据，这种高效的存储方式使EnumSet对象占用内存小，效率高(尤其是在进行批处理时)。EnumSet中不允许加入null值，否则会报出空指针异常。

enum Season {
    SPRING, SUMMER, FALL, WINTER
}

public class EnumSetTest {
    public static void main(String[] args) {
        EnumSet es1 = EnumSet.allOf(Season.class);
        System.out.println(es1);

        EnumSet es2 = EnumSet.noneOf(Season.class);
        // []
        System.out.println(es2);

        es2.add(Season.WINTER);
        System.out.println(es2);
    }
}

4 各Set类的性能分析

HashSet在查找、增加数据时性能都要比TreeSet更好，这是因为TreeSet底层要通过红黑树来维护，只有需要保持排序的存储元素时才选用TreeSet。LinkedHashSet在增加、删除元素时，比HashSet略慢，这是链表造成的开销，但是由于链表结构，LinkedHashSet会在遍历上更快。EnumSet是所有Set中性能最好的，但是只能存储枚举类型数据。Set集合都是线程非安全的，可以使用collections工具类中sychronizedSortedSet方法包装该集合来实现同步。

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