HashMap
1.描述
-
HashMap是常用的Java集合之一，是基于哈希表的Map介面的實作，設計目標是盡量實作哈希表O(1)級別的增刪改查效果，與HashTable主要區別為不支持同步和允許null作為key和value，
各項默認值
-
初始容量（capacity）：16（1<<4），即2^4，
-
最大容量：(1<<30)，即2^30，
-
默認擴容因子（loadFactor）：0.75，
-
自動擴容閾值：當前HashMap元素個數 > capacity * loadFactor，會自動擴容，并重新hash，
-
擴容機制：擴容至當前HashMap容量*2.0，且每次擴容后的容量必須為2的n次方，
-
容量必須為2的n次方的原因：
HashMap對元素進行讀、寫操作時，需要將Map元素的Key的哈希值對陣列長度（HashMap 的容量）進行取模運算，結果作為該元素在陣列中的索引（index），在計算機中，取模運算的代價遠高于位運算的代價，當陣列長度為 2^n 時，可以將Map元素的Key的hashcode對 (2^n)-1 進行 與運算(&)，效果與對陣列長度進行取模運算相等，所以為了提高 HashMap 的操作效率，規定 HashMap 的容量必須為2的n次方，即2^n，
-
2.底層實作 1.7與1.8及以后
2.1JDK1.8之前
? 采用 陣列+鏈表 實作，形成一個陣列帶著多個桶的結構，每個陣列元素就是一個桶，而陣列索引就是每個桶中鏈表的表頭，每一個Map元素的資料結構是一個 Entry，
-
- 陣列存盤區間連續，占用記憶體較多，尋址容易，插入和洗掉困難，
- 鏈表存盤區間離散，占用記憶體較少，尋址困難，插入和洗掉容易，
-
遺留問題
- 在某些極端情況下，會導致大量元素都存放在同一個桶(陣列索引是鏈表的表頭)的鏈表中，此時的HashMap 就相當于一個單鏈表，假設鏈表中的元素個數為n個，則其操作時間復雜度就變成了O(n)，完全失去了哈希表的優勢，
2.2JDK1.8及以后:
-
采用 陣列+鏈表+紅黑樹 實作，每個Map元素的資料結構是 Node(鏈表) 或 TreeNode(紅黑樹)，
-
解決遺留問題：
- jdk1.8時默認還是使用 陣列+鏈表 實作，只是元素的資料結構從 Entry 變為了 Node，當存盤在同一個桶中的元素過多時，才會將鏈表轉換為紅黑樹實作，保證其操作時間復雜度為 O(logn)，
-
鏈表與紅黑樹的轉換條件
-
- 鏈表->紅黑樹：整個 HashMap 中的元素個數 >= 64 且 同一個桶下的鏈表中的元素個數 > 8；此時Map元素的資料結構從 Node 轉為 TreeNode ;
-
- 紅黑樹->鏈表：同一個桶下的鏈表中的元素個數 < 6；此時元素的資料結構為 Node；
3.HashMap Q/A start
1.鏈表轉紅黑樹的閾值為什么是8？
-
因為紅黑樹的平均查找長度是log(n)，長度為8的時候，平均查找長度為3，如果繼續使用鏈表，平均查找長度為8/2=4，這才有轉換為樹的必要，鏈表長度如果是小于等于6，6/2=3，雖然速度也很快的，但是轉化為樹結構和生成樹的時間并不會太短，
-
還有選擇6和8，中間有個差值7可以有效防止鏈表和樹頻繁轉換，假設一下，如果設計成鏈表個數超過8則鏈表轉換成樹結構，鏈表個數小于8則樹結構轉換成鏈表，如果一個HashMap不停的插入、洗掉元素，鏈表個數在8左右徘徊，就會頻繁的發生樹轉鏈表、鏈表轉樹，效率會很低，
2.為什么是要轉為紅黑樹，二叉平衡樹不行嗎？
-
因為平衡二叉是高度平衡的樹, 當平衡被破壞時，需要要 rebalance（再平衡）, 開銷會比紅黑樹大.
-
原因：
-
插入引起的不平衡：
插入一個node引起了樹的不平衡，平衡二叉樹和紅黑樹都是最多只需要2次旋轉操作，即兩者都是O(1)；
-
洗掉引起的不平衡：
最壞情況下，平衡二叉樹需要維護從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉的量級是O(logN)此，而紅黑樹最多只需3次旋轉，只需要O(1)的復雜度，
-
3.是否執行緒安全？不安全的場景
- HashMap執行緒不安全，主要表現在：
? 多執行緒同時put時可能會丟失值（前面的put被后面的覆寫），
? 多執行緒擴容時會出現環狀結構，造成死回圈，(1.8之前)
? 多執行緒使用迭代器時會觸發fast-fail機制，
- 如何解決？
? 使用 Collections 的 synchronizedMap() 對其進行包裝，使其執行緒安全，（鎖整個表，效率差）
? 直接使用 執行緒安全的ConcurrentHashMap，(分段鎖/CAS，效率相對較高)
- 執行緒安全的map有哪些？
? hashtable,concurrentHashMap
4.說下hashmap put的程序
- key的hashcode高16位與低16位異或運算得到新的hash，為了讓資料（特別是在當前容量不大的情況下）散列更均勻，然后把異或計算出的新hash與此時的hashmap容量-1做&運算，得到插入下標，
5.為什么要做&運算，還有什么方式
- :二進制運算速度快，還可以取模，之后如果下標位陣列無資料則直接插入，如果有資料則鏈表往下逐個進行hash比較，如果產生hash碰撞再進行==或者equals比較key是否一樣，一樣則覆寫原資料，否則添加到鏈表后面，（jdk7是新元素插入至鏈表頭部）
6.rehash后的元素具體去向問題（1.7和1.8元素rehash后元素去向是不同的）
7.擴容機制jdk7及以后
當hashmap中資料量超過當前容量*擴容因子(默認0.75)則擴容為原來的2倍，問：當前插入的位置上沒有元素就不擴容（jdk7）
8.為什么是2次冪擴容
- 2進制運算快；
- hash與當前容量-1做&運算很快且很巧妙地獲得元素下標；
- 擴容后能巧妙地重新分配元素位置）說下擴容的rehash，擴容后的部分節點資料會重新定位，具體規則是hash&原容量，得到無非兩個結果:0和1，如果是0則該元素所在下標位置不動，如果是1則將該元素放置原位置擴容后的對應位置（假如原先容量為16，元素位置在陣列下標14的位置，則擴容后容量為32，該元素移動到陣列下標30的位置（即原索引+原容量位置），
為什么看hashmap原始碼，你覺得看了后對你有什么好處
- 比較喜歡探究（其實是近期面試才認真看的...），知道了計算機位運算速度會比其它數學運算快；學習了它的思想對我思考問題方式有提升（能吹多少盡量吹多少）擴容是一個費性能的事，如果知道集合中大致會存多少元素最好給它一個初始容量
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61836.html
標籤：Java