何為HashMap环础？
HashMap是用哈希表（直接一點(diǎn)可以說數(shù)組加單鏈表）+ 紅黑樹實(shí)現(xiàn)的map類（其實(shí)所謂Map其實(shí)就是保存了兩個(gè)對(duì)象之間的映射關(guān)系的一種集合）。
版本之更迭
–》JDK 1.7?： Table數(shù)組 (也有叫做 "位桶" )?+ Entry鏈表（頭插法）弱睦；
–》JDK 1.8?：?Table數(shù)組 (也有叫做 "位桶" )?+ Node鏈表（換了名） + 紅黑樹（尾插法）；
HashMap的實(shí)現(xiàn)原理
當(dāng)系統(tǒng)開始初始化 HashMap 時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長度為 capacity（默認(rèn)為2的16次冪） 的 Entry 數(shù)組温赔。
這個(gè)數(shù)組被用來存儲(chǔ)key-value對(duì)，每?個(gè)鍵值對(duì)組成了?個(gè)Entry實(shí)體鬼癣，存儲(chǔ)元素（也就是一個(gè) Entry實(shí)體）的位置被稱為 "桶 (bucket) "陶贼，每個(gè) bucket 都有其指定索引，系統(tǒng)可以根據(jù)其索引快速訪問該 bucket 里存儲(chǔ)的元素待秃。
無論何時(shí)拜秧，HashMap 的每個(gè) "桶" 只存儲(chǔ)一個(gè)元素，由于 Entry 對(duì)象可以包含一個(gè)引用變量（就是 Entry 構(gòu)造器的的最后一個(gè)參數(shù)Next指針）用于指向下一個(gè) Entry章郁，因此可能出現(xiàn)的情況是：HashMap 的 bucket 中只有一個(gè) Entry枉氮，但這個(gè) Entry 指向另一個(gè) Entry ——這就形成了一個(gè) Entry 鏈（單向的鏈表結(jié)構(gòu)）。
參數(shù)說明
HashMap的初始化
HashMap有4個(gè)構(gòu)造器暖庄，其他構(gòu)造器如果用戶沒有傳入initialCapacity 和loadFactor這兩個(gè)參數(shù)嘲恍，會(huì)使用默認(rèn)值
從上面這段代碼我們可以看出，在常規(guī)構(gòu)造器中雄驹，沒有為數(shù)組table分配內(nèi)存空間（有一個(gè)入?yún)橹付∕ap的構(gòu)造器例外）佃牛，只是賦值，只有在執(zhí)行put操作的時(shí)候才真正構(gòu)建table數(shù)組医舆，為什么要這樣做俘侠？估計(jì)是避免初始化了HashMap之后不使用反而占用內(nèi)存吧
OK,接下來我們來看看put操作的實(shí)現(xiàn)
HashMap的存儲(chǔ)操作
inflateTable這個(gè)方法用于為主干數(shù)組table在內(nèi)存中分配存儲(chǔ)空間，通過roundUpToPowerOf2(toSize)可以確保capacity為大于或等于toSize的最接近toSize的二的次方數(shù)蔬将，比如toSize = 13,則capacity = 16; toSize = 16,capacity = 16; toSize =17,capacity = 32.
roundUpToPowerOf2中的這段處理使得數(shù)組長度一定為2的次冪爷速，Integer.highestOneBit是用來獲取一個(gè)小于等于i的2的冪次方數(shù)
number減1是為了所獲取的結(jié)果不超過原數(shù)
返回一個(gè)小于等于i的2的冪次方數(shù)
按位從左向右移動(dòng)，取i的最高位霞怀，其他位清0（右移與或運(yùn)算的目的就是想讓某個(gè)數(shù)字的低位都變?yōu)?惫东，再用該結(jié)果減去該結(jié)果右移一位后的結(jié)果，則相當(dāng)于清除了原數(shù)字的低位毙石，即得到了我們想要的結(jié)果）
hash函數(shù)
以上hash函數(shù)計(jì)算出的值廉沮，通過indexFor進(jìn)一步處理來獲取實(shí)際的存儲(chǔ)位置
h&（length-1）保證獲取的index一定在數(shù)組范圍內(nèi)，舉個(gè)例子徐矩，默認(rèn)容量16滞时，length-1=15，h=18,轉(zhuǎn)換成二進(jìn)制計(jì)算為index=2滤灯。位運(yùn)算對(duì)計(jì)算機(jī)來說坪稽，性能更高一些（HashMap中有大量位運(yùn)算曼玩，計(jì)算機(jī)底層就是2進(jìn)制運(yùn)算）。數(shù)組下標(biāo)的獲取無視了HashCode高位的參與窒百，所以有了以上Hash函數(shù)代碼中對(duì)HashCode進(jìn)行進(jìn)一步的運(yùn)算和調(diào)整黍判，避免太多低位相同的HashCode存儲(chǔ)在同一位置上，鏈表過長篙梢，遍歷時(shí)間太久
再來看看addEntry的實(shí)現(xiàn)：
通過以上代碼能夠得知样悟，當(dāng)size大于閾值并且即將要發(fā)生哈希沖突（?jdk7中resize，只有當(dāng) size>=threshold并且 table中的那個(gè)槽中已經(jīng)有Entry時(shí)庭猩，才會(huì)發(fā)生resize。）的時(shí)候陈症，需要進(jìn)行數(shù)組擴(kuò)容蔼水，擴(kuò)容時(shí)，需要新建一個(gè)長度為之前數(shù)組2倍的新的數(shù)組录肯，然后將當(dāng)前的Entry數(shù)組中的元素全部傳輸過去趴腋，擴(kuò)容后的新數(shù)組長度為之前的2倍，所以擴(kuò)容相對(duì)來說是個(gè)耗資源的操作论咏。
