hashMap 數(shù)據(jù)結(jié)構(gòu)：
jdk1.7 數(shù)組+鏈表
jdk1.8 數(shù)組+鏈表+紅黑樹(shù)
hashMap 原理：
1.7 說(shuō)明：
HashMap map = new HashMap();
實(shí)例化以后岩臣，底層創(chuàng)建了長(zhǎng)度 為16，類型為Entry的數(shù)組 table.
map.put(key1,value1);
首先架谎，調(diào)用key1所在類的hashCode()計(jì)算key1哈希值炸宵，哈希值經(jīng)過(guò)算法計(jì)算，得到上面Entry數(shù)組中的存放位置谷扣，
情況一:
如果此位置上的數(shù)據(jù)為空土全，插入key1，value1抑钟，添加成功涯曲。
情況二:
如果此位置不為空（意味此位置存在一個(gè)或多個(gè)數(shù)據(jù)(以鏈表形勢(shì)存在)）比較key1和已經(jīng)存在一個(gè)或多個(gè)數(shù)據(jù)的哈希值。如果key1的哈希值和已經(jīng)存在數(shù)據(jù)的哈希值都不相同在塔，插入key1幻件，value1，添加成功蛔溃。
情況三:
如果key1的哈希值和已經(jīng)存在的某一個(gè)數(shù)據(jù)(key2-value2)的哈希值相同绰沥，繼續(xù)比較：調(diào)用key1所在類的equals(key2)方法，比較：如果equals()返回false:此時(shí)key1-value1添加成功贺待。
如果equals()返回true:使用value1替換value2徽曲。相當(dāng)于把原來(lái)的值替換為新值。
補(bǔ)充：關(guān)于情況2和情況3：此時(shí)key1-value1和原來(lái)的數(shù)據(jù)以鏈表的方式存儲(chǔ)麸塞。
在不斷的添加過(guò)程中秃臣，會(huì)涉及到擴(kuò)容問(wèn)題，當(dāng)超出臨界值(且要存放的位置非空)時(shí)，擴(kuò)容奥此。默認(rèn)的擴(kuò)容方式：擴(kuò)容為原來(lái)容量的2倍弧哎，并將原有的數(shù)據(jù)復(fù)制過(guò)來(lái)。
1.8 相較于jdk7在底層實(shí)現(xiàn)方面的不同：
- new HashMap():底層沒(méi)有創(chuàng)建一個(gè)長(zhǎng)度為16的數(shù)組
- jdk 8底層的數(shù)組是：Node[],而非Entry[]
- 首次調(diào)用put()方法時(shí)稚虎，底層創(chuàng)建長(zhǎng)度為16的數(shù)組
- jdk7底層結(jié)構(gòu)只有：數(shù)組+鏈表撤嫩。jdk8中底層結(jié)構(gòu)：數(shù)組+鏈表+紅黑樹(shù)。當(dāng)數(shù)組的某一個(gè)索引位置上的元素以鏈表形式存在的數(shù)據(jù)個(gè)數(shù) > 8 且當(dāng)前數(shù)組的長(zhǎng)度 > 64時(shí)此時(shí)此索引位置上的所有數(shù)據(jù)改為使用紅黑樹(shù)存儲(chǔ)蠢终。
