1. HashMap的數(shù)據(jù)結(jié)構(gòu)
在java編程語言中巧婶，最基本的結(jié)構(gòu)就是兩種缸血，一個(gè)是數(shù)組物蝙，另外一個(gè)是模擬指針（引用）澜汤，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來構(gòu)造的蚜迅，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)俊抵，即數(shù)組和鏈表的結(jié)合體谁不。數(shù)組和鏈表分別擁有不同的優(yōu)勢(shì)和缺點(diǎn)，而HashMap把它們組合起來了务蝠。
數(shù)組存儲(chǔ)區(qū)間是連續(xù)的拍谐，占用內(nèi)存嚴(yán)重烛缔，故空間復(fù)雜的很大馏段。但數(shù)組的二分查找時(shí)間復(fù)雜度小，為O(1)践瓷；數(shù)組的特點(diǎn)是：尋址容易院喜，插入和刪除困難；
鏈表存儲(chǔ)區(qū)間離散晕翠，占用內(nèi)存比較寬松喷舀，故空間復(fù)雜度很小砍濒，但時(shí)間復(fù)雜度很大，達(dá)O（N）硫麻。鏈表的特點(diǎn)是：尋址困難爸邢，插入和刪除容易。
其中Java源碼如下：
static class Entry?implements Map.Entry{
final K key;
V value;
Entry?next;final int hash;
……}
可以看出拿愧，Entry就是數(shù)組中的元素杠河，每個(gè) Map.Entry 其實(shí)就是一個(gè)key-value對(duì)，它持有一個(gè)指向下一個(gè)元素的引用浇辜，這就構(gòu)成了鏈表券敌。
2、HashMap實(shí)現(xiàn)存儲(chǔ)和讀取
1)存儲(chǔ)數(shù)據(jù)
public V put(K key, V value) {
//HashMap允許存放null鍵和null值柳洋。3//當(dāng)key為null時(shí)待诅，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置
if(key ==null)
return putForNullKey(value);
//根據(jù)key的keyCode重新計(jì)算hash值熊镣。
int hash =hash(key.hashCode());
//搜索指定hash值在對(duì)應(yīng)table中的索引卑雁。
int i =indexFor(hash, table.length);
//如果 i 索引處的 Entry 不為 null，通過循環(huán)不斷遍歷 e 元素的下一個(gè)元素轧钓。
for(Entry e = table[i]; e !=null; e =e.next)?{
Object k;
if(e.hash == hash && ((k = e.key) == key ||key.equals(k)))?{
//如果發(fā)現(xiàn)已有該鍵值序厉，則存儲(chǔ)新的值毕箍，并返回原始值
V oldValue =e.value;
e.value =value;
e.recordAccess(this);
returnoldValue;}20}
//如果i索引處的Entry為null，表明此處還沒有Entry而柑。
modCount++;
//將key文捶、value添加到i索引處媒咳。
addEntry(hash, key, value, i);
return null;
}
根據(jù)hash值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)），如果數(shù)組該位置上已經(jīng)存放有其他元素了涩澡，那么在這個(gè)位置上的元素將以鏈表的形式存放顽耳，新加入的放在鏈頭妙同，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素粥帚，就直接將該元素放到此數(shù)組中的該位置上胰耗。hash(int h)方法根據(jù)key的hashCode重新計(jì)算一次散列芒涡。此算法加入了高位計(jì)算卖漫，防止低位不變，高位變化時(shí)赠群，造成的hash沖突。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);4
}
我們可以看到在HashMap中要找到某個(gè)元素查描，需要根據(jù)key的hash值來求得對(duì)應(yīng)數(shù)組中的位置。如何計(jì)算這個(gè)位置就是hash算法叹誉。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合鸯两，所以我們當(dāng)然希望這個(gè)HashMap里面的元素位置盡量的分布均勻些长豁，盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)钧唐，那么當(dāng)我們用hash算法求得這個(gè)位置的時(shí)候，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要的匠襟，而不用再去遍歷鏈表钝侠，這樣就大大優(yōu)化了查詢的效率。
根據(jù)上面 put 方法的源代碼可以看出酸舍，當(dāng)程序試圖將一個(gè)key-value對(duì)放入HashMap中時(shí)帅韧，程序首先根據(jù)該 key的 hashCode() 返回值決定該 Entry 的存儲(chǔ)位置：如果兩個(gè) Entry 的 key 的 hashCode() 返回值相同，那它們的存儲(chǔ)位置相同啃勉。如果這兩個(gè) Entry 的 key 通過 equals 比較返回 true忽舟，新添加 Entry 的 value 將覆蓋集合中原有 Entry的 value，但key不會(huì)覆蓋淮阐。如果這兩個(gè) Entry 的 key 通過 equals 比較返回 false叮阅，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部——具體說明繼續(xù)看 addEntry() 方法的說明泣特。
通過這種方式就可以高效的解決HashMap的沖突問題浩姥。
2）獲取數(shù)據(jù)
public V get(Object key) {
if(key ==null)
return getForNullKey();
int hash =hash(key.hashCode());
for(Entrye =table[indexFor(hash, table.length)];
e !=null;
e =e.next) {
Object k;
if(e.hash == hash && ((k = e.key) == key ||key.equals(k)))
return e.value;
}
return null;
}
從HashMap中g(shù)et元素時(shí)，首先計(jì)算key的hashCode状您，找到數(shù)組中對(duì)應(yīng)位置的某一元素勒叠，然后通過key的equals方法在對(duì)應(yīng)位置的鏈表中找到需要的元素。
3）歸納起來簡(jiǎn)單地說膏孟，HashMap 在底層將 key-value 當(dāng)成一個(gè)整體進(jìn)行處理眯分，這個(gè)整體就是一個(gè) Entry 對(duì)象。HashMap 底層采用一個(gè) Entry[] 數(shù)組來保存所有的 key-value 對(duì)骆莹，當(dāng)需要存儲(chǔ)一個(gè) Entry 對(duì)象時(shí)颗搂，會(huì)根據(jù)hash算法來決定其在數(shù)組中的存儲(chǔ)位置担猛，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置幕垦；當(dāng)需要取出一個(gè)Entry時(shí)丢氢，也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry先改。
3疚察、HashMap的resize
當(dāng)hashmap中的元素越來越多的時(shí)候，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長(zhǎng)度是固定的）仇奶，所以為了提高查詢的效率貌嫡，就要對(duì)hashmap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中该溯，所以這是一個(gè)通用的操作岛抄，很多人對(duì)它的性能表示過懷疑，不過想想我們的“均攤”原理狈茉，就釋然了夫椭，而在hashmap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置氯庆，并放進(jìn)去蹭秋，這就是resize堤撵。
那么hashmap什么時(shí)候進(jìn)行擴(kuò)容呢？當(dāng)hashmap中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor時(shí)实昨，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75荒给，也就是說，默認(rèn)情況下锐墙，數(shù)組大小為16，那么當(dāng)hashmap中元素個(gè)數(shù)超過16*0.75=12的時(shí)候溪北，就把數(shù)組的大小擴(kuò)展為2*16=32，即擴(kuò)大一倍之拨，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作烁竭，所以如果我們已經(jīng)預(yù)知hashmap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高h(yuǎn)ashmap的性能吉挣。比如說婉弹，我們有1000個(gè)元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適终吼，不過上面annegu已經(jīng)說過，即使是1000际跪，hashmap也自動(dòng)會(huì)將其設(shè)置為1024。 但是new HashMap(1024)還不是更合適的姆打，因?yàn)?.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題幔戏，也避免了resize的問題。
總結(jié)：HashMap的實(shí)現(xiàn)原理：
利用key的hashCode重新hash計(jì)算出當(dāng)前對(duì)象的元素在數(shù)組中的下標(biāo)
存儲(chǔ)時(shí)评抚，如果出現(xiàn)hash值相同的key，則覆蓋原始值慨代，記住，覆蓋不是刪除侍匙，而是則將當(dāng)前的key-value放入鏈表中了。
獲取時(shí)想暗，直接找到hash值對(duì)應(yīng)的下標(biāo)，在進(jìn)一步判斷key是否相同说莫，從而找到對(duì)應(yīng)值。
理解了以上過程就不難明白HashMap是如何解決hash沖突的問題储狭，核心就是使用了數(shù)組的存儲(chǔ)方式，然后將沖突的key的對(duì)象放入鏈表中辽狈，一旦發(fā)現(xiàn)沖突就在鏈表中做進(jìn)一步的對(duì)比。
