java提高篇（二十）-----集合大家族

Feb 10, 2017 pm 02:16 PM

在編寫java程式中，我們最常用的除了八種基本資料類型，String物件外還有一個集合類，在我們的程式中到處充斥著集合類別的身影！ java中集合大家族的成員實在是太豐富了，有常用的ArrayList、HashMap、HashSet，也有不常用的Stack、Queue，有線程安全的Vector、HashTable，也有線程不安全的LinkedList、TreeMap等等！

上面的圖片展示了整個集合大的成員以及他們之間的關係。以下就上面的各個介面、基類做一些簡單的介紹(主要介紹各個集合的特點。區別)，更加詳細的介紹會在不久的將來一一講解。

一、Collection介面

Set。 Collection所代表的是一種規則，它所包含的元素都必須遵循一條或多條規則。如有些允許重複而有些則不能重複、有些必須要按照順序插入而有些則是散列，有些支援排序但是有些則不支援。

在Java中所有實現了Collection介面的類別都必須提供兩套標準的建構函數，一個是無參，用於創建一個空的Collection，一個是帶有Collection參數參數的有參構造函數參數，用於建立一個新的Collection，這個新的Collection與傳入進來的Collection具備相同的元素。

二、List介面

List所代表的是有序的Collection，也就是它用某種特定的插入順序來維護元素順序。使用者可以對清單中每個元素的插入位置進行精確地控制，同時可以根據元素的整數索引（在清單中的位置）存取元素，並蒐索清單中的元素。實作List介面的集合主要有：ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList

ArList是一個動態數組，也是我們最常使用的集合。它允許任何符合規則的元素插入甚至包括null。每一個ArrayList都有一個初始容量（10），該容量代表了陣列的大小。隨著容器中的元素不斷增加，容器的大小也會隨著增加而增加。在每次在容器中增加元素的同時都會進行容量檢查，當快溢出時，就會進行擴容操作。所以如果我們明確所插入元素的多少，最好指定一個初始容量值，避免過多的進行擴容操作而浪費時間、效率。

size、isEmpty、get、set、iterator 和 listIterator 作業都以固定時間運作。 add 操作以分攤的固定時間運行，也就是說，添加 n 個元素需要 O(n) 時間（由於要考慮到擴容，所以這不只是添加元素會帶來分攤固定時間開銷那麼簡單）。

ArrayList擅長於隨機存取。同時ArrayList是非同步的。

2.2、LinkedList

對則為一個相同網路介面所以它除了有ArrayList的基本操作方法外還額外提供了get，remove，insert方法在LinkedList的首部或尾部。

由於實現的方式不同，LinkedList不能隨機訪問，它所有的操作都是要按照雙重鍊錶的需要執行。在清單中索引的操作將從開頭或結尾遍歷清單（從靠近指定索引的一端）。這樣做的好處就是可以透過較低的代價在List中進行插入和刪除操作。

與ArrayList一樣，LinkedList也是非同步的。如果多個執行緒同時存取一個List，則必須自行實作存取同步。一個解決方法是在建立List時建構一個同步的List：
List list = Collections.synchronizedList(new LinkedList(...));

與ArrayList相似，但是Vector是同步的。所以說Vector是線程安全的動態數組。它的操作與ArrayList幾乎一樣。

2.4、Stack

從

Stack繼承自Vector，實現一個後進先出堆疊的堆疊的堆疊。 Stack提供5個額外的方法使得Vector得以被當作堆疊使用。基本的push和pop 方法，還有peek方法得到棧頂的元素，empty方法測試堆疊是否為空，search方法檢測一個元素在堆疊中的位置。 Stack剛建立後是空棧。

三、Set介面

Set是一種不含重複元素的不包含重複元素的一種不包含重複元素的一種不包含重複元素。它維持它自己的內部排序，所以隨機存取沒有任何意義。與List一樣，它同樣運行null的存在但只有一個。由於Set介面的特殊性，所有傳入Set集合中的元素都必須不同，同時要注意任何可變對象，如果在對集合中元素進行操作時，導致e1.equals(e2)==true，則必定會產生某些問題。實作了Set介面的集合有：EnumSet、HashSet、TreeSet。

3.1、EnumSet

是

枚舉的專用。所有的元素都是枚舉型別。

3.2、HashSet

以達到其速度最快的集合，因為其速度是基礎的集合，因為其速度來實現其速度最快的集合。它內部元素的順序是由雜湊碼來決定的，所以它不保證set 的迭代順序；特別是它不保證該順序恆久不變。

3.3、TreeSet

基於TreeMap，生成一個內部化的順序來實現排序。它是使用元素的自然順序對元素進行排序，或根據建立Set 時提供的Comparator 進行排序，取決於使用的建構方法。

四、Map介面

Map與List、Setkey同時它也沒有繼承Collection。在Map中它保證了key與value之間的一一對應關係。也就是說一個key對應一個value，所以它不能存在相同的key值，當然value值可以相同。實作map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

4.1、HashMap

以哈希表資料結構實現，且查找物件時透過雜湊函數計算其位置，它是數字化時，它是定義了一個物件時數Entry[] table），元素會透過雜湊轉換函數將元素的雜湊位址轉換成數組中存放的索引，如果有衝突，則使用雜湊鍊錶的形式將所有相同雜湊位址的元素串起來，可能透過查看HashMap.Entry的源碼它是一個單鍊錶結構。

4.2、TreeMap

4.3、 HashTable

也是以哈希表資料結構實現的，解決衝突時與HashMap也一樣也是採用了散列鍊錶的形式，不過性能比HashMap

隊列，它主要分為兩大類，一類是阻塞式隊列，隊列滿了以後再插入元素則會拋出異常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一種佇列則是雙端佇列，支援在頭、尾兩端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

六、異同點

6.1、Vector和ArrayList

1，vector是線程同步的，所以它也是線程安全的，而arraylist是線程異步的，是不安全的。如果不考慮到線程的安全因素，一般用arraylist效率比較高。

2，若集合中的元素的數目大於目前集合數組的長度時，vector增長率為目前數組長度的100%,而arraylist增長率為當前數組長度的50%.如過在集合中使用數據數據量比較大的數據，用vector有一定的優勢。 3，如果找到指定位置的數據，vector和arraylist使用的時間是相同的，都是0(1),這個時候使用vector和arraylist都可以。而如果移動一個指定位置的資料花費的時間為0(n-i)n為總長度，這個時候就應該考慮到使用linklist,因為它移動一個指定位置的資料所花費的時間為0(1),而查詢一個指定位置的資料時所花費的時間為0(i)。

ArrayList 和Vector是採用數組方式存儲數據，此數組元素數大於實際存儲的數據以便增加和插入元素，都允許直接序號索引元素，但是插入數據要設計到數組元素移動等內存數組元素，所以索引資料快插入資料慢，Vector由於使用了synchronized方法（線程安全）所以性能上比ArrayList要差，LinkedList使用雙向鍊錶實現存儲，按序號索引資料需要進行向前或向後遍歷，但是插入數據時只需要記錄本項的前後項即可，所以插入數度較快！

6.2、Aarraylist和Linkedlist

       2.隨機存取get和set，ArrayList覺得優於LinkedList，因為LinkedList要移動指標。
       3.對於新增和刪除操作add和remove，LinedList比較佔優勢，因為ArrayList要移動資料。這一點要看實際情況的。若只對單一資料插入或刪除，ArrayList的速度反而優於LinkedList。但若是批量隨機的插入刪除數據，LinkedList的速度大大優於ArrayList. 因為ArrayList每插入一條數據，要移動插入點及之後的所有數據。

6.3、HashMap與TreeMap

序的結果你就應該使用TreeMap（HashMap中元素的排列順序是不固定的）。 HashMap中元素的排列順序是不固定的）。

2、 HashMap透過hashcode對其內容進行快速查找，而TreeMap中所有的元素都保持著某種固定的順序，如果你需要得到一個有序的結果你就應該使用TreeMap（HashMap中元素的排列順序是不固定的）。集合架構」提供兩種常規的Map實作：HashMap和TreeMap (TreeMap實作SortedMap介面)。

3、在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。但如果您要插入最好的選擇。以自然順序或自訂順序遍歷鍵，那麼TreeMap會更好。。一個實現。 2.同步性:Hashtable是執行緒安全的，也就是說是同步的，而HashMap是線程式不安全的，不是同步的。一張表格的條目的key或value 。