《吊打面試官》系列-HashMap
本文公眾號來源：三太子敖丙作者：三太子敖丙本文已收錄至我的GitHub
前言
作為一個在互聯(lián)網(wǎng)公司面一次拿一次Offer的面霸，打敗了無數(shù)競爭對手，每次都只能看到無數(shù)落寞的身影失望的離開，略感愧疚（請允許我使用一下夸張的修辭手法）。
于是在一個寂寞難耐的夜晚，我痛定思痛，決定開始寫互聯(lián)網(wǎng)技術棧面試相關的文章，希望能幫助各位讀者以后面試勢如破竹，對面試官進行360°的反擊，吊打問你的面試官，讓一同面試的同僚瞠目結舌，瘋狂收割大廠Offer！
所有文章的名字只是我的噱頭，我們應該有一顆謙遜的心，所以希望大家懷著空杯心態(tài)好好學，一起進步。
正文
一個婀娜多姿，穿著襯衣的小姐姐，拿著一個精致的小筆記本，徑直走過來坐在我的面前。
看著眼前這個美麗的女人，心想這不會就是Java基礎系列的面試官吧，真香。
不過看樣子這么年輕應該問不出什么深度的吧，嘻嘻。（哦？是么?）
小伙子，聽前面的面試官說了，你Redis和消息隊列都回答得不錯，看來還是有點東西。
美麗迷人的面試官您好，您見笑了，全靠看了敖丙的《吊打面試官》系列，不然我還真的回答不上很多原本的知識盲區(qū)，他真的有點東西。
面試官心想：哦，吊打面試官是么，那今天我就讓你知道，吊打這兩個字怎么寫的吧，年輕人啊，提前為你感到惋惜。
嗯嗯小帥比，雖然前面的技術棧沒啥太大的瑕疵，不過未來很長的一段時間我會用一期期的基礎教你做人的，你要準備好喲！
好了我們開始今天的面試吧，小伙子你了解數(shù)據(jù)結構中的HashMap么？能跟我聊聊他的結構和底層原理么？
切，這也太看不起我了吧，居然問這種低級問題，不過還是要好好回答。
嗯嗯面試官，我知道HashMap是我們非常常用的數(shù)據(jù)結構，由數(shù)組和鏈表組合構成的數(shù)據(jù)結構。
大概如下，數(shù)組里面每個地方都存了Key-Value這樣的實例，在Java7叫Entry在Java8中叫Node。
因為他本身所有的位置都為null，在put插入的時候會根據(jù)key的hash去計算一個index值。
就比如我put（”帥丙“，520），我插入了為”帥丙“的元素，這個時候我們會通過哈希函數(shù)計算出插入的位置，計算出來index是2那結果如下。
hash（“帥丙”）= 2
你提到了還有鏈表，為啥需要鏈表，鏈表又是怎么樣子的呢？
我們都知道數(shù)組長度是有限的，在有限的長度里面我們使用哈希，哈希本身就存在概率性，就是”帥丙“和”丙帥“我們都去hash有一定的概率會一樣，就像上面的情況我再次哈?！北麕洝皹O端情況也會hash到一個值上，那就形成了鏈表。
每一個節(jié)點都會保存自身的hash、key、value、以及下個節(jié)點，我看看Node的源碼。
說到鏈表我想問一下，你知道新的Entry節(jié)點在插入鏈表的時候，是怎么插入的么？
java8之前是頭插法，就是說新來的值會取代原有的值，原有的值就順推到鏈表中去，就像上面的例子一樣，因為寫這個代碼的作者認為后來的值被查找的可能性更大一點，提升查找的效率。
但是，在java8之后，都是所用尾部插入了。
為啥改為尾部插入呢？
這?。?！這個問題，面試官可真會問?。。∵€好我飽讀詩書，不然死定了！
有人認為是作者隨性而為，沒啥luan用，其實不然，其中暗藏玄機
首先我們看下HashMap的擴容機制：
帥丙提到過了，數(shù)組容量是有限的，數(shù)據(jù)多次插入的，到達一定的數(shù)量就會進行擴容，也就是resize。
什么時候resize呢？
有兩個因素：
Capacity：HashMap當前長度。
LoadFactor：負載因子，默認值0.75f。
怎么理解呢，就比如當前的容量大小為100，當你存進第76個的時候，判斷發(fā)現(xiàn)需要進行resize了，那就進行擴容，但是HashMap的擴容也不是簡單的擴大點容量這么簡單的。
擴容？它是怎么擴容的呢？
分為兩步
擴容：創(chuàng)建一個新的Entry空數(shù)組，長度是原數(shù)組的2倍。
ReHash：遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組。
為什么要重新Hash呢，直接復制過去不香么？
臥槽這個問題！有點知識盲區(qū)呀！
1x1得 1 ?1x2 得 2 ?…. 有了，我想起來敖丙那天晚上在我耳邊的話了：假如我年少有為不自卑，懂得什么是珍貴，那些美夢沒給你，我一生有愧….什么鬼！
小姐姐：是因為長度擴大以后，Hash的規(guī)則也隨之改變。
Hash的公式---> index = HashCode（Key） & （Length - 1）
原來長度（Length）是8你位運算出來的值是2 ，新的長度是16你位運算出來的值明顯不一樣了。
擴容前：
擴容后：
說完擴容機制我們言歸正傳，為啥之前用頭插法，java8之后改成尾插了呢？
臥槽，我以為她忘記了！居然還是被問到了！
我先舉個例子吧，我們現(xiàn)在往一個容量大小為2的put兩個值，負載因子是0.75是不是我們在put第二個的時候就會進行resize？
2*0.75 = 1 所以插入第二個就要resize了
現(xiàn)在我們要在容量為2的容器里面用不同線程插入A，B，C，假如我們在resize之前打個短點，那意味著數(shù)據(jù)都插入了但是還沒resize那擴容前可能是這樣的。
我們可以看到鏈表的指向A->B->C
Tip：A的下一個指針是指向B的
因為resize的賦值方式，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置，在舊數(shù)組中同一條Entry鏈上的元素，通過重新計算索引位置后，有可能被放到了新數(shù)組的不同位置上。
就可能出現(xiàn)下面的情況，大家發(fā)現(xiàn)問題沒有？
B的下一個指針指向了A
一旦幾個線程都調(diào)整完成，就可能出現(xiàn)環(huán)形鏈表
如果這個時候去取值，悲劇就出現(xiàn)了——Infinite Loop。
誒臥槽，小伙子難不倒他呀！
小伙子有點東西呀，但是你都都說了頭插是JDK1.7的那1.8的尾插是怎么樣的呢？
因為java8之后鏈表有紅黑樹的部分，大家可以看到代碼已經(jīng)多了很多if else的邏輯判斷了，紅黑樹的引入巧妙的將原本O(n)的時間復雜度降低到了O(logn)。
Tip：紅黑樹的知識點同樣很重要，還是那句話不打沒把握的仗，限于篇幅原因，我就不在這里過多描述了，以后寫到數(shù)據(jù)結構再說吧，不過要面試的仔，還是要準備好，反正我是經(jīng)常問到的。
使用頭插會改變鏈表的上的順序，但是如果使用尾插，在擴容時會保持鏈表元素原本的順序，就不會出現(xiàn)鏈表成環(huán)的問題了。
就是說原本是A->B，在擴容后那個鏈表還是A->B
Java7在多線程操作HashMap時可能引起死循環(huán)，原因是擴容轉(zhuǎn)移后前后鏈表順序倒置，在轉(zhuǎn)移過程中修改了原來鏈表中節(jié)點的引用關系。
Java8在同樣的前提下并不會引起死循環(huán)，原因是擴容轉(zhuǎn)移后前后鏈表順序不變，保持之前節(jié)點的引用關系。
那是不是意味著Java8就可以把HashMap用在多線程中呢？
我認為即使不會出現(xiàn)死循環(huán)，但是通過源碼看到put/get方法都沒有加同步鎖，多線程情況最容易出現(xiàn)的就是：無法保證上一秒put的值，下一秒get的時候還是原值，所以線程安全還是無法保證。
小伙子回答得很好嘛，這都被你回答道了，面試這么多人都不知道頭插和尾插，還是被你說出來了，可以可以。
面試官謬贊啊，要不是你這樣美若天仙的面試官面試我，我估計是想不起來了。
我*，你套近乎？
小姐姐抿嘴一笑，小子你offer有了，耶穌都帶不走你，我說的！
那我問你HashMap的默認初始化長度是多少？
我記得我在看源碼的時候初始化大小是16
你那知道為啥是16么？
臥*，這叫什么問題??？他為啥是16我怎么知道？？？你確定你沒逗我？
我努力回憶源碼，不知道有沒有漏掉什么細節(jié)，以前在學校熬夜看源碼的一幕幕在腦海里閃過，想起那個晚上在操場上，跟我好了半個月的小綠拉著我的手說：你就要當爸爸了。
等等，這都是什么鬼，哦哦哦，想起來了?。。?/p>
在JDK1.8的 236 行有1<<4就是16，為啥用位運算呢？直接寫16不好么？
我再次陷入沉思，瘋狂腦暴，叮！
有了！
面試官您好，我們在創(chuàng)建HashMap的時候，阿里巴巴規(guī)范插件會提醒我們最好賦初值，而且最好是2的冪。
這樣是為了位運算的方便，位與運算比算數(shù)計算的效率高了很多，之所以選擇16，是為了服務將Key映射到index的算法。
我前面說了所有的key我們都會拿到他的hash，但是我們怎么盡可能的得到一個均勻分布的hash呢？
是的我們通過Key的HashCode值去做位運算。
我打個比方，key為”帥丙“的十進制為766132那二進制就是 10111011000010110100
我們再看下index的計算公式：index = HashCode（Key） & （Length- 1）
15的的二進制是1111，那10111011000010110100 &1111 十進制就是4
之所以用位與運算效果與取模一樣，性能也提高了不少！
那為啥用16不用別的呢？
因為在使用不是2的冪的數(shù)字的時候，Length-1的值是所有二進制位全為1，這種情況下，index的結果等同于HashCode后幾位的值。
只要輸入的HashCode本身分布均勻，Hash算法的結果就是均勻的。
這是為了實現(xiàn)均勻分布。
喲小家伙，知道的確實很多，那我問你個問題，為啥我們重寫equals方法的時候需要重寫hashCode方法呢？
你能用HashMap給我舉個例子么？
這都能被他問到，還好我看了敖丙的系列呀，不然真的完了?。?！
但是我想拖延點時間，只能故做沉思，仰望天空片刻，45°仰望天空的樣子，說實話，我看到面試官都流口水了！可惜我是他永遠得不到的男人，好了不裝逼了。
我想起來了面試官！
因為在java中，所有的對象都是繼承于Object類。Ojbect類中有兩個方法equals、hashCode，這兩個方法都是用來比較兩個對象是否相等的。
在未重寫equals方法我們是繼承了object的equals方法，那里的 equals是比較兩個對象的內(nèi)存地址，顯然我們new了2個對象內(nèi)存地址肯定不一樣
對于值對象，==比較的是兩個對象的值
對于引用對象，比較的是兩個對象的地址
大家是否還記得我說的HashMap是通過key的hashCode去尋找index的，那index一樣就形成鏈表了，也就是說”帥丙“和”丙帥“的index都可能是2，在一個鏈表上的。
我們?nèi)et的時候，他就是根據(jù)key去hash然后計算出index，找到了2，那我怎么找到具體的”帥丙“還是”丙帥“呢？
equals！是的，所以如果我們對equals方法進行了重寫，建議一定要對hashCode方法重寫，以保證相同的對象返回相同的hash值，不同的對象返回不同的hash值。
不然一個鏈表的對象，你哪里知道你要找的是哪個，到時候發(fā)現(xiàn)hashCode都一樣，這不是完犢子嘛。
可以可以小伙子，我記得你上面說過他是線程不安全的，那你能跟我聊聊你們是怎么處理HashMap在線程安全的場景么？
面試官，在這樣的場景，我們一般都會使用HashTable或者CurrentHashMap，但是因為前者的并發(fā)度的原因基本上沒啥使用場景了，所以存在線程不安全的場景我們都使用的是CorruentHashMap。
HashTable我看過他的源碼，很簡單粗暴，直接在方法上鎖，并發(fā)度很低，最多同時允許一個線程訪問，currentHashMap就好很多了，1.7和1.8有較大的不同，不過并發(fā)度都比前者好太多了。
那你能跟我聊聊CurrentHashMap么？
好呀，不過今天天色已晚，我覺得我們要不改天再約？
再說最近敖丙好像雙十二比較忙，一次怎么能懟這么多呢？
好吧好吧，小伙子還挺會為別人著想，而且還喜歡這么優(yōu)秀的作者，你我覺得來日可期，那我們改日再約，今天表現(xiàn)很好，希望下次能保持住！
總結
HashMap絕對是最常問的集合之一，基本上所有點都要爛熟于心的那種，篇幅和時間的關系，我就不多介紹了，核心的點我基本上都講到了，不過像紅黑樹這樣的就沒怎么聊了，但是不代表不重要。
篇幅和精力的原因我就介紹到了一部分的主要知識點，我總結了一些關于HashMap常見的面試題，大家問下自己能不能回答上來，不能的話要去查清楚喲。
HashMap常見面試題：
HashMap的底層數(shù)據(jù)結構？
HashMap的存取原理？
Java7和Java8的區(qū)別？
為啥會線程不安全？
有什么線程安全的類代替么?
默認初始化大小是多少？為啥是這么多？為啥大小都是2的冪？
HashMap的擴容方式？負載因子是多少？為什是這么多？
HashMap的主要參數(shù)都有哪些？
HashMap是怎么處理hash碰撞的？
hash的計算規(guī)則？
推薦阿里云推廣服務器89/年，229/3年，買來送自己，送女朋友馬上過年再合適不過了，買了搭建個項目給面試官看也香，還可以熟悉技術棧，(老用戶用家人賬號買就好了，我用我女朋友的?）。掃碼購買
我這里還有購買后的教程：搭建教程，從0開始一步一步帶你搭建?
兩年嘔心瀝血的文章：「面試題」「基礎」「進階」這里全都有！