Java進階總結——集合

說明：對于以上的框架圖有如下幾點說明

1.所有集合類都位于java.util包下。Java的集合類主要由兩個接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，這兩個接口又包含了一些子接口或實現類。

集合接口：6個接口（短虛線表示），表示不同集合類型，是集合框架的基礎。
抽象類：5個抽象類（長虛線表示），對集合接口的部分實現。可擴展為自定義集合類。
實現類：8個實現類（實線表示），對接口的具體實現。
Collection 接口是一組允許重復的對象。
Set 接口繼承 Collection，集合元素不重復。
List 接口繼承 Collection，允許重復，維護元素插入順序。
Map接口是鍵－值對象，與Collection接口沒有什么關系。
9.Set、List和Map可以看做集合的三大類：
List集合是有序集合，集合中的元素可以重復，訪問集合中的元素可以根據元素的索引來訪問。
Set集合是無序集合，集合中的元素不可以重復，訪問集合中的元素只能根據元素本身來訪問（也是集合里元素不允許重復的原因）。
Map集合中保存Key-value對形式的元素，訪問時只能根據每項元素的key來訪問其value。

二 總體分析

看上面的框架圖，先抓住它的主干，即Collection和Map。我們在業務代碼中用的最多的也是基于這兩種接口類型實現的具體集合類。同時在每個接口以及實現類中我們也實現了相應的迭代器以便遍歷集合中的元素。
1.Collection是一個接口，包含了集合的基本屬性和操作，對應的實現類有list和set兩大分支。
其中List是一個有序隊列，允許重復元素的存在。其實現有linkedlist,linkedHashList等；
set是一個不允許有重復元素存在的集合，其實現有hashset和treeset，hshset依賴于hshmap。
2.Map是一個映射接口，即key-value鍵值對。Map中的每一個元素包含“一個key”和“key對應的value”。AbstractMap是個抽象類，它實現了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是繼承于AbstractMap。Hashtable雖然繼承于Dictionary，但它實現了Map接口。
3.再看Iterator。它是遍歷集合的工具，即我們通常通過Iterator迭代器來遍歷集合。我們說Collection依賴于Iterator，是因為Collection的實現類都要實現iterator()函數，返回一個Iterator對象。ListIterator是專門為遍歷List而存在的。

三 Collection接口

1.List接口
List集合代表一個有序集合，集合中每個元素都有其對應的順序索引。List集合允許使用重復元素，可以通過索引來訪問指定位置的集合元素。實現List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

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

（2）LinkedList
同樣實現List接口的LinkedList與ArrayList不同，ArrayList是一個動態數組，而LinkedList是一個雙向鏈表。所以它除了有ArrayList的基本操作方法外還額外提供了get，remove，insert方法在LinkedList的首部或尾部。
由于實現的方式不同，LinkedList不能隨機訪問，它所有的操作都是要按照雙重鏈表的需要執行。在列表中索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。這樣做的好處就是可以通過較低的代價在List中進行插入和刪除操作。
與ArrayList一樣，LinkedList也是非同步的。如果多個線程同時訪問一個List，則必須自己實現訪問同步。

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

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

2.Set接口
Set是一種不包括重復元素的Collection。它維持它自己的內部排序，所以隨機訪問沒有任何意義。與List一樣，它同樣允許null的存在但是僅有一個。由于Set接口的特殊性，所有傳入Set集合中的元素都必須不同，同時要注意任何可變對象，如果在對集合中元素進行操作時，導致e1.equals(e2)==true，則必定會產生某些問題。Set接口有三個具體實現類，分別是散列集HashSet、鏈式散列集LinkedHashSet和樹形集TreeSet。
Set是一種不包含重復的元素的Collection，無序，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素。需要注意的是:雖然Set中元素沒有順序，但是元素在set中的位置是由該元素的HashCode決定的，其具體位置其實是固定的。

（1）HashSet
HashSet 是一個沒有重復元素的集合。它是由HashMap實現的，不保證元素的順序(這里所說的沒有順序是指：元素插入的順序與輸出的順序不一致)，而且HashSet允許使用null 元素。HashSet是非同步的，如果多個線程同時訪問一個哈希set，而其中至少一個線程修改了該set，那么它必須保持外部同步。 HashSet按Hash算法來存儲集合的元素，因此具有很好的存取和查找性能。
HashSet的實現方式大致如下，通過一個HashMap存儲元素，元素是存放在HashMap的Key中，而Value統一使用一個Object對象。
HashSet使用和理解中容易出現的誤區:
a.HashSet中存放null值
HashSet中是允許存入null值的，但是在HashSet中僅僅能夠存入一個null值。
b.HashSet中存儲元素的位置是固定的
HashSet中存儲的元素的是無序的，這個沒什么好說的，但是由于HashSet底層是基于Hash算法實現的，使用了hashcode，所以HashSet中相應的元素的位置是固定的。
c.必須小心操作可變對象（Mutable Object）。如果一個Set中的可變元素改變了自身狀態導致Object.equals(Object)=true將導致一些問題。

（2）LinkedHashSet
LinkedHashSet繼承自HashSet，其底層是基于LinkedHashMap來實現的，有序，非同步。LinkedHashSet集合同樣是根據元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序。這樣使得元素看起來像是以插入順序保存的，也就是說，當遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。

（3）TreeSet
TreeSet是一個有序集合，其底層是基于TreeMap實現的，非線程安全。TreeSet可以確保集合元素處于排序狀態。TreeSet支持兩種排序方式，自然排序和定制排序，其中自然排序為默認的排序方式。當我們構造TreeSet時，若使用不帶參數的構造函數，則TreeSet的使用自然比較器；若用戶需要使用自定義的比較器，則需要使用帶比較器的參數。
注意：TreeSet集合不是通過hashcode和equals函數來比較元素的.它是通過compare或者comparaeTo函數來判斷元素是否相等.compare函數通過判斷兩個對象的id，相同的id判斷為重復元素，不會被加入到集合中。

四、Map接口
Map與List、Set接口不同，它是由一系列鍵值對組成的集合，提供了key到Value的映射。同時它也沒有繼承Collection。在Map中它保證了key與value之間的一一對應關系。也就是說一個key對應一個value，所以它不能存在相同的key值，當然value值可以相同。

1.HashMap
以哈希表數據結構實現，查找對象時通過哈希函數計算其位置，它是為快速查詢而設計的，其內部定義了一個hash表數組（Entry[] table），元素會通過哈希轉換函數將元素的哈希地址轉換成數組中存放的索引，如果有沖突，則使用散列鏈表的形式將所有相同哈希地址的元素串起來，可能通過查看HashMap.Entry的源碼它是一個單鏈表結構。

2.LinkedHashMap
LinkedHashMap是HashMap的一個子類，它保留插入的順序，如果需要輸出的順序和輸入時的相同，那么就選用LinkedHashMap。
LinkedHashMap是Map接口的哈希表和鏈接列表實現，具有可預知的迭代順序。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
LinkedHashMap實現與HashMap的不同之處在于，后者維護著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
根據鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問順序(調用get方法)的鏈表。默認是按插入順序排序，如果指定按訪問順序排序，那么調用get方法后，會將這次訪問的元素移至鏈表尾部，不斷訪問可以形成按訪問順序排序的鏈表。
注意，此實現不是同步的。如果多個線程同時訪問鏈接的哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。
由于LinkedHashMap需要維護元素的插入順序，因此性能略低于HashMap的性能，但在迭代訪問Map里的全部元素時將有很好的性能，因為它以鏈表來維護內部順序。

3.TreeMap
TreeMap 是一個有序的key-value集合，非同步，基于紅黑樹（Red-Black tree）實現，每一個key-value節點作為紅黑樹的一個節點。TreeMap存儲時會進行排序的，會根據key來對key-value鍵值對進行排序，其中排序方式也是分為兩種，一種是自然排序，一種是定制排序，具體取決于使用的構造方法。

自然排序：TreeMap中所有的key必須實現Comparable接口，并且所有的key都應該是同一個類的對象，否則會報ClassCastException異常。

定制排序：定義TreeMap時，創建一個comparator對象，該對象對所有的treeMap中所有的key值進行排序，采用定制排序的時候不需要TreeMap中所有的key必須實現Comparable接口。

TreeMap判斷兩個元素相等的標準：兩個key通過compareTo()方法返回0，則認為這兩個key相等。

如果使用自定義的類來作為TreeMap中的key值，且想讓TreeMap能夠良好的工作，則必須重寫自定義類中的equals()方法，TreeMap中判斷相等的標準是：兩個key通過equals()方法返回為true，并且通過compareTo()方法比較應該返回為0。