通過(guò)幾個(gè)問(wèn)題來(lái)學(xué)習(xí)HashMap
前提大家都知道，HashMap是由哈希表實(shí)現(xiàn)的，哈希表就是由數(shù)組和鏈表組成的。
給出一個(gè)很形象的數(shù)據(jù)結(jié)構(gòu)圖。
問(wèn)題1.既然HashMap是數(shù)組+鏈表實(shí)現(xiàn)的，數(shù)組開始的時(shí)候一定是有一個(gè)固定長(zhǎng)度的，那HashMap中的數(shù)組默認(rèn)長(zhǎng)度是多少呢？
默認(rèn)情況下，內(nèi)部數(shù)組的長(zhǎng)度就是16，這個(gè)可以從HashMap的底層源碼的構(gòu)造函數(shù)中看到。下面我們就開始HashMap的源碼閱讀之旅。
HashMap的構(gòu)造函數(shù)有三個(gè)。默認(rèn)我們都是不會(huì)傳這個(gè)initialCapacity的，如果不傳的話，那么就會(huì)使用默認(rèn)為4的DEFAULT_INITIAL_CAPACITY
然后將initialCapacity的值賦給了threshold，我們會(huì)在put方法中判斷，如果是第一次put數(shù)據(jù)就會(huì)初始化Table，也就使用到了這個(gè)threshold。
那么是怎么初始化的呢？就是拿到這個(gè)threshold對(duì)其做一下平方。（roundUpToPowerOf2就是對(duì)2的冪次冪）
一步步追蹤源代碼，發(fā)現(xiàn)最后是返回的默認(rèn)的4的平方的數(shù)組長(zhǎng)度。
問(wèn)題2.HashMap既然底層是一個(gè)線性的數(shù)組，那么是怎么實(shí)現(xiàn)的隨機(jī)存取呢？
（因?yàn)槭请S機(jī)存取，所以是有些索引位置是沒有元素的，會(huì)產(chǎn)生一些空間的浪費(fèi)，但是這其實(shí)就是空間換時(shí)間，讓HashMap既有數(shù)組的查詢快，又有鏈表的增刪快的優(yōu)點(diǎn)）
// 存儲(chǔ)時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
Entry[index] = value;
// 取值時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];
存儲(chǔ)的時(shí)候就是拿到key的hash值然后對(duì)HashMap底層數(shù)組的長(zhǎng)度取余，取余的結(jié)果就是存儲(chǔ)的索引。
取值的時(shí)候一樣是拿到key的hash值然后對(duì)HashMap底層數(shù)組的長(zhǎng)度取余，得到索引直接去數(shù)組里面取就行了。取出來(lái)是一個(gè)鏈表的封裝類Entry,然后遍歷一下Entry中的值取出我們要的就行了。
總結(jié)：元素存儲(chǔ)的規(guī)則 hash(key)%len, 就是key的hash值對(duì)HashMap底層數(shù)組的長(zhǎng)度取余，這個(gè)公式一定要記住。
問(wèn)題3.通過(guò)上面的問(wèn)題我們了解了HashMap的存取，但是我們要知道Hash算法其實(shí)就是把任意長(zhǎng)度的輸入變換成固定長(zhǎng)度的輸出，這種轉(zhuǎn)換是一種壓縮映射，也就是說(shuō)，Hash值的空間遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)Hash成相同的輸出。而且我們又對(duì)HashMap默認(rèn)size 16的數(shù)組長(zhǎng)度取余，所以不同的key就更是有很大概率返回相同的索引了，那會(huì)不會(huì)就把之前存的數(shù)據(jù)給覆蓋了呢？
答案當(dāng)然是否定的。不然誰(shuí)還敢用HashMap存數(shù)據(jù)呢。
HashMap我們知道是數(shù)組+鏈表實(shí)現(xiàn)的，前面我們是只看到了數(shù)組，鏈表呢就是在這使用的。這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個(gè)概念。上面我們提到過(guò)Entry類里面有一個(gè)next屬性，作用是指向下一個(gè)Entry。打個(gè)比方， 第一個(gè)鍵值對(duì)A進(jìn)來(lái)，通過(guò)計(jì)算其key的hash得到的index=0，記做:Entry[0] = A。一會(huì)后又進(jìn)來(lái)一個(gè)鍵值對(duì)B，通過(guò)計(jì)算其index也等于0，現(xiàn)在怎么辦？HashMap會(huì)這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來(lái)C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個(gè)鍵值對(duì),他們通過(guò)next這個(gè)屬性鏈接在一起。也就是說(shuō)數(shù)組中存儲(chǔ)的是最后插入的元素。（數(shù)組中只會(huì)存一個(gè)Entry元素,這一個(gè)元素的next就會(huì)指向下一個(gè)元素，這樣循環(huán)）
問(wèn)題4.我們前面看到數(shù)組的默認(rèn)長(zhǎng)度是16，可以說(shuō)很小，那他會(huì)不會(huì)擴(kuò)容呢？
答案是肯定的。默認(rèn)HashMap內(nèi)部數(shù)組的長(zhǎng)度為16，負(fù)載因子為0.75，就是在構(gòu)造函數(shù)里面?zhèn)鞯膬蓚€(gè)值。閾值就是12（16*0.75=12），這樣當(dāng)?shù)谑齻€(gè)元素加入時(shí)，底層數(shù)組就會(huì)擴(kuò)容。擴(kuò)容為原數(shù)組大小的兩倍。
resize（2*table.length）就是擴(kuò)容的操作。擴(kuò)容為原數(shù)組的兩倍。
