Set集合

Set集合

Set集合与Collection基本上完全一样，它没有提供任何额外的方法。实际上Set就是Collection，只是行为略有不同（Set不允许包含重复元素）。

Set集合不允许包含相同的元素，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失败，add方法返回false，且新元素不会被加入。

Set判断两个对象相同不是使用==运算符，而是根据equals方法。

public class SetTest {

    public static void main(String[] args) {
        Set books = new HashSet();
        //添加一个字符串对象
        books.add(new String("疯狂Java讲义"));
        //再次添加一个字符串对象
        //因为两个字符串对象通过equals方法比较相等
        //所以添加失败，返回false
        boolean result = books.add(new String("疯狂Java讲义"));
        //从下面输出看到集合只有一个元素
        System.out.println(result + "——>" + books);

    }

}

false——>[疯狂Java讲义]

HashSet类

HashSet是Set接口的典型实现，大多数时候使用Set集合就是使用这个实现类。HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。

HashSet具有以下特点

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

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

也就是说HashSet添加元素能否添加成功取决于该元素的hashCode()方法和equals()方法

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

public class HashSetTest {

    public static void main(String[] args) {
        Set books = new HashSet();
        //分别向books集合中添加两个A对象、两个B对象、两个C对象
        books.add(new A());
        books.add(new A());
        books.add(new B());
        books.add(new B());
        books.add(new C());
        books.add(new C());

        for (Object obj : books){
            System.out.println(obj);
        }




    }

}

//类A的equals()方法总是返回true，但没有重写其hashCode()方法
class A{
    @Override
    public boolean equals(Object obj){
        return true;
    }
}

//类B的hashCoded()方法总是返回1，但没有重写其equals()方法
class B{
    @Override
    public int hashCode(){
        return 1;
    }
}

//类C的hashCode()方法总是返回2，且重写了其equals()方法
class C{
    @Override
    public int hashCode(){
        return 2;
    }

    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

输出结果

B@1
B@1
A@30f39991
C@2
A@a09ee92

上面程序中向books集合中分别添加了两个A对象、两个B对象和两个C对象，其中C类重写了equals()方法总是返回true，hashCode()方法总是返回2，这将导致HashSet把两个C对象当成同一个对象。

当把一个对象放入HashSet中时，如果需要重写该对象对应类的equals()方法，则也应该重写其hashCode()方法。其规则是：如果两个对象通过equals()方法比较返回true，这两个对象的hashCode值也应该相同。

如果两个对象通过equals()方法比较返回true，但这两个对象的hashCode()方法返回不同的hashCode值时，这将导致HashSet会把这两个对象保存在Hash表的不同位置，从而使两个对象都可以添加成功，这就与Set集合的规则有些出入了。

如果两个对象的hashCode()方法返回的hashCode值相同，但它们通过equals()方法比较返回false时将更麻烦：因为两个对象的hashCode值相同，HashSet将试图把它们保存在同一个位置，但又不行（否则将只剩下一个对象），所以实际上会在这个位置用链式结构来保存多个对象；而HashSet访问元素时也是根据元素的hashCode值来快速定位的，如果HashSet中两个以上的元素具有相同的hashCode值，将会导致性能下降。

当从HashSet中访问元素时，HashSet先计算该元素的hashCode值（也就是调用该对象的hashCode()方法的返回值），然后直接到该hashCode值对应的位置去取出该元素，这就是HashSet速度很快的原因。

重写hashCode()方法的基本规则

• 在程序运行过程中，同一个对象多次调用hashCode()方法应该返回相同的值。
• 当两个对象通过equals()方法比较返回true时，这两个对象的hashCode()方法应返回相等的值。
• 对象中用作equals()方法比较标准的Field，都应该用来计算hashCode值。

重写hashCode()方法的一般规则

1. 把对象内每个有意义的Field（即每个用作equals()方法比较标准的Field）计算出int类型的hashCode值。

2. 用第一步计算出来的多个hashCode值组合计算出一个hashCode值返回

return f1.hashCode() + (int)f2;

为了避免直接相加产生偶然相等（两个对象的f1、f2 Field并不相等，但它们的和恰好相等），可以通过为各Field乘以任意一个质数后再相加。

return f1.hashCode() * 17 + (int)f2 * 13;

如果向HashSet中添加一个可变对象后，后面程序修改了该可变对象的Field，则可能导致它与集合中的其他元素相同（即两个对象通过equals()方法比较返回true，两个对象的hashCode值也相等），这就有可能导致HashSet中包含了两个相同的对象。

public class HashSetTest2 {

    public static void main(String[] args) {
        HashSet hs = new HashSet();
        hs.add(new R(5));
        hs.add(new R(-3));
        hs.add(new R(9));
        hs.add(new R(-2));
        //打印HashSet集合，集合元素没有重复
        System.out.println(hs);
        //取出第一个元素
        Iterator it = hs.iterator();
        R first = (R) it.next();
        //为第一个元素的count实例变量赋值
        first.count = -3;
        //再次输出HashSet集合，集合元素有重复元素
        System.out.println(hs);
        //删除count为-3的R对象
        hs.remove(new R(-3));
        //可以看到被删除了一个R元素
        System.out.println(hs);
        //输出false
        System.out.println("hs是否包含count为-3的R对象？" + hs.contains(new R(-3)));
        //输出false
        System.out.println("hs是否包含count为-2的R对象？" + hs.contains(new R(-2)));

    }

}

class R{
    int count;
    public R(int count){
        this.count = count;
    }

    @Override
    public String toString(){
        return "R[count:" + count + "]";
    }

    @Override
    public boolean equals(Object obj){
        if (this == obj) return true;
        if (obj != null && obj.getClass() == R.class){
            R r = (R) obj;
            if (r.count == this.count){
                return true;
            }
        }

        return false;
    }

    @Override
    public int hashCode(){
        return this.count;
    }


}

输出结果

[R[count:-2], R[count:-3], R[count:5], R[count:9]]
[R[count:-3], R[count:-3], R[count:5], R[count:9]]
[R[count:-3], R[count:5], R[count:9]]
hs是否包含count为-3的R对象？false
hs是否包含count为-2的R对象？false

解析

因为将第一个R(-2)对象的count值改成了-3，但HashSet一开始
已经把R(-2)对象添加到了hashCode值为-2的地方，
所以当改变R(-2)的count为-3，再打印hs集合就存在两个相同的元素了。

当删除R(-3)对象时，会先去计算R(-3)对象的hashCode值，
然后根据hashCode值找到对应对象R(-3)，此时找到的是集合中的第二个元素，
然后通过equals比较相等则删除hs集合中第二个元素。

同理，判断hs是否包含count为-3的R对象，先根据R(-3)的hashCode值为-3，
hs集合中通过hashCode值找不到该对象，所以打印false
判断hs是否包含count为-2的R对象，虽然通过hashCode值-2可以找到就是
第一个元素，但equals方法不等，所以也是打印false

当向HashSet中添加可变对象时，必须十分小心。如果修改HashSet集合中的对象，有可能导致该对象与集合中的其他对象相等，从而导致HashSet无法准确访问该对象。

LinkedHashSet类

HashSet还有一个子类LinkedHashSet，LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。也就是说，当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合里的元素。
LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet的性能，但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

public class LinkedHashSetTest {

    public static void main(String[] args) {
        LinkedHashSet books = new LinkedHashSet();
        books.add("疯狂Java讲义");
        books.add("轻量级Java EE企业应用实战");
        System.out.println(books);
        //删除 疯狂Java讲义
        books.remove("疯狂Java讲义");
        //重新添加 疯狂Java讲义
        books.add("疯狂Java讲义");
        System.out.println(books);
    }

}

[疯狂Java讲义, 轻量级Java EE企业应用实战]
[轻量级Java EE企业应用实战, 疯狂Java讲义]

输出LinkedHashSet集合的元素时，元素的顺序总是与添加顺序一致。

TreeSet类

TreeSet是SortedSet接口的实现类，正如SortedSet名字所暗示的，TreeSet可以确保集合元素处于排序状态。与HashSet集合想比，TreeSet还提供了如下几个额外的方法。

//如果TreeSet采用了定制排序，则该方法返回定制排序所使用的Comparator
//如果TreeSet采用了自然排序，则返回null
	public Comparator<? super E> comparator() {
	    return m.comparator();
	}

//返回集合中的第一个元素
    public E first() {
        return m.firstKey();
    }

//返回集合中的最后一个元素
   public E last() {
        return m.lastKey();
    }

//返回集合中位于指定元素之前的元素
//即小于指定元素的最大元素，参考元素不需要是TreeSet集合里的元素
    public E lower(E e) {
        return m.lowerKey(e);
    }

//返回集合中位于指定元素之后的元素
//即大于指定元素的最小元素
    public E higher(E e) {
        return m.higherKey(e);
    }

//返回此Set的子集合，范围从fromElement（包含）到toElement（不包含）
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

//返回此Set的子集，由小于toElement的元素组成
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }

//返回此Set的子集，由大于或等于fromElement的元素组成
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

表面上看起来这些方法很复杂，其实它们很简单，因为TreeSet中的元素是有序的，所以增加了访问第一个、前一个、后一个、最后一个元素的方法，并提供了三个从TreeSet中截取子TreeSet的方法

public class TreeSetTest {

    public static void main(String[] args) {
        TreeSet nums = new TreeSet();
        //向TreeSet中添加四个Integer对象
        nums.add(5);
        nums.add(2);
        nums.add(10);
        nums.add(-9);

        //输出集合元素，看到集合元素已经处于排序状态
        System.out.println(nums);
        //输出集合里的第一个元素
        System.out.println(nums.first());
        //输出集合里的最后一个元素
        System.out.println(nums.last());
        //返回小于4的子集，不包含4
        System.out.println(nums.headSet(4));
        //返回大于5的子集，如果Set中包含5，子集中也包含
        System.out.println(nums.tailSet(5));
        //返回大于等于-3、小于4的子集
        System.out.println(nums.subSet(-3, 4));

    }

}

输出结果

[-9, 2, 5, 10]
-9
10
[-9, 2]
[5, 10]
[2]

根据上面程序的运行结果即可看出，TreeSet并不是根据元素的插入顺序进行排序的，而是根据元素实际值的大小来进行排序的。

与HashSet集合采用hash算法来决定元素的存储位置不同，TreeSet采用红黑树的数据结构来存储集合元素。

那么TreeSet进行排序的规则是怎样的呢？TreeSet支持两种排序方法：自然排序和定制排序。在默认情况下，TreeSet采用自然排序

自然排序

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

Java提供了一个Comparable接口，该接口定义了一个compareTo(Object obj)，该方法返回一个整数值，实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时，例如obj1.compareTo(obj2)，如果该方法返回0，则表明这两个对象相等；如果该方法返回一个正整数，则表明obj1大于obj2；如果该方法返回一个负整数，则表明obj1小于obj2.

Java的一些常用类已经实现了Comparable接口，并提供了比较大小的标准。下面是实现了Comparable接口的常用类

• BigDecimal、BigInteger以及所有的数值型对应的包装类：按它们对应的数值大小进行比较
• Character：按字符的unicode值进行比较
• Boolean：true对应的包装类实例大于false对应的包装类实例
• String：按字符串中字符的unicode值进行比较
• Date、Time：后面的时间、日期比前面的时间、日期大

如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable接口，否则程序将会抛出异常。

public class TreeSetErrorTest {

    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
        ts.add(new Err());
    }

}

class Err{}

运行程序

Exception in thread "main" java.lang.ClassCastException: com.sunrise.eHealth.day0611.Err cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at com.sunrise.eHealth.day0611.TreeSetErrorTest.main(TreeSetErrorTest.java:10)

当把一个对象加入TreeSet集合中时，TreeSet调用该对象的compareTo(Object obj)方法与容器中的其他对象比较大小，然后根据红黑树结构找到它的存储位置。如果两个对象通过compareTo(Object obj)方法比较相等，新对象将无法添加到TreeSet集合中。
对于TreeSet集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过compareTo(Object obj)方法比较是否返回0，如果通过compareTo(Object obj)方法比较返回0，TreeSet则会认为它们相等，否则就认为它们不相等。

定制排序

TreeSet的自然排序是根据集合元素的大小，TreeSet将它们以升序排序。如果需要实现定制排序，例如以降序排序，则可以通过Comparator接口的帮助。
如果需要实现定制排序，则需要在创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序逻辑。

当通过Comparator对象来实现TreeSet的定制排序时，依然不可以向TreeSet中添加类型不同的对象，否则会引发ClassCastException异常。使用定制排序时，TreeSet对集合元素排序不管集合元素本身的大小，而是由Comparator对象负责集合元素的排序规则。TreeSet判断两个集合元素相等的标准是：通过Comparator比较两个元素返回了0，这样TreeSet不会把第二个元素添加到集合中。

EnumSet类

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

EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效，因此EnumSet对象占用内存很小，而且运行效率很好。尤其是进行批量操作（如调用containsAll和retainAll方法）时，如果其参数也是EnumSet集合，则该批量操作的执行速度也非常快。

EnumSet类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的static方法来创建EnumSet对象。EnumSet类它提供了如下常用的static方法来创建EnumSet对象

创建一个包含指定枚举类里所有枚举值的EnumSet集合

    public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {
        EnumSet<E> result = noneOf(elementType);
        result.addAll();
        return result;
    }

创建一个其元素类型与指定EnumSet里元素类型相同的EnumSet集合，新EnumSet集合包含原EnumSet集合所不包含的、此枚举类剩下的枚举值（即新EnumSet和原EnumSet集合的集合元素加起来就是该枚举类的所有枚举值）

    public static <E extends Enum<E>> EnumSet<E> complementOf(EnumSet<E> s) {
        EnumSet<E> result = copyOf(s);
        result.complement();
        return result;
    }

使用一个普通集合来创建EnumSet集合

    public static <E extends Enum<E>> EnumSet<E> copyOf(Collection<E> c) {
        if (c instanceof EnumSet) {
            return ((EnumSet<E>)c).clone();
        } else {
            if (c.isEmpty())
                throw new IllegalArgumentException("Collection is empty");
            Iterator<E> i = c.iterator();
            E first = i.next();
            EnumSet<E> result = EnumSet.of(first);
            while (i.hasNext())
                result.add(i.next());
            return result;
        }
    }

创建一个与指定EnumSet具有相同元素类型、相同集合元素的EnumSet集合

    public static <E extends Enum<E>> EnumSet<E> copyOf(EnumSet<E> s) {
        return s.clone();
    }

创建一个元素类型为指定枚举类型的空EnumSet

    public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
        Enum<?>[] universe = getUniverse(elementType);
        if (universe == null)
            throw new ClassCastException(elementType + " not an enum");

        if (universe.length <= 64)
            return new RegularEnumSet<>(elementType, universe);
        else
            return new JumboEnumSet<>(elementType, universe);
    }

创建一个包含一个或多个枚举值的EnumSet集合，传入的多个枚举值必须属于同一个枚举类。

    public static <E extends Enum<E>> EnumSet<E> of(E first, E... rest) {
        EnumSet<E> result = noneOf(first.getDeclaringClass());
        result.add(first);
        for (E e : rest)
            result.add(e);
        return result;
    }

创建一个包含从from枚举值到to枚举值范围内所有枚举值的EnumSet集合

    public static <E extends Enum<E>> EnumSet<E> range(E from, E to) {
        if (from.compareTo(to) > 0)
            throw new IllegalArgumentException(from + " > " + to);
        EnumSet<E> result = noneOf(from.getDeclaringClass());
        result.addRange(from, to);
        return result;
    }

以下代码示范了EnumSet集合的常规用法

public class EnumSetTest {

    public static void main(String[] args) {
        //创建一个EnumSet集合，集合元素就是Season枚举类的全部枚举值
        EnumSet es1 = EnumSet.allOf(Season.class);
        System.out.println(es1);
        //创建一个EnumSet空集合，指定其集合元素是Season类的枚举值
        EnumSet es2 = EnumSet.noneOf(Season.class);
        System.out.println(es2);

        //手动添加两个元素
        es2.add(Season.WINTER);
        es2.add(Season.SPRING);
        System.out.println(es2);

        //以指定枚举值创建EnumSet集合
        EnumSet es3 = EnumSet.of(Season.SUMMER, Season.WINTER);
        System.out.println(es3);

        EnumSet es4 = EnumSet.range(Season.SUMMER, Season.WINTER);
        System.out.println(es4);

        //新创建的EnumSet集合元素和es4集合元素有相同的类型
        //es5集合元素 + es4集合元素 = Season枚举类的全部枚举值
        EnumSet es5 = EnumSet.complementOf(es4);
        System.out.println(es5);




    }

}

enum Season{
    SPRING,SUMMER,FALL,WINTER
}

输出结果

[SPRING, SUMMER, FALL, WINTER]
[]
[SPRING, WINTER]
[SUMMER, WINTER]
[SUMMER, FALL, WINTER]
[SPRING]

当试图复制一个Collection集合里的元素来创建EnumSet集合时，必须保证Collection集合里的所有元素都是同一个枚举类的枚举值。

各Set实现类的性能分析

HashSet和TreeSet是Set的两个典型实现，到底如何选择HashSet和TreeSet呢？
HashSet的性能总是比TreeSet好（特别是最常用的添加、查询元素等操作），因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时，才应该使用TreeSet，否则都应该使用HashSet。

HashSet还有一个子类：LinkedHashSet，对于普通的插入、删除操作，LinkedHashSet比HashSet要略微慢一点，这是有维护链表所带来的额外开销造成的；不过，因为有了链表，遍历LinkedHashSet会更快。

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

必须指出的是，Set的三个实现类HashSet、TreeSet和EnumSet都是线程不安全的。如果有多个线程同时访问一个Set集合，并且有超过一个线程修改了该Set集，则必须手动保证该Set集合的同步性。通常可以通过Collections工具类的synchronizedSortedSet方法来包装该Set集合。此操作最好在创建时进行，以防止对Set集合的意外非同步访问。