2016.7.29

ArrayList

ArrayList底層是數(shù)組實現(xiàn)，查詢上是線性的，有索引可循，而LinkedList是鏈表，每一個元素是一個節(jié)點(diǎn)，迭代下一個元素是尋址，查詢比ArrayList慢，數(shù)據(jù)更新也要先查詢到位置所有也是ArrayList較優(yōu)
末尾（附近）添加元素比LinkedList快很多（1E6次循環(huán)時18:901）
數(shù)據(jù)查詢和數(shù)據(jù)更新較優(yōu)

LinkedList

LinkedList底層是鏈表，插入和刪除數(shù)據(jù)只需要改變鏈接的指向就行，而ArrayList則需將新數(shù)據(jù)或被刪數(shù)據(jù)后的所有數(shù)據(jù)全部后移或前移
在開頭添加元素比ArrayList快很多（1E5次循環(huán)時6:4484）
在元素中存放下一個元素的位置指向，尋址較慢
在開頭（附近）和末尾插入元素很快，開頭是因為改變鏈接的指向就行，遍歷的次數(shù)也少，末尾是因為有一個last專門存放末尾元素，直接末尾的鏈接指向新元素，在將新元素設(shè)為last即可。
數(shù)據(jù)插入數(shù)據(jù)刪除較優(yōu)

HashSet

HasSet根據(jù)對象的hashCode值來決定該對象在HashSet中存儲位置。
哈希表是通過使用稱為散列法的機(jī)制來存儲數(shù)據(jù)的，元素并沒有以某種特定順序來存放。
對于 HashSet 而言，它是基于 HashMap 實現(xiàn)的，HashSet 底層采用 HashMap 來保存所有元素，因此 HashSet 的實現(xiàn)比較簡單，它只是封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態(tài)的 Object 對象。
HashSet 的絕大部分方法都是通過調(diào)用 HashMap 的方法來實現(xiàn)的，因此 HashSet 和 HashMap 兩個集合在實現(xiàn)本質(zhì)上是相同的。

HashSet有5個構(gòu)造函數(shù)，4個調(diào)用了HashMap的構(gòu)造函數(shù)，1個調(diào)用了LinkedHashMap構(gòu)造函數(shù)。

LinkedHashSet

LinkedHashSet繼承HashSet
LinkedHashSet同樣根據(jù)對象的hashCode值來決定該對象在HashSet中存儲位置，但它同時使用鏈表維護(hù)元素的次序。
這樣使得元素看起 來像是以插入順序保存的，也就是說，當(dāng)遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。
LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。

有4個構(gòu)造函數(shù)，全部調(diào)用了HashSet那個使用了LinkedHashMap的構(gòu)造函數(shù)

TreeSet

提供一個使用樹結(jié)構(gòu)存儲Set接口的實現(xiàn)，對象以升序順序存儲，訪問和遍歷的時間很快。
TreeSet是SortedSet接口的唯一實現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)。
TreeSet支持兩種排序方式，自然排序 和定制排序，其中自然排序為默認(rèn)的排序方式。
向TreeSet中加入的應(yīng)該是同一個類的對象。
TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0。

自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法來比較元素之間大小關(guān)系，然后將元素按照升序排列。
Java提供了一個Comparable接口，該接口里定義了一個compareTo(Object obj)方法，該方法返回一個整數(shù)值，實現(xiàn)了該接口的對象就可以比較大小。
obj1.compareTo(obj2)方法如果返回0，則說明被比較的兩個對象相等，如果返回一個正數(shù)，則表明obj1大于obj2，如果是 負(fù)數(shù)，則表明obj1小于obj2。
如果我們將兩個對象的equals方法總是返回true，則這兩個對象的compareTo方法返回應(yīng)該返回0。

定制排序
自然排序是根據(jù)集合元素的大小，以升序排列，如果要定制排序，應(yīng)該使用Comparator接口，實現(xiàn) int compare(T o1,T o2)方法。

HashMap

插入時平均。
HashMap提供了三個構(gòu)造函數(shù)：
HashMap()：構(gòu)造一個具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap。

在這里提到了兩個參數(shù)：初始容量，加載因子。這兩個參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)初始容量為16，負(fù)載因子為0.75，一般情況下我們是無需修改的。

當(dāng)插入數(shù)據(jù)超過（初始容量*加載因子）時，會自動調(diào)用resize()擴(kuò)容，將容量擴(kuò)大一倍。
若你一開始就知道了大概的數(shù)據(jù)量，建議直接定義初始容量為你所知道的數(shù)據(jù)量。不然插入數(shù)據(jù)一旦達(dá)到限度，自動擴(kuò)容又要申請新的存儲空間，還要把之前的數(shù)據(jù)全部copy一遍，浪費(fèi)時間也浪費(fèi)空間。

LinkedHashMap

遍歷是平均最快，插入鍵值對量巨大時平均速度最快。
繼承HashMap，也是使用鏈表維護(hù)元素的次序。
是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構(gòu)造時用帶參數(shù)，按照應(yīng)用次數(shù)排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當(dāng)HashMap容量很大，實際數(shù)據(jù)較少時，遍歷起來可能會比 LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關(guān)，和容量無關(guān)，而HashMap的遍歷速度和他的容量有關(guān)。

TreeMap

插入鍵值對量巨大時平均速度最慢，因為排序要花很長的時間。
TreeMap基于紅黑樹（Red-Black tree）實現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時提供的 Comparator 進(jìn)行排序，具體取決于使用的構(gòu)造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的時間復(fù)雜度是 log(n) 。