data:2016-10-3 8:54
HashMap 執(zhí)行原理
內(nèi)部采用數(shù)組與鏈表的結(jié)合形式。 當(dāng)put時(shí)，首先根據(jù)key的hash值（調(diào)用hashcode方法）希停，來(lái)確定該key的value應(yīng)該位于數(shù)組哪個(gè)位置。當(dāng)hash值相同時(shí)筒严，調(diào)用equal方法判斷是否為同一個(gè)數(shù)據(jù)扛芽，相同則省略（hashmap不能存一樣的值，應(yīng)該是覆蓋關(guān)系）腐晾，不同時(shí)叉弦，則加入該數(shù)組中鏈表的開(kāi)頭（例如剛開(kāi)始3號(hào)數(shù)組中的鏈表里面有數(shù)據(jù) a->b->c, 之后put的一個(gè)數(shù)據(jù)d的key的hash值一樣，但是equal 不一樣藻糖，這時(shí)d添加到鏈表的開(kāi)頭淹冰，此時(shí)鏈表的內(nèi)容即為 d->a->b->c）
為了使數(shù)據(jù)的查詢效率提高，所以每個(gè)鏈表最好只有一個(gè)值巨柒，這樣就不需要再去遍歷鏈表了樱拴。hash算法采用2^n容量，可以最大避免碰撞幾率洋满。
static int indexFor(int h, int length) { return h & (length-1); }
擴(kuò)容機(jī)制： loadfactor 擴(kuò)容因子晶乔。當(dāng)數(shù)據(jù)容量超過(guò) 當(dāng)前最大容量*loadfactor時(shí)，容量自動(dòng)擴(kuò)大2倍牺勾，并將當(dāng)前的數(shù)據(jù)重新放入新的hashmap中正罢。所以初始的定義大小為2^n的大小最佳。
