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值

轉載于:https://www.cnblogs.com/hgb1116/p/5967992.html

總結

以上是生活随笔為你收集整理的java中的数据结构总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。