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