JAVA集合 - SET

set.png

对集合的操作

对集合主要有三种操作：

1. 插入和删除，以及在指定位置插入和删除
2. 获取元素
3. 对集合进行迭代

不同的集合在这三个方面有不同的性能，没有哪个集合是完美的。

数据结构

实现集合的四种数据结构：

1. 数组（Arrays）
   优点：根据位置（positon）快速访问元素。
   缺点：插入和删除元素慢，因为需要重新调整元素位置。
   如：ArrayList, CopyOnWriteArrayList, EnumSet, EnumMap

2. 链表（Linked list）
   优点：插入和删除元素快。
   缺点：根据位置访问元素慢，因为需要从头到尾向下找。
   如：ConcurrentSkipListSet, LinkedList, ConcurrentLinkedQueue, LinkedBlockingQueue, ConcurrentSkipListMap

3. 哈希表（Hash tables），根据内容进行索引，不像数组和链表提供基于位置的访问。
   优点：根据内容访问元素，以及插入和删除都比较快。
   缺点：无法根据位置索引访问元素。
   如：HashSet, LinkedHashSet, HashMap, LinkedHashMap, WeakHashMap, IdentityHashMap, ConcurrentHashMap

4. 树（Trees）
   根据内容管理其元素，根据指定的排序方法保存元素。
   优点：有序，插入和删相对较快。
   缺点：无法根据位置索引访问元素。
   如：TreeSet, TreeMap

具体的集合实现可能用到多种数据结构，比如在JAVA8中，HashMap就可能用到链表，也可能用到树。

集合的并发访问

当一个集合被并发访问，那么就要处理线程安全的问题，JAVA提供了几种机制来实现安全的并发访问：

1. Synchronized
   比如：Hashtable, Vector，其所有方法都是同步的，导致并发性能极差，应该避免使用。
   同样还有Collections.synchronized下的系列同步包装方法。

   List<Object> synchronizedList = Collections.synchronizedList(new ArrayList<>());
   

2. copy-on-write
   使用数组存储集合元素，并且数组是immutable的，任何对集合的修改（新增/删除），都是导致新数组的创建，
   需要同步的仅仅是新数组替换旧数组，是通过将变量声明为volatile来实现的。
   这种类型的集合适合使用读场景，因数不需要同步也不需要数组复制。
   比如：CopyOnWriteArraySet, CopyOnWriteArrayList
3. CAS（compare and swap）
   CAS其字面意思就是比较并替换，其大概过程是：首先复制变量的值，再开始其要做的计算，当计算完成需要更新变量的值时，会先比较此时变量的值是否和开始时复制的变量一致，如果一致说明没有被其他线程修改过，那就可以完成更新。如果不一致，则说明已经被其他线程修改过了，可以重新计算也可以放弃，根据具体算法需要决定。
   CAS有ABA问题，可以通过AtomicStampedReference解决，这里就不展开了。
   比如：ConcurrentLinkedQueue, ConcurrentSkipListMap
4. java.util.concurrent.locks.Lock
   JAVA中的锁除了synchronized，还有ReentrantLock, ReentrantReadWriteLock, StampedLock。
   比如：LinkedBlockingQueue就利用ReentrantLock来保证同步。至于各种锁的区别，此处就不展开了，如有兴趣Google一下。

SET

SortedSet (java.util)
    NavigableSet (java.util)
        ConcurrentSkipListSet (java.util.concurrent)
        TreeSet (java.util)
AbstractSet (java.util)
    TreeSet (java.util)
    HashSet (java.util)
        LinkedHashSet (java.util)
    EnumSet (java.util)
        JumboEnumSet (java.util)
        RegularEnumSet (java.util)
    CopyOnWriteArraySet (java.util.concurrent)
    ConcurrentSkipListSet (java.util.concurrent)

HashSet, TreeSet, LinkedHashSet

Set中的元素不能重复，其实现主要有三种：HashSet, TreeSet, LinkedHashSet，简单来说如果想要fast set就使用HashSet；如果需要有序使用TreeSet；如果想保持插入顺序使用LinkedHashSet.

	HashSet	LinkedHashSet	TreeSet
如何实现？	使用HashMap实现	使用LinkedHashMap实现	使用TreeMap实现
元素顺序	没有任何顺序	保持插入顺序	根据提供的Comparator排序
性能	A (优)	A--（良）	C （差）
是否允许NULL	最多允许一个NULL	最多允许一个NULL	JAVA7之前允许第一个元素为NULL，从7开始不允许有NULL
如果判断元素是否存在	equals() and hashCode()	equals() and hashCode()	compare() or compareTo() 比较结果为0即为相同
时间复杂度	O(1)	O(1)	O(log(n))

他们的相同点：

1. 都不允许元素重复
2. 都不是线程安全的
3. 都是fail-fast的，如果在创建Iterator之后，修改集合会抛出ConcurrentModificationException。

http://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/
http://www.benchresources.net/hashset-vs-linkedhashset-vs-treeset-in-java/

---

CopyOnWriteArraySet

CopyOnWriteArraySet是通过CopyOnWriteArrayList实现的，其底层实现是数组，且该数组是不可变的，如果要修改CopyOnWriteArraySet的内容就需要重新创建新的数组。
如果需要频繁修改Set，不应该使用CopyOnWriteArraySet。在对CopyOnWriteArraySet, CopyOnWriteArrayList进行遍历时，遍历的只是底层数组的快照，而且该Iterator不支持remove方法。

EnumSet

此集合用来存放枚举类型，并且只能存放同一种枚举类型，其底层是基与位操作(bit manipulation)来实现，所以性能很高，即便是containsAll, retainAll这类操作依然很快。永远不会抛出ConcurrentModificationException，不是线程安全的，如果需要线程同步，则：

Set<MyEnum> s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));

The iterators of EnumSet are weakly consistent.

ConcurrentSkipListSet

基与跳表（skip list）实现的并发集合，是通过ConcurrentSkipListMap实现的，类似TreeSet该集合也会对元素进行排序，支持并发操作，通过CAS实现的。
跳表有多层链表，最底层存放了所有的元素，如果机率（probability）设置为0.5，那么上一层会存放下一层一半数量的元素，此时如果有新的元素插入，首先会插入最底层，是否插入上一层会投币决定是否插入。

image

The iterators of ConcurrentSkipListSet are weakly consistent.

Skip list1
Skip list2

Set集合的时间复杂度

	add	contains	remove	next	notes	是否允许为NULL
HashSet	O(1)	O(1)	O(1)	O(h/n)	h是hash表容量	最多一个NULL
LinkedHashSet	O(1)	O(1)	O(1)	O(1)		最多一个NULL
CopyOnWriteArraySet	O(n)	O(n)	O(n)	O(1)		最多一个NULL
EnumSet	O(1)	O(1)	O(1)	O(1)		不允许
TreeSet	O(log n)	O(log n)	O(log n)	O(log n)		7之前允许第一个元素为NULL，从7开始不允许为NULL
ConcurrentSkipListSet	O(log n)	O(log n)	O(log n)	O(1)		不允许

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/changes8.html
https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist