Map 在面試中永遠(yuǎn)是一個(gè)繞不開(kāi)的點(diǎn)，本文將詳細(xì)講解Map的相關(guān)內(nèi)容。關(guān)注公眾號(hào)「Java面典」了解更多 Java 知識(shí)點(diǎn)。
Map
- Map 是一個(gè)鍵值對(duì)（key-value）映射接口；
- 映射中不能包含重復(fù)的鍵，每個(gè)鍵最多只能映射到一個(gè)值；
- Map 允許以鍵集（keySet()）、值集（valueSet()）或鍵-值映射關(guān)系集（entrySet()）的形式查看某個(gè)映射的內(nèi)容。
HashMap
特點(diǎn)
- 根據(jù) key 的 hashCode 存儲(chǔ)數(shù)據(jù)，大多數(shù)情況下（hash沖突時(shí)除外）可以直接定位到值；
- HashMap具有較快的隨機(jī)讀取速度，遍歷速度不可控；
- 一個(gè) HashMap 對(duì)象中最多只允許一條記錄的鍵為 null，允許多條記錄的值為 null；
- HashMap是非線程安全的。
實(shí)現(xiàn)
可以看出 HashMap 其實(shí)是一個(gè)數(shù)組 + 單向鏈表組成。
容量
- capacity：當(dāng)前數(shù)組容量（默認(rèn)16），始終保持 2^n，可以擴(kuò)容，擴(kuò)容后數(shù)組大小為當(dāng)前的 2 倍；
- loadFactor：負(fù)載因子，默認(rèn)為 0.75；
- threshold：擴(kuò)容閾值，等于 capacity * loadFactor。
Java8實(shí)現(xiàn)
從 Java8 開(kāi)始，Java 對(duì) HashMap 的實(shí)現(xiàn)有了一定的改變，開(kāi)始引入紅黑樹(shù)，所以其結(jié)構(gòu)變成了 數(shù)組 + 鏈表 + 紅黑樹(shù)組成。
原因：當(dāng)發(fā)生 hash 沖突時(shí)，在鏈表中查詢 Node 的時(shí)間復(fù)雜度為 O(n)，為了降低時(shí)間復(fù)雜度，引入紅黑樹(shù)，時(shí)間復(fù)雜度變?yōu)?O(logN)。
容量：除了Java7中的容量相關(guān)參數(shù)外，Java8為了引入紅黑樹(shù)，還引入了另外幾個(gè)容量相關(guān)的變量。
- static final int TREEIFY_THRESHOLD = 8：鏈表轉(zhuǎn)樹(shù)閾值。當(dāng)鏈表長(zhǎng)度 > 該值時(shí)，則將鏈表轉(zhuǎn)換成紅黑樹(shù)；
- static final int UNTREEIFY_THRESHOLD = 6：樹(shù)還原鏈表閾值。當(dāng)紅黑樹(shù)內(nèi)節(jié)點(diǎn)數(shù)量 < 6時(shí)，則將紅黑樹(shù)轉(zhuǎn)換成鏈表；
- static final int MIN_TREEIFY_CAPACITY = 64：最小樹(shù)化閾值。當(dāng)哈希表中的容量 > 該值時(shí)，才允許鏈表轉(zhuǎn)化為紅黑樹(shù)。否則將直接擴(kuò)容。為了避免進(jìn)行擴(kuò)容、樹(shù)形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD。
ConcurrentHashMap
特點(diǎn)
- ConcurrentHashMap 其實(shí)就是一個(gè)線程安全的HashMap；
- ConcurrentHashMap key 和 value 均不允許為 null。
網(wǎng)上關(guān)于key 和 value 不允許為 null 的解釋是這樣描述的：如果map.get(key)return null，則無(wú)法檢測(cè)到該鍵是否顯式映射到 null 該鍵。在非并行映射中，您可以通過(guò)進(jìn)行檢查 map.contains(key)，但在并行映射中，兩次調(diào)用之間的映射可能已更改。
實(shí)現(xiàn)
- ConcurreuntHashMap 實(shí)現(xiàn)和 HashMap 差不多的，但是為了支持并發(fā)操作，引入了 Segment，ConcurreuntHashMap 由一個(gè) Segment 數(shù)組組成；
- Segment 通過(guò)繼承 ReentrantLock 來(lái)進(jìn)行加鎖，Segment 數(shù)組就相當(dāng)于是 ConcurreuntHashMap 的分段鎖，每次操作只用鎖住對(duì)應(yīng)的 Segment 就行了；
- Segment 內(nèi)部由 HashMap 組成；
- concurrencyLevel：并行級(jí)別，默認(rèn)16。其實(shí)就是 ConcurreuntHashMap 由長(zhǎng)度為 16 的 Segment 組成，所以可以理解為 ConcurreuntHashMap 默認(rèn)同時(shí)可以支持最多 16 個(gè)線程并發(fā)寫(xiě)。Segment 數(shù)組可以在初始化的時(shí)候指定，初始化后不可擴(kuò)容。
Java8實(shí)現(xiàn)
和 HashMap 一樣， ConcurrentHashMap 在 Java8 中也引入了紅黑樹(shù)的機(jī)制。在這里就不再贅述了。
LinkedHashMap
LinkedHashMap 是 HashMap 的一個(gè)子類，它記錄了元素插入的順序，能夠保證在使用迭代器遍歷的時(shí)候，先插入的元素先獲取。也可在構(gòu)造時(shí)帶參數(shù)，按照訪問(wèn)次序排序。
WeakHashMap
特點(diǎn)
- WeakHashMap 鍵值都可以是null；
- WeakHashMap 的鍵是“弱鍵”。當(dāng)某個(gè)鍵不再正常使用時(shí)，會(huì)被從 WeakHashMap 中被自動(dòng)移除。
弱鍵原理
- 弱鍵通過(guò) WeakReference 和 ReferenceQueue 實(shí)現(xiàn)，
- WeakHashMap 的 key 是 WeakReference 類型的， ReferenceQueue是一個(gè)隊(duì)列，它會(huì)保存被GC回收的“弱鍵”；
- 當(dāng)某“弱鍵”不再被其它對(duì)象引用，并被GC回收時(shí)，這個(gè)“弱鍵”也同時(shí)會(huì)被添加到 ReferenceQueue(queue) 隊(duì)列中；
- 當(dāng)再次操作 WeakHashMap 時(shí)，會(huì)先同步 table 和 queue 。table 中保存了全部的鍵值對(duì)，而 queue 中保存被 GC 回收的鍵值對(duì)；同步它們，就是刪除 table 中被 GC 回收的鍵值對(duì)。
主要變量
- table：是一個(gè)Entry[]數(shù)組類型，用于存儲(chǔ)鍵值對(duì)；
- size： 表示 WeakHashMap 的大小；
- threshold ：閾值，用于判斷是否需要調(diào)整容量，threshold的值="容量*加載因子"；
- loadFactor： 加載因子；
- modCount：是用來(lái)實(shí)現(xiàn)fail-fast機(jī)制的
- queue：保存的是“已被GC清除”的“弱引用的鍵”。
TreeMap
- TreeMap 實(shí)現(xiàn) SortedMap 接口，能夠把它保存的記錄根據(jù)鍵排序；
- 默認(rèn)按照鍵值升序排序，也可指定排序的比較器；
- 在使用 TreeMap 時(shí)，key 必須實(shí)現(xiàn) Comparable 接口或者在構(gòu)造 TreeMap 傳入自定義的 Comparator，否則會(huì)在運(yùn)行時(shí)拋出 java.lang.ClassCastException 類型的異常。
Hashtable
- Hashtable 繼承自 Dictionary 接口，相當(dāng)于介于 HashMap 與 ConcurrentHashMap 之間的一種哈希表；
- 相較于 HashMap 而言，他是線程安全的，同時(shí)與 ConcurrentHashMap 一樣，key vlaue 均不能為null；
- 相較于 ConcurrentHashMap 而言，Hashtable 不支持多線程同時(shí)操作。
- 所以在在單線程環(huán)境一般使用 HashMap，而在多線程環(huán)境中，使用 ConcurrentHashMap 。
Java集合系列推薦
Java集合02——三分鐘了解你必須掌握的兩個(gè)Set
Java集合01——List 的幾個(gè)實(shí)現(xiàn)類，了解一下？
