Java中的數據結構一覽
Java的類庫實在是很多，以至于很多人都不太了解，結果總是自己造輪子。
下面匯總了Java中的一些數據結構，加上一些實現的分析，同時備忘。
至于時間復雜度，個人覺得寫出來的用處不大。如果明白它是怎么實現的，那自然就知道它的時間復雜度。
如果不理解它的實現，把時間復雜度背得再熟也沒用。
接口：
Collection<E>
子接口：
BlockingDeque<E>, BlockingQueue<E>, Deque<E>, List<E>, NavigableSet<E>,
Queue<E>, Set<E>, SortedSet<E>
實現類：
ArrayBlockingQueue, ArrayDeque, ArrayList, ConcurrentLinkedQueue,
ConcurrentSkipListSet, CopyOnWriteArrayList, CopyOnWriteArraySet, DelayQueue,
EnumSet, HashSet, LinkedBlockingDeque, LinkedBlockingQueue, LinkedHashSet,
LinkedList, PriorityBlockingQueue, PriorityQueue, Stack, SynchronousQueue, TreeSet, Vector
List<E>
實現類：
ArrayList, CopyOnWriteArrayList, LinkedList,Stack, Vector
Queue<E>
子接口：
BlockingDeque<E>, BlockingQueue<E>, Deque<E>
實現類：
ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque,
LinkedBlockingQueue, LinkedList, PriorityBlockingQueue, PriorityQueue, SynchronousQueue
Set<E>
子接口：
NavigableSet<E>, SortedSet<E>
實現類：
ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, LinkedHashSet, TreeSet
Map<K,V>
子接口：
ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, SortedMap<K,V>
實現類：
ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap,
LinkedHashMap, TreeMap, WeakHashMap
并發與線程安全等
通常含有Concurrent，CopyOnWrite，Blocking的是線程安全的，但是這些線程安全通常是有條件的，所以在使用前一定要仔細閱讀文檔。
具體實現：
List<E>系列：
ArrayList<E>，如其名，但是其容量增長計劃是newCapacity = (oldCapacity * 3)/2 + 1，和C++通常的Vector是翻倍的策略不同。
CopyOnWriteArrayList<E>，里面有一個ReentrantLock，每當add時，都鎖住，把所有的元素都復制到一個新的數組上。
只保證歷遍操作是線程安全的，get操作并不保證，也就是說如果先得到size，再調用get(size-1)，有可能會失效
那么CopyOnWriteArrayList是如何實現線程安全的迭代操作？
在迭代器中保存原數組。
LinkedList<E>，標準雙向鏈表
Vector<E>，過時，多數方法上加上了synchronized
Stack<E>，繼承自Vector，過時，優先應使用 Deque<Integer> stack = new ArrayDeque<Integer>();
Queue<E>系列：
LinkedList<E>，見List<E>系列
ArrayDeque<E>，內部用一個數組保存元素，有int類型head和tail的。
PriorityQueue<E>，內部用一個數組來保存元素，但數組是以堆的形式來組織的，因此是有序的。
PriorityBlockingQueue<E>，包裝了一個PriorityQueue<E>，一個ReentrantLock，一個Condition，TODO
ArrayBlockingQueue<E>，TODO
ConcurrentLinkedQueue<E>，TODO
DelayQueue<E>，TODO
LinkedBlockingDeque<E>，TODO
LinkedBlockingQueue<E>，TODO
SynchronousQueue<E>，TODO
Deque<E>（雙端隊列）系列：
ArrayDeque<E>，見Queue系列
LinkedList<E>，見List系列
LinkedBlockingDeque<E>，TODO
Set系列：
HashSet，包裝了一個HashMap：
public HashSet() {
map = new HashMap<E,Object>();
}
TreeSet，包裝了一個TreeMap，參考HashSet
LinkedHashSet，包裝了LinkedHashMap，參考HashSet
EnumSet，TODO
CopyOnWriteArraySet，簡單包裝了CopyOnWriteArrayList，注意這個Set的get的時間復雜度。
ConcurrentSkipListSet，包裝了一個ConcurrentSkipListMap，參考HashSet。
Map系列：
HashMap<K,V>，標準鏈地址法實現
TreeMap<K,V>，紅黑二叉樹
LinkedHashMap<K,V>，在Entry中增加before和after指針把HashMap中的元素串聯起來，這樣在迭代時，就可以按插入順序歷遍。
EnumMap，TODO
ConcurrentHashMap，參考之前的文章
ConcurrentSkipListMap，TODO，log(n)的時間復雜度，有點像多級鏈表保存的，貌似有點像redis中的SortedSet的實現
Hashtable，過時
IdentityHashMap，正常的HashMap中比較是用equals方法，這個用的是“==”比較符
WeakHashMap<K,V>，弱引用的HashMap，正常的 HashMap是強引用，即里面的value不會被GC回收，
在WeakHashMap<K,V>中，V中最好是WeakReference 類型的，用像這樣的代碼：m.put(key, new WeakReference(value))。
其它的一些實用的第三方的數據結構：
LRUCache，LongHashMap，Java7中的LinkedTransferQueue，
Apache的包，里面有很多實用的類：
http://commons.apache.org/collections/
Google的包，里面有很多并發的牛B類：
AtomicLongMap，等等
大對象的數據結構：https://github.com/HugeCollections/Collections
注意事項：
并發容器多數不能使用null值