Java容器学习笔记（二） Set接口及其实现类的相关知识总结

在Java容器学习笔记（一）中概述了Collection的基本概念及接口实现，并且总结了它的一个重要子接口List及其子类的实现和用法。

本篇主要总结Set接口及其实现类的用法，包括HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）等。



2.     Set接口及其实现类
Set接口中方法清单：

Set集合和List集合都存放的是单个元素的序列，但是Set集合不允许集合中有重复元素（主要依赖于equals方法）。

Set接口的父接口为Collection和Iterable，直接实现该接口的子接口有SortedSet和NavigableSet。

实现Set接口的重要类有HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）。

在Set接口中没有新增任何方法，所有方法均来自其父接口。它无法提供像List中按位存取的方法。在数学上一个集合有三个性质：确定性，互异性，无序性。

Ø  HashSet的特点、实现机制及使用方法

a)      HashSet的特点：

HashSet中存放的元素是无序的，底层是用HashMap实现的，其中key是要放入的元素，value是一个Object类型的名为PRESENT的常量，由于用到了散列函数，因此其存取速度是非常快的，在地址空间很大的情况下它的存取速度可以达到O(1)级。如果首先了解了HashMap的实现方法，那么HashSet的实现是非常简单的。

b）HashSet的实现机制：
首先需要了解一下散列或者哈希的用法。我们知道，当数据量很大时hash函数计算的结果将会重复，按照下图所示的形式进行存贮。

在HashSet中有个loadFactor（负载因子），对于上图所示总共有11个位置，目前有4个位置已经存放，即40%的空间已被使用。

在HashSet的默认实现中，初始容量为16，负载因子为0.75，也就是说当有75%的空间已被使用，将会进行一次再散列（再哈希），之前的散列表（数组）将被删除，新增加的散列表是之前散列表长度的2倍，最大值为Integer.MAX_VALUE。

负载因子越高，内存使用率越大，元素的寻找时间越长。

负载因子越低，内存使用率越小，元素的寻找时间越短。

从上图可以看出，当哈希值相同时，将存放在同一个位置，使用链表方式依次链接下去。

（面试官问到这个问题，当时我的回答是再哈希，其实我并不知道HashSet真正是怎么实现的，我只知道在学习数据结构时学习过再哈希，就是这个哈希表很满时需要重新建立哈希表，以便于存取，因为大量的值放在一个位置上就变成了链表的查询了，几乎是O(n/2)级别的，但是我没有说出来再哈希的过程，以及哈希值相同时到底如何存放，所以……~~o(>_<)o ~~）。

为了说明HashSet在Java中确实如上实现，下面附上JDK中两个重要方法的源码：（下面源码来自于HashMap，原因是HashSet是基于HashMap实现的）

/**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

HashSet共实现了5个构造方法，对外提供了4个构造方法。这些方法在api中均可看到详细使用说明。由于HashSet基于HashMap实现，我们只关心我们放入的key，value是个Object类型的常量，所以在iterator方法中使用的是HashMap的keySet方法进行迭代的。

c）HashSet的使用方法：

从HashSet的特点及实现上看，我们知道在不需要放入重复数据并且不关心放入顺序以及元素是否要求有序的情况下，我们没有任何理由不选择使用HashSet。另外HashSet是允许放空值的。

那么HashSet是如何保证不重复的？下面一个例子说明：

    import java.util.HashSet;  
    import java.util.Iterator;  
    public class ExampleForHashSet {  
        public static void main(String[] args) {  
            HashSet<Name> hs = new HashSet<Name>();  
            hs.add(new Name("Wang", "wu"));  
            hs.add(new Name("Zhang", "san"));  
            hs.add(new Name("Wang", "san"));  
            hs.add(new Name("Zhang", "wu"));  
            //本句输出为2  
            System.out.println(hs.size());  
            Iterator<Name> it = hs.iterator();  
            //下面输出两行，分别为Zhang:san和Wang:wu  
            while(it.hasNext()) {  
                System.out.println(it.next());  
            }  
        }  
    }  
    class Name {  
        String first;  
        String last;  
        public Name(String first, String last) {  
            this.first = first;  
            this.last = last;  
        }  
        @Override  
        public boolean equals(Object o) {  
            if(null == o) {  
                return false;  
            }  
            if(this == o) {  
                return true;  
            }  
            if(o instanceof Name) {  
                Name name = (Name)o;  
                //本例认为只要first相同即相等  
                if(this.first.equals(name.first)) {  
                    return true;  
                }  
            }  
            return false;  
        }  
        @Override  
        public int hashCode() {  
            int prime = 31;  
            int result = 1;  
            //hashcode的实现一定要和equals方法的实现对应  
            return prime*result + first.hashCode();  
        }  
        @Override  
        public String toString() {  
            return first + ":" + last;  
        }  
    }  

简单说明一下上面的例子：

上面已经提到HashSet里面放的元素是不允许重复的，那么什么样的元素是重复呢，重复的定义是什么？

上面例子中实现了一个简单的类Name类，并且重写了equals方法与hashCode方法，那么重复指的是equals方法吗？equals相同就算是重复吗？当然不是这样的。如果我们改写一下hashCode方法，将返回值改为

       return prime*result + first.hashCode() + last.hashCode()

那么HashSet中的size会变为4，但是Name(“Wang”, “wu”)和Name(“Wang”, “san”)其实用equals方法来比较的话其实是相同的。

       Name n1 = new Name("W", "x");

    Name n2 = new Name("W", "y");

    System.out.println(n1.equals(n2));

也就是说上面代码会输出true。

这样我们是不是可以这样认为：如果hashCode相同的话再判断equals的返回值是否为true，如果为true则相同，即上面说的重复。如果hashCode不同那么一定是不重复的？

由此看来equals相同，hashCode不一定相同，equals和hashCode的返回值不是绝对关联的？当然我们实现equals方法时是要根据hashCode方法实现的，必须建立关联关系，也就是说正常情况下equals相同，则hashCode的返回值应该是相同的。

Ø  LinkedHashSet的特点、实现机制及使用方法

a)      LinkedHashSet的特点：

LinkedHashSet保证了按照插入顺序有序，继承自HashSet，没有实现新的可以使用的方法。

b)      LinkedHashSet实现机制：

LinkedHashSet继承自HashSet，构造时使用了在HashSet中被忽略的构造方法：

    /** 
      * Constructs a new, empty linked hash set.  (This package private 
      * constructor is only used by LinkedHashSet.) The backing 
      * HashMap instance is a LinkedHashMap with the specified initial 
      * capacity and the specified load factor. 
      * 
      * @param      initialCapacity   the initial capacity of the hash map 
      * @param      loadFactor        the load factor of the hash map 
      * @param      dummy             ignored (distinguishes this 
      *             constructor from other int, float constructor.) 
      * @throws     IllegalArgumentException if the initial capacity is less 
      *             than zero, or if the load factor is nonpositive 
      */  
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {  
        map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  
    }  

由上面JDK代码可以看出LinkedHashSet底层是使用LinkedHashMap实现的。

所以在实现上是比较简单的，是根据dummy这个参数，我们不需要传入，选择构造的是HashSet还是LinkedHashSet。

c)      LinkedHashSet的使用方法：

由于LinkedHashSet继承自HashSet，并且没有提供额外的供使用的方法，所以在使用时与HashSet基本相同，只是面临的是选择的问题。我们根据需要选择不同的数据结构来实现我们的需求。

Ø  CopyOnWriteArraySet的特点、实现机制及使用方法

a)      CopyOnWriteArraySet的特点：

CopyOnWriteArraySet是java.util.concurrent包中的一个类，继承自AbstractSet，底层使用CopyOnWriteArrayList实现，拥有Set的特点，也具有ArrayList的特点，并且是线程安全的类。

b)      CopyOnWriteArraySet的实现机制：

在实现时使用了写时拷贝的方法以及使用重入锁实现了线程的同步，底层使用CopyOnWriteArrayList来构造出一个实例对象，在添加元素时调用CopyOnWriteArrayList的addIfAbsent方法保证数据不重复，其它实现与CopyOnWriteArrayList类似。

c)      CopyOnWriteArraySet的使用方法：

这仍然面临的是一个选择的问题，HashSet底层也是使用数组实现的，它的优点是存取效率很高，当负载因子很小时，几乎可以达到O(1)级的存取速度，但是它不是线程安全的。当我们需要在多线程并发环境下使用时可以考虑使用这个类，当然为了实现线程安全，这不是一个唯一的方法。

Ø  TreeSet的特点、实现机制及使用方法

a)      TreeSet的特点：

TreeSet中所放的元素是有序的，并且元素是不能重复的。

b)      TreeSet的实现机制：

TreeSet是如何保持元素的有序不重复的？

首先TreeSet底层使用TreeMap实现，和HashSet一样，将每个要放入的元素放到key的位置，value位置放的是一个Object类型的常量。

在JDK源码中有下面一段注释：

    /** 
         * Constructs a new, empty tree set, sorted according to the 
         * natural ordering of its elements.  All elements inserted into 
         * the set must implement the {@link Comparable} interface. 
         * Furthermore, all such elements must be <i>mutually 
         * comparable</i>: {@code e1.compareTo(e2)} must not throw a 
         * {@code ClassCastException} for any elements {@code e1} and 
         * {@code e2} in the set.  If the user attempts to add an element 
         * to the set that violates this constraint (for example, the user 
         * attempts to add a string element to a set whose elements are 
         * integers), the {@code add} call will throw a 
         * {@code ClassCastException}. 
     */  

从注释中可以看出保证不重复的关键因素不是hashCode和equals方法，而是compareTo。也就是说要加入的元素要实现Comparable接口。

c)      TreeSet的使用方法：

在总结HashSet的使用方法时，我们用到了一个例子，那么在使用TreeSet时同样是一个选择的问题，我们是否要保证插入的元素有序（不是按插入顺序有序，而是根据compareTo的返回值排序）是我们选择使用那种类型的Set的一个标准。（我不是专家，我只是菜鸟，欢迎拍砖）

Ø  ConcurrentSkipListSet的特点、实现机制及使用方法

a） ConcurrentSkipListSet的特点：

首先必须说的是这个类的名字很是让我奇怪，就像我当时奇怪CopyOnWriteArrayList一样，觉得这是一个比较长的名字，但是当我查了Copy-on-Write的意思时我就不再奇怪了，甚至让我猜到了它的实现机制。

那么Concurrent-Skip是什么意思呢？并行跳过？

与大多数其他并发 collection 实现一样，此类不允许使用 null 元素，因为无法可靠地将 null 参数及返回值与不存在的元素区分开来。

b） ConcurrentSkipListSet的实现机制：

ConcurrentSkipListSet底层是使用ConcurrentSkipListMap实现的。那么并行跳过到底是什么意思，本人暂时不能做出总结。⊙﹏⊙b汗

c） ConcurrentSkipListSet的使用方法：

⊙﹏⊙b汗