作為一個職場搬了幾年磚的碼農，不管是面試別人還是被別人面試，hashmap在面試出現的幾率可以說高達90%以上！
面試官們，如此反覆的提及hashmap，它在軟件開發中的重要性可見一斑。
那麼，hashmap到底是個什麼鬼？
hashmap在不同的jdk版本其實現方式也是不大一樣的。
JDK1.7：基於數組（散列桶）+鏈表來實現。
transient Entry[] table=(Entry [])EMPTY_TABLE;static class Entry implements Map.Entry { final K key; V value; Entry next; int hash;...}
使用一個Entry數組來存儲數據，用key的hashcode取模來決定key會被放到數組裡的位置，如果hashcode相同，或者hashcode取模後的結果相同（hash collision），那麼這些key會被定位到Entry數組的同一個格子裡，這些key會形成一個鏈表。
在hashcode特別差的情況下，比如所有key的hashcode都相同，這個鏈表可能會很長，那麼put/get操作都可能需要遍歷這個鏈表。
換句話說時間複雜度在最差情況下會退化到O(n)。
JDK1.8：基於數組（散列桶）+鏈表/紅黑樹來實現。
transient Node[] table;static class Node implements Map.Entry { final int hash; final K key; V value; Node next; ... }
使用一個Node數組來存儲數據，但這個Node可能是鏈表結構，也可能是紅黑樹結構。
如果插入的key的hashcode相同，那麼這些key也會被定位到Node數組的同一個格子裡。
如果同一個格子裡的key不超過8個，使用鏈表結構存儲。
如果超過了8個，那麼會調用treeifyBin函數，將鏈表轉換為紅黑樹。
那麼即使hashcode完全相同，由於紅黑樹的特點，查找某個特定元素，也只需要O(log n)的開銷。
也就是說put/get的操作的時間複雜度最差只有O(log n)。
相同點
1. 默認初始容量都是16，默認負載因子都是0.75。數組的長度length都是2的次冪，擴容時都是2倍
2. 通過hash計算索引的方法相同（hash & length-1）
3. key為null的鍵值對都會放入table[0]中
4. 都是懶加載，初始時表為空，在插入第一個鍵值對時初始化
不同點
1. 結構不同，JDK1.8增加了紅黑樹優化結構
2. put方法的區別，JDK1.7中put時，添加到頭節點；JDK1.8中添加到尾節點
3. 計算hash的方法不同，JDK1.8更優化
4. JDK1.7新鏈表的順序倒置，JDK1.8新鏈表順序不倒置
jdk1.8 put操作：
①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；
②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；
③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這裡的相同指的是hashCode以及equals；
④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；
⑤.遍歷table[i]，判斷鏈表長度是否大於8，大於8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可；
⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。
篇幅有限，感興趣的童鞋可以看看hashmap源碼是如何處理這些關鍵點：根據key獲取哈希桶數組索引位置、put方法的詳細執行、擴容機制。
下面分享一個面試常問的問題：HashMap是線程安全的麼？如果不是，那如果既想用HashMap又想讓它線程安全應該怎麼做？
可以有如下幾種方式來回答：
替換成Hashtable，Hashtable通過對整個表上鎖實現線程安全，但是效率比較低
使用Collections類的synchronizedMap方法包裝一下。方法如下：
public static
Map synchronizedMap(Map m) 返回由指定映射支持的同步（線程安全的）映射
使用ConcurrentHashMap，它使用分段鎖來保證線程安全
前兩種方式獲得的線程安全的HashMap在讀寫數據的時候會對整個容器上鎖
ConcurrentHashMap是不需要對整個容器上鎖的，它只需鎖住要修改的部分
![hashmap：面試必問知識點，你瞭解多少？]()
閱讀更多 碼農的搬磚生涯 的文章
