本文首發於我的個人博客： "尾尾部落" 1. Iterator介面 Iterator介面，這是一個用於遍歷集合中元素的介面，主要包含hashNext(),next(),remove()三種方法。它的一個子介面LinkedIterator在它的基礎上又添加了三種方法，分別是add(),previous ...
本文首發於我的個人博客：尾尾部落
1. Iterator介面
Iterator介面，這是一個用於遍歷集合中元素的介面，主要包含hashNext(),next(),remove()三種方法。它的一個子介面LinkedIterator在它的基礎上又添加了三種方法，分別是add(),previous(),hasPrevious()。也就是說如果是先Iterator介面，那麼在遍歷集合中元素的時候，只能往後遍歷，被遍歷後的元素不會在遍歷到，通常無序集合實現的都是這個介面，比如HashSet，HashMap；而那些元素有序的集合，實現的一般都是LinkedIterator介面，實現這個介面的集合可以雙向遍歷，既可以通過next()訪問下一個元素，又可以通過previous()訪問前一個元素，比如ArrayList。
2. List
List是元素有序並且可以重覆的集合。
List的主要實現：ArrayList, LinkedList, Vector。
2. ArrayList、LinkedList、Vector 的區別
| ArrayList | LinkedList | Vector | |
|---|---|---|---|
| 底層實現 | 數組 | 雙向迴圈鏈表 | 數組 |
| 同步性及效率 | 不同步，非線程安全，效率高 | 不同步，非線程安全，效率高 | 同步，線程安全，效率低 |
| 特點 | 查詢快,增刪慢 | 查詢慢,增刪快 | 查詢快,增刪慢 |
| 預設容量 | 10 | / | 10 |
| 擴容機制 | int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5 倍 | / | 2 倍 |
總結：
- ArrayList 和 Vector 基於數組實現，對於隨機訪問get和set，ArrayList優於LinkedList，因為LinkedList要移動指針。
- LinkedList 不會出現擴容的問題，所以比較適合隨機位置增、刪。但是其基於鏈表實現，所以在定位時需要線性掃描，效率比較低。
- 當操作是在一列數據的後面添加數據而不是在前面或中間,並且需要隨機地訪問其中的元素時,使用ArrayList會提供比較好的性能；
- 當你的操作是在一列數據的前面或中間添加或刪除數據,並且按照順序訪問其中的元素時,就應該使用LinkedList了。
3. Set
Set集合中的對象不按特定的方式排序(存入和取出的順序不一定一致)，並且沒有重覆對象。
Set的主要實現類：HashSet, TreeSet。
| HashSet | TreeSet | LinkedHashSet | |
|---|---|---|---|
| 底層實現 | HashMap | 紅黑樹 | LinkedHashMap |
| 重覆性 | 不允許重覆 | 不允許重覆 | 不允許重覆 |
| 有/無序 | 無序 | 有序，支持兩種排序方式，自然排序和定製排序，其中自然排序為預設的排序方式。 | 有序，以元素插入的順序來維護集合的鏈接表 |
| 時間複雜度 | add()，remove()，contains()方法的時間複雜度是O(1) | add()，remove()，contains()方法的時間複雜度是O(logn) | LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色於HashSet，時間複雜度是 O(1)。 |
| 同步性 | 不同步，線程不安全 | 不同步，線程不安全 | 不同步，線程不安全 |
| null值 | 允許null值 | 不支持null值，會拋出 java.lang.NullPointerException 異常。因為TreeSet應用 compareTo() 方法於各個元素來比較他們，當比較null值時會拋出 NullPointerException異常。 | 允許null值 |
| 比較 | equals() | compareTo() | equals() |
HashSet如何檢查重覆
當你把對象加入HashSet時，HashSet會先計算對象的hashcode值來判斷對象加入的位置，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode，HashSet會假設對象沒有重覆出現。但是如果發現有相同hashcode值的對象，這時會調用equals（）方法來檢查hashcode相等的對象是否真的相同。如果兩者相同，HashSet就不會讓加入操作成功。
hashCode（）與equals（）的相關規定：
- 如果兩個對象相等，則hashcode一定也是相同的
- 兩個對象相等,對兩個equals方法返回true
- 兩個對象有相同的hashcode值，它們也不一定是相等的
- 綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋
hashCode()的預設行為是對堆上的對象產生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數據）。
總結：
HashSet是一個通用功能的Set，而LinkedHashSet 提供元素插入順序保證，TreeSet是一個SortedSet實現，由Comparator 或者 Comparable指定的元素順序存儲元素。
4. Map
Map 是一種把鍵對象和值對象映射的集合，它的每一個元素都包含一對鍵對象和值對象。 Map沒有繼承於Collection介面從Map集合中檢索元素時，只要給出鍵對象，就會返回對應的值對象。
Map 的常用實現類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap
| HashMap | HashTable | ||
|---|---|---|---|
| 底層實現 | 數組+鏈表 | 數組+鏈表 | |
| 同步性 | 線程不同步 | 同步 | |
| null值 | 允許 key 和 Vale 是 null，但是只允許一個 key 為 null,且這個元素存放在哈希表 0 角標位置 | 不允許key、value 是 null | |
| hash | 使用hash(Object key)擾動函數對 key 的 hashCode 進行擾動後作為 hash 值 | 直接使用 key 的 hashCode() 返回值作為 hash 值 | |
| 容量 | 容量為 2^4 且容量一定是 2^n | 預設容量是11,不一定是 2^n | |
| 擴容 | 兩倍，且哈希桶的下標使用 &運算代替了取模 | 2倍+1，取哈希桶下標是直接用模運算 |
幾個問題：
1. HashMap 的工作原理？
通過hash的方法，通過put和get存儲和獲取對象。存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的占用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，併進一步調用equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞衝突的元素組織起來，在Java 8中，如果一個bucket中碰撞衝突的元素超過某個限制(預設是8)，則使用紅黑樹來替換鏈表，從而提高效率。
2.get和put的原理嗎？equals()和hashCode()的都有什麼作用？
通過對key的hashCode()進行hashing，並計算下標( n-1 & hash)，從而獲得buckets的位置。如果產生碰撞，則利用key.equals()方法去鏈表或樹中去查找對應的節點
3. HashMap 的長度為什麼是2的冪次方？
為了能讓 HashMap 存取高效，儘量較少碰撞，也就是要儘量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的演算法。
HashMap 和 LinkedHashMap 的區別
- LinkedHashMap 擁有與 HashMap 相同的底層哈希表結構，即數組 + 單鏈表 + 紅黑樹，也擁有相同的擴容機制。
- LinkedHashMap 相比 HashMap 的拉鏈式存儲結構，內部額外通過 Entry 維護了一個雙向鏈表。
- HashMap 元素的遍歷順序不一定與元素的插入順序相同，而 LinkedHashMap 則通過遍歷雙向鏈表來獲取元素，所以遍歷順序在一定條件下等於插入順序。
- LinkedHashMap 可以通過構造參數 accessOrder 來指定雙向鏈表是否在元素被訪問後改變其在雙向鏈表中的位置。
HashMap & TreeMap 的區別
HashMap實現了Map介面，不保障元素順序。
TreeMap實現了SortedMap介面，是一個有序的Map。內部採用紅黑樹實現，紅黑樹是一種維護有序數據的高效數據結構
ConcurrentHashMap 和 Hashtable 的區別
ConcurrentHashMap 和 Hashtable 的區別主要體現在實現線程安全的方式上不同。
底層數據結構： JDK1.7的 ConcurrentHashMap 底層採用 分段的數組+鏈表 實現，JDK1.8 採用的數據結構跟HashMap1.8的結構一樣，數組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數據結構類似都是採用 數組+鏈表 的形式，數組是 HashMap 的主體，鏈表則是主要為瞭解決哈希衝突而存在的；
實現線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） 對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高併發訪問率。（預設分配16個Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，併發控制使用 synchronized 和 CAS 來操作。（JDK1.6以後 對 synchronized鎖做了很多優化） 整個看起來就像是優化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了相容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。
JDK1.7的ConcurrentHashMap：
JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹節點 Node: 鏈表節點）：
參考
獲取最新資訊，請關註微信公眾號：南強說晚安
