集合框架 Set篇---HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipList

Set
---------
1.HashSet

2.LinkedHashSet
3.TreeSet
4.CopyOnWriteArraySet
5.ConcurrentSkipListSet

---------------------HashSet-------------------------

HashSet实现了AbstractSet，由下面的HashSet源码容易看出，其内部依赖于HashMap的实现。其迭代顺序是不能保证的，元素存储是无序的。

public class HashSet<E> extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{
    /*----------成员变量-------------*/
   private transient HashMap<E,Object>map;//内部的实现依赖于HashMap 

    // 一个Object对象作为HashMap中value值的填充，该值对set来说是没有什么意义的
    private static final Object PRESENT = new Object();
    /*------------------------------*/

    /*----------构造方法-------------*/
    /**
     *创建一个空的集合，实际上创建一个空的HashMap
     */
    public HashSet() {
        map = new HashMap<E,Object>();
    }

    /**
     * 把集合作为set的初始化数据，并对对应的HashMap的容量进行指定
     */
    public HashSet(Collection<? extends E> c) {
       map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
    }

    /**
     * 指定初始容量及负载因子（这些概念可以参考HashMap的实现部分）
     */
    public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }

    /**
     * 指定初始容量（默认负载因子为0.75）
     */
    public HashSet(int initialCapacity) {
       map = new HashMap<E,Object>(initialCapacity);
    }

    /**
     *创建一个以LinkedHashMap为实现的LinkedHashSet时，调用该构造方法
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
         map = newLinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }
    /*------------------------------*/

    /**
     * 通过HashMap的keySet返回一个无序的迭代器Iterator
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * 集合中元素的个数 
     */
    public int size() {
        return map.size();
    }

    /**
     * 判断集合是否为空
     */
    public boolean isEmpty() {
         return map.isEmpty();
    }

    /**
     *是否包含某个元素
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * 添加元素的操作
     */
    public boolean add(E e) {
         return map.put(e, PRESENT)==null;
    }

    /**
     * 删除元素的操作
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * 清空集合
     */
    public void clear() {
         map.clear();
    }

    /**
     * 返回一个集合的“浅拷贝”对象
     */
    public Object clone() {
          try {
              HashSet<E> newSet = (HashSet<E>) super.clone();
              newSet.map = (HashMap<E, Object>) map.clone();
              return newSet;
            } catch (CloneNotSupportedException e) {
                 throw new InternalError();
          }
    }

    /**
     * 持久化集合时的写操作
     */
    private void writeObject(java.io.ObjectOutputStream s)  throws java.io.IOException {
         // Write out any hidden serialization magic
         s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
       for (Iterator i=map.keySet().iterator(); i.hasNext(); )
              s.writeObject(i.next());
    }

    /**
     * 持久化集合时的读操作
     */
    private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
         s.defaultReadObject();

        // Read in HashMap capacity and load factor and create backing HashMap
        int capacity = s.readInt();
        float loadFactor = s.readFloat();
        map = (((HashSet)this) instanceof LinkedHashSet ? new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in size
        int size = s.readInt();

       // Read in all elements in the proper order.
       for (int i=0; i<size; i++) {
            E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }
}

---------------------LinkedHashSet-------------------------

//下面就是LinkedHashSet的主要实现，内部出了构造方法，没有其他的任何代码，LinkedHashSet是HashSet的实现，

//通过调用HashSet中的构造方法，其背后是依赖于LinkedHashMap实现的，所以可以保持集合的元素的插入的顺序。

public class LinkedHashSet<E> extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {

    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-------------------------

//TreeSet，一个排序的Set集合，底层依赖于TreeMap的实现
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{
    private transient NavigableMap<E,Object> m;         //TreeMap也实现了NavigableMap接口
    private static final Object PRESENT = new Object(); //一个虚拟的填充值用的对象（对set集合没有实际意义）

    /*--------------构造方法--------------*/
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    public TreeSet() {
       this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator) {
       this(new TreeMap<E,Object>(comparator));
    }
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
    /*------------------------------------*/
    /**
     * 返回升序（asc）排列集合的迭代器
     */
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

    /**
     * 返回降序（desc）排列集合的迭代器
     */
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }

    /**
     * 返回一个降序的Set集合
     */
    public NavigableSet<E> descendingSet() {
        return new TreeSet(m.descendingMap());
    }

    /**
     * 元素个数size
     */
    public int size() {
        return m.size();
    }

    /**
     * 判断是否为空集合
     */
    public boolean isEmpty() {
        return m.isEmpty();
    }

    /**
     * 是否包含某元素
     */
    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    /**
     *添加元素
     */
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

    /**
     *移除元素
     */
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

    /**
     * 清空集合
     */
    public void clear() {
        m.clear();
    }

    /**
     * 把给定的集合中的元素添加到set集合中（依赖于TreeMap的实现）
     */
    public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

    /*--以下是由于实现-NavigableSet和SortedSet接口而实现的一些方法，根据方法名很容易判断其作用，不再一一说明----*/
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
        return new TreeSet<E>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
    }

    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<E>(m.headMap(toElement, inclusive));
    }
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<E>(m.tailMap(fromElement, inclusive));
    }
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

    public Comparator<? super E> comparator() {
        return m.comparator();
    }
    public E first() {
        return m.firstKey();
    }
    public E last() {
        return m.lastKey();
    }

    // NavigableSet API methods

    public E lower(E e) {
        return m.lowerKey(e);
    }
    public E floor(E e) {
        return m.floorKey(e);
    }
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

    public E higher(E e) {
        return m.higherKey(e);
    }
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null)? null : e.getKey();
    }
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null)? null : e.getKey();
    }
   
  //writeObject readObject等方法没有一一列出
}

--------------------CopyOnWriteArraySet----------------

CopyOnWriteArraySet是一个依赖CopyOnWriteArrayList实现的 Set集合。因此，它共享以下相同的基本属性：

-它最适合于具有以下特征的应用程序：set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
-它是线程安全的。
-因为通常需要复制整个基础数组，所以可变操作（add、set 和 remove 等等）的开销很大。
-迭代器不支持可变 remove 操作。
-使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

//CopyOnWriteArraySet的源码实现
public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    private final CopyOnWriteArrayList<E> al;//内部实现所依赖的CopyOnWriteArrayList对象

    /**
     * 空构造
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
    /**
     * 传入集合变量的构造
     */
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        al = new CopyOnWriteArrayList<E>();
        al.addAllAbsent(c);
    }

    /**
     * 通过调用CopyOnWriteArrayList的方法，实现该Set集合的操作
     */
    public int size() {
         return al.size();
    }
    public boolean isEmpty() {
         return al.isEmpty();
    }
    public boolean contains(Object o) {
         return al.contains(o);
    }
    public Object[] toArray() {
         return al.toArray();
    }
    public <T> T[] toArray(T[] a) {
         return al.toArray(a);
    }
    public void clear() {
        al.clear();
    }
    public boolean remove(Object o) {
         return al.remove(o);
    }
    public boolean add(E e) {
         return al.addIfAbsent(e);//这就保证了Set集合不存在相同的元素
    }
    public boolean containsAll(Collection<?> c) {
         return al.containsAll(c);
    }
    public boolean addAll(Collection<? extends E> c) {
         return al.addAllAbsent(c) > 0;
    }
    public boolean removeAll(Collection<?> c) {
         return al.removeAll(c);
    }
    public boolean retainAll(Collection<?> c) {
         return al.retainAll(c);
    }
    public Iterator<E> iterator() {
         return al.iterator();
    }

    /**
     * 重写Set的equals方法：作用是比较两个set集合的是否相等
     */
    public boolean equals(Object o) {
        if (o == this) //如果是同一个set对象,就相等
            return true;
        if (!(o instanceof Set))//不是Set类别，不可能相等
            return false;
        Set<?> set = (Set<?>)(o);
         Iterator<?> it = set.iterator();

        // 下面的算法复杂度为O(n^2)，所以CopyOnWriteArraySet过大的情况效率会比较低，不推荐。
        //  Use a single snapshot of underlying array
         Object[] elements = al.getArray();
         int len = elements.length;
        // Mark matched elements to avoid re-checking
        boolean[] matched = new boolean[len];
        int k = 0;
        //通过迭代比较每一个元素是否和al.getArray()获得的数组元素是否相同
        outer: while (it.hasNext()) {
            if (++k > len)
                return false;
            Object x = it.next();
            for (int i = 0; i < len; ++i) {
                if (!matched[i] && eq(x, elements[i])) {
                    matched[i] = true;
                    continue outer;
                }
            }
           return false;
        }
        return k == len;
    }

    /**
     * 考虑null的情况下，判断equals
     */
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }
}

-------------------ConcurrentSkipListSet--------------------------

ConcurrentSkipListSet是一个基于 ConcurrentSkipListMap 的可缩放并发 NavigableSet 实现。set 的元素可以根据它们的自然顺序进行排序，也可以根据创建 set 时所提供的 Comparator 进行排序，具体取决于使用的构造方法。
此实现为 contains、add、remove 操作及其变体提供预期平均 log(n) 时间开销。多个线程可以安全地并发执行插入、移除和访问操作。

//ConcurrentSkipListSet的源码实现
public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private final ConcurrentNavigableMap<E,Object> m;//基于 ConcurrentSkipListMap

    /*---------------------------构造方法-----------------------------*/
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E,Object>();
    }

    public ConcurrentSkipListSet(Comparator<? super E> comparator) {
        m = new ConcurrentSkipListMap<E,Object>(comparator);
    }

    public ConcurrentSkipListSet(Collection<? extends E> c) {
        m = new ConcurrentSkipListMap<E,Object>();
        addAll(c);
    }

    public ConcurrentSkipListSet(SortedSet<E> s) {
        m = new ConcurrentSkipListMap<E,Object>(s.comparator());
        addAll(s);
    }

    ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
        this.m = m;
    }
    /*-----------------------------------------------------------------*/

    public ConcurrentSkipListSet<E> clone() {
        ConcurrentSkipListSet<E> clone = null;
         try {
             clone = (ConcurrentSkipListSet<E>) super.clone();
            clone.setMap(new ConcurrentSkipListMap(m));
         } catch (CloneNotSupportedException e) {
             throw new InternalError();
         }

        return clone;
    }

    /* ----------------基于 ConcurrentSkipListMap，实现该Set集合的操作  -------------- */
    public int size() {
         return m.size();
    }

    public boolean isEmpty() {
         return m.isEmpty();
    }

    public boolean contains(Object o) {
         return m.containsKey(o);
    }

    public boolean add(E e) {
         return m.putIfAbsent(e, Boolean.TRUE) == null;
    }

    public boolean remove(Object o) {
         return m.remove(o, Boolean.TRUE);
    }
    public void clear() {
         m.clear();
    }
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

    public Iterator<E> descendingIterator() {
         return m.descendingKeySet().iterator();
    }


    /* ---------------- 重写AbstractSet 的equals方法-------------- */

    public boolean equals(Object o) {
        // Override AbstractSet version to avoid calling size()
         if (o == this)
             return true;
         if (!(o instanceof Set))
             return false;
         Collection<?> c = (Collection<?>) o;
        try {
            return containsAll(c) && c.containsAll(this);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    public boolean removeAll(Collection<?> c) {
        // Override AbstractSet version to avoid unnecessary call to size()
        boolean modified = false;
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            if (remove(i.next()))
                modified = true;
        return modified;
    }

    /* ---------------- 实现NavigableSet接口的操作-------------- */

    public E lower(E e) {
        return m.lowerKey(e);
    }
    public E floor(E e) {
        return m.floorKey(e);
    }
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }
    public E higher(E e) {
        return m.higherKey(e);
    }

    public E pollFirst() {
        Map.Entry<E,Object> e = m.pollFirstEntry();
        return e == null? null : e.getKey();
    }

    public E pollLast() {
        Map.Entry<E,Object> e = m.pollLastEntry();
        return e == null? null : e.getKey();
    }


    /* ---------------- 实现SortedSet接口的操作 -------------- */

    public Comparator<? super E> comparator() {
        return m.comparator();
    }

    public E first() {
        return m.firstKey();
    }
    public E last() {
        return m.lastKey();
    }

    public NavigableSet<E> subSet(E fromElement,boolean fromInclusive, E toElement, boolean toInclusive) {
         return new ConcurrentSkipListSet<E>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
    }
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
         return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
    }
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
         return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
    }

    public NavigableSet<E> subSet(E fromElement, E toElement) {
         return subSet(fromElement, true, toElement, false);
    }

    public NavigableSet<E> headSet(E toElement) {
         return headSet(toElement, false);
    }
    public NavigableSet<E> tailSet(E fromElement) {
         return tailSet(fromElement, true);
    }

    public NavigableSet<E> descendingSet() {
         return new ConcurrentSkipListSet(m.descendingMap());
    }

    // Support for resetting map in clone
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long mapOffset;
    static {
        try {
            mapOffset = unsafe.objectFieldOffset(ConcurrentSkipListSet.class.getDeclaredField("m"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    private void setMap(ConcurrentNavigableMap<E,Object> map) {
        unsafe.putObjectVolatile(this, mapOffset, map);
    }

}