來自：juejin.im/post/5c1da988f265da6143130ccc
為了能夠在面試回答中優(yōu)雅而不失體面回答面試考點，該文章借鑒了不同平臺對知識點的描述。回答
HashMap 是一種存取高效但不保證有序的常用容器。它的數據結構為“數組+鏈表”，是解決哈希沖突的產物，也就是我們常說的鏈地址法。它實現了Map 接口采用K-V 鍵值對存儲數據，并實現了淺拷貝和序列化。HashMap 的默認初始大小為16，初始化大小必須為2的冪，最大大小為2的30次方。數組中存儲的鏈表節(jié)點Entry 類實現于Map.Entry 接口，它實現了對節(jié)點的通用操作。HashMap 的閾值默認為“容量*0.75f”，當存儲節(jié)點數量超過該值，則對map 進行擴容處理。HashMap 提供了4種構造方法，分別是默認構造方法；可以指定初始容量的構造方法；可以指定初始容量和閾值的構造方法以及基于一個Map 的構造方法。雖然是構造函數，但是真正的初始化都是在第一次添加操作里面實現的。在第一次添加操作中，HashMap 會先判斷存儲數組有沒有初始化，如果沒有先進行初始化操作，初始化過程中會取比用戶指定的容量大的最近的2 的冪次方數作為數組的初始容量，并更新擴容的閾值。接著添加操作講解。添加操作的執(zhí)行流程為:先判斷有沒有初始化
再判斷傳入的key 是否為空，為空保存在table[o] 位置
key 不為空就對key 進hash，hash 的結果再& 數組的長度就得到存儲的位置
如果存儲位置為空則創(chuàng)建節(jié)點，不為空就說明存在沖突
解決沖突HashMap 會先遍歷鏈表，如果有相同的value 就更新舊值，否則構建節(jié)點添加到鏈表頭
添加還要先判斷存儲的節(jié)點數量是否達到閾值，到達閾值要進行擴容
擴容擴2倍，是新建數組所以要先轉移節(jié)點，轉移時都重新計算存儲位置，可能保持不變可能為舊容量+位置。
擴容結束后新插入的元素也得再hash 一遍才能插入。
先判斷是否為空，為空就在table[0] 去找值
不為空也是先hash,&數組長度計算下標位置
再遍歷找相同的key 返回值
HashMap 的其他操作大同小異，再講講HashMap1.7 的問題還有1.7 和1.8 的差別。HashMap 是一個并發(fā)不安全的容器，在迭代操作是采用的是fast-fail 機制；在并發(fā)添加操作中會出現丟失更新的問題；因為采用頭插法在并發(fā)擴容時會產生環(huán)形鏈表的問題，導致CPU 到達100%，甚至宕機。Hash1.7 和1.8 最大的不同在于1.8 采用了“數組+鏈表+紅黑樹”的數據結構，在鏈表長度超過8 時，把鏈表轉化成紅黑樹來解決HashMap 因鏈表變長而查詢變慢的問題；其次在hash 取下標時將1.7 的9次擾動（5次按位與和4次位運算）改為2次（一次按位與和一次位運算）
1.7 的底層節(jié)點為Entry，1.8 為node ，但是本質一樣，都是Map.Entry 的實現
還有就是在存取數據時添加了關于樹結構的遍歷更新與添加操作，并采用了尾插法來避免環(huán)形鏈表的產生
但是并發(fā)丟失更新的問題依然存在。
回答順序：數據結構+繼承結構+基本字段+構造方法+添加操作+擴容操作+獲取操作+并發(fā)問題+與1.8的區(qū)別考點分析
HashMap 作為最基本的容器，它本身的設計與1.7 1.8的差異性導致HashMap 成為面試中最最高頻的考點。所以掌握HashMap 勢在必行，但是想要在各種寬泛的回答中脫穎而出，就必須對hashMap 前因后果了然于胸。考點一：為什么初始容量必須為2 的冪？為什么負載因子為0.75f？為什么要做那么多擾動處理？
2 的n次冪轉化為二進制為1后面n個0，在計算下標的時候是hash&(length - 1)，也就是&(n-1)個1:初始容量為4->100，length-1 -> 11。所有的二進制為都為1有什么好處？0/1 & 1 都為它本身
0/1 & 0 都為 0
可以看出&1保證了取值的平均。如果某一位為0 ，比如最后一位，那么它&出來下標就一定是個偶數，減少了HashMap 數組一半的取值，大大增加了沖突的可能。如果負載因子小，意味著閾值變小。比如容量為10 的HashMap，負載因子為0.5f，那么存儲5個就會擴容到20，出現哈希沖突的可能性變小，但是空間利用率不高。適用于有足夠內存并要求查詢效率的場景。相反如果閾值為1 ，那么容量為10，就必須存儲10個元素才進行擴容，出現沖突的概率變大，極端情況下可能會從O(1)退化到O(n)。適用于內存敏感但不要求要求查詢效率的場景（3）hash() 的意義在于使hash 結果不同hash 算法的好壞直接影響hash 結構的效率，壞的hash 算法極端情況下可能會使hash 結構的存取效率從O(1)退化到O(n)。1.8 之所以把9 次擾動降到2 次，是出于計算效率的考慮。考點二：& 字符雖然和 % 效果一樣，但是操作效率更高
考點三：為什么int，String 適合最為key？
int 和 String 的好處在于hash 出來的值不會改變。如果是一個對象，那么他們可能會因為內部引用的改變而hashCode 值的改變，會導致存儲重復的數據或找不到數據的情況。考點四：并發(fā)操作導致的添加丟失和環(huán)形鏈表的產生過程
知識點拓展
不僅僅是HashMap 的東西，根據你的回答，面試官會引出很多其他的問題，所以你在自己設計回答的過程中可以有意識引導面試官問出你熟悉的內容，安排的明明白白。拓展一：解決Hash 沖突的不同方案
鏈地址法
開發(fā)地址：線性探測法、平方探測法
完全散列：布谷鳥散列
拓展二：HashMap 是淺拷貝，說一說淺拷貝和深拷貝的區(qū)別
拓展三：說一說Collections.synchronizedMap()和HashTable 的區(qū)別
拓展四：說一說HashMap 如何實現有序(LinkHashMap 和TreeMap)以及他們的差別
拓展五：說一說ConcurrentHashMap 如何實現線程安全
結尾
這篇文章更多的是HashMap 面試怎么答，以及需要注意的知識點，希望對你有所幫助。推薦閱讀：
【65期】Spring的IOC是啥？有什么好處?
【64期】MySQL 服務占用cpu 100%，如何排查問題? （MySQL面試第七彈）
【63期】談談MySQL 索引，B+樹原理，以及建索引的幾大原則（MySQL面試第六彈）
5T技術資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內回復「2048」，即可免費獲取！！微信掃描二維碼，關注我的公眾號
朕已閱?
