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