java util_java.util包中集合詳解

本文隻是集合的概述，介紹集合之間的關系，以及各種集合的異同，不會深入介紹具體的實作，具體實作的介紹，可以參見文中提供的連結。

java集合概述

java集合整體分為collection和map兩種，接口關系如下：

image.png

image.png

Iterable

為了實作new loop，類需要繼承Iterable，例如：

List list = new ArrayList();

for(Object o : list){

//do something o;

}

從java8開始，新增forEach

Collection

Collection定義了集合的基本操作，詳細函數可以參考JavaDoc。

List

List在java.util包中的實作(其中cocurrent包中還有并行實作)，主要有以下幾種：

java.util.ArrayList

java.util.LinkedList

java.util.Vector

java.util.Stack

是否容許空

是否容許重複

是否有序(周遊輸出保持插入順序)

是否線程安全

ArrayList

是

是

是

否

LinkList

是

是

是

否

Vector

是

是

是

是

Stack

是

是

是

是

實作類的繼承整體關系如下：

ArrayList

LinkedList

Vector

Stack

ArrayList是通過數組實作，LinkedList是通過雙向連結清單實作。這樣就決定了他們兩個的使用範圍。LinkedList在以下情況下，比較合适：1)如果資料删除、随機插入比較多；2)随機資料的讀取比較少。如果随機讀取多于寫入，并且寫入也是追加寫入，那麼可以使用ArrayList，但是最好預估資料量，設定ArrayList的初始大小。ArrayList和LinkedList的詳細對比。實作介紹參考： 圖解集合2：LinkedList

Vector和Stack也是通過數組實作，線程安全，但ArrayList和LinkedList沒有保證線程安全。

是否容許空

是否容許重複

是否有序(周遊輸出保持插入順序)

是否線程安全

ArrayList

是

是

是

否

LinkList

是

是

是

否

Vector

是

是

是

是

Stack

是

是

是

是

Set

Set中元素不可以重複。在java.util包中的實作，主要有以下幾種：

java.util.EnumSet

java.util.HashSet

java.util.LinkedHashSet

java.util.TreeSet

EnumSet可以應用在枚舉分組時，詳細介紹可以參考《Java中的EnumSet》。

image.png

HashSet

TreeSet

LinkedHashSet

HashSet是使用HashMap實作的，元素無序。 add，delete和contain方法具有恒定的時間複雜度O(1)。 TreeSet是使用樹結構(紅黑樹TreeMap)實作的，集合中的元素是有序的，指的是排序。但add，delete 和contain方法的時間複雜度為O(log(n))，提供了幾種方法first()，last()，headSet()，tailSet()處理有序集(SortedSet中定義)。LinkedHashSet介于HashSet和TreeSet之間，是LinkedHashMap來實作的，提供了插入的順序。 基本方法的時間複雜度是O(1)。詳情參考《HashSet vs. TreeSet vs. LinkedHashSet》。

是否容許空

是否容許重複

是否有序(周遊輸出保持插入順序)

是否線程安全

HashSet

是

否

否

否

TreeSet

是

否

否

否

LinkedHashSet

是

否

是

否

Queue

Queue在java.util包中的實作主要有以下兩個：

java.util.LinkedList

java.util.PriorityQueue

Deque定義了在Queue兩端進行insert和remove函數(addFirst/addLast)，經典是實作是LinkedList。

PriorityQueue是從JDK1.5開始提供的新的資料結構接口，它是一種基于優先級堆的極大優先級隊列(基于數組的完全二叉樹)。優先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素。如果不提供Comparator的話，優先隊列中元素預設按自然順序排列，也就是數字預設是小的在隊列頭，字元串則按字典序排列(參閱 Comparable)，也可以根據 Comparator 來指定，這取決于使用哪種構造方法。優先級隊列不允許 null 元素。依靠自然排序的優先級隊列還不允許插入不可比較的對象(這樣做可能導緻 ClassCastException),更多内容參考《Java PriorityQueue工作原理及實作》。

是否容許空

是否容許重複

是否有序(周遊輸出保持插入順序)

是否線程安全

PriorityQueue

否

是

否

否

周遊的時候，隻保證第一個是最小值(或最大值)，如：

Queue priorityQueue=new PriorityQueue();

priorityQueue.add(5);

priorityQueue.add(2);

priorityQueue.add(1);

priorityQueue.add(10);

priorityQueue.add(3);

System.out.println("");

Iterator iterator1=priorityQueue.iterator();

while (iterator1.hasNext()){

System.out.print(iterator1.next()+" ");

}

output:1 3 2 10 5

Map

Map在java.util包中的實作主要包括以下幾個：

java.util.HashMap

java.util.Hashtable

java.util.EnumMap

java.util.IdentityHashMap

java.util.LinkedHashMap

java.util.Properties

java.util.TreeMap

java.util.WeakHashMap

HashMap vs TreeMap vs LinkedHashMap

我們經常使用的也就是HashMap和TreeMap。HashMap線程不安全,不保證内部存儲元素的任何順序，詳情參考Java HashMap工作原理及實作。TreeMap保證了存儲元素的順序。

image.png

HashMap vs Hashtable

Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.

Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

Since synchronization is not an issue for you, I'd recommend HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap.

Differences between HashMap and Hashtable?

是否容許空

是否容許重複

是否有序(周遊輸出保持插入順序)

是否線程安全

HashMap

是

是

否

否

HashTable

否

是

否

是

TreeMap

隻是value容許

是

否

否

LinkedHashMap

是

是

是

否

如果對集合的實作比較感興趣，推薦大家讀取其中連結和參考文獻，最好自己打開源碼讀讀。其中若有纰漏，歡迎指正。

參考