539
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的包，裏麵有很多實用的類：
https://commons.apache.org/collections/
Google的包，裏麵有很多並發的牛B類：
AtomicLongMap，等等
大對象的數據結構：https://github.com/HugeCollections/Collections
注意事項：
並發容器多數不能使用null值
最後更新：2017-04-02 16:47:36