解決哈希沖突的方案有多種：
- 開(kāi)放定址法：發(fā)生沖突弊攘，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址镶柱；
- 再散列函數(shù)法握爷；
- 鏈地址法（HashMap就是采用了鏈地址法跛璧，也就是數(shù)組+鏈表的方式）；
? ? ? ?HashMap的主干是一個(gè)Entry數(shù)組（源碼中叫做table）饼拍。Entry是HashMap的基本組成單元磕蒲，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)。
HashMap對(duì)象中其他幾個(gè)重要字段：
// 實(shí)際存儲(chǔ)key-value鍵值對(duì)的個(gè)數(shù)
transient int size;
// 閾值近她，當(dāng)table（上文中的Entry數(shù)組）為空時(shí)湖蜕，該值為初始容量（初始容量默認(rèn)為16）；當(dāng)table被填充了叨吮，也就是為table分配內(nèi)存空間后辆布，threshold一般為capacity*loadFactroy（capacity即table容量）；HashMap在擴(kuò)容時(shí)需要參考threshold茶鉴，后面會(huì)詳細(xì)談到锋玲。
int threshold;
// 負(fù)載因子，代表了table的填充度有多少涵叮，默認(rèn)是0.75
final int loadFactory;
//用于快速失敗惭蹂，由于HashMap非線程安全，在對(duì)HashMap進(jìn)行迭代時(shí)割粮，如果期間其他線程的參與導(dǎo)致HashMap的結(jié)構(gòu)發(fā)生變化了（比如put盾碗，remove等操作），需要拋出異常ConcurrentModificationException（foreach時(shí)）
transient int modCount;
構(gòu)造器
? ? ? ?在常規(guī)構(gòu)造器中舀瓢，沒(méi)有為數(shù)組table分配內(nèi)存空間（有一個(gè)入?yún)橹付∕ap的構(gòu)造器例外）廷雅，而是在執(zhí)行put操作的時(shí)候才真正構(gòu)建table數(shù)組。
? ? ? ?在構(gòu)造器中對(duì)傳入的初始容量進(jìn)行校驗(yàn)京髓，最大不能超過(guò)MAXIMUM_CAPACITY = 1<<30(230)航缀，且數(shù)組的長(zhǎng)度一定為2的次冪。
int capacity = 1;
// initialCapacity即為構(gòu)造器中可以傳入的自定義HashMap初始容量參數(shù)
while (capacity < initialCapacity)
capacity <<= 1;
? ? ? ?這段代碼保證初始化時(shí)HashMap的容量總是2的n次方堰怨，即底層數(shù)組的長(zhǎng)度總是為2的n次方（具體原因后文會(huì)有介紹）芥玉。
擴(kuò)容resize()
? ? ? ?當(dāng)發(fā)生哈希沖突并且size大于閾值（threshold=capacity*loadFactory）的時(shí)候，需要進(jìn)行數(shù)組擴(kuò)容（resize）备图，擴(kuò)容時(shí)飞傀，需要新建一個(gè)長(zhǎng)度為之前數(shù)組2倍的新的數(shù)組皇型，然后將當(dāng)前的Entry數(shù)組中的元素全部傳輸過(guò)去（遍歷，重新計(jì)算索引位置砸烦，將老數(shù)組數(shù)據(jù)復(fù)制到新數(shù)組中去）弃鸦，擴(kuò)容后的新數(shù)組長(zhǎng)度為之前的2倍，所以擴(kuò)容相對(duì)來(lái)說(shuō)是個(gè)耗資源的操作幢痘。如果capacity已經(jīng)達(dá)到最大（230）唬格，則threshold變?yōu)镮nteger.MAX_VALUE。
? ? ? ?如果loadFactory（負(fù)載因子）取得太大颜说，threshold與capacity太接近购岗，當(dāng)容量增大時(shí)，沖突會(huì)增加门粪，造成同一地址鏈表過(guò)大（當(dāng)size大于threshold時(shí)才擴(kuò)容）喊积；如果太小，哈希表太稀疏玄妈，浪費(fèi)存儲(chǔ)空間乾吻。負(fù)載因子可以大于1（即threshold大于數(shù)組長(zhǎng)度，因?yàn)槭擎湹刂贩ǎ?/p>
PUT存入元素
? ? ? ?Put時(shí)如果key為null拟蜻，存儲(chǔ)位置為table[0]或table[0]的沖突鏈上绎签。如果該對(duì)應(yīng)數(shù)據(jù)已存在，執(zhí)行覆蓋操作酝锅。用新value替換舊value诡必，并返回舊value，如果對(duì)應(yīng)數(shù)據(jù)不存在搔扁，則添加到鏈表的頭上（保證插入O（1））
? ? ? ?put流程：首先判斷key是否為null爸舒，若為null，則直接調(diào)用putForNullKey方法稿蹲。若不為空則先計(jì)算key的hash值扭勉，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素场绿，循環(huán)遍歷鏈表剖效，比較是否存在相同的key嫉入，若存在則覆蓋原來(lái)key的value焰盗，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。若table在該處沒(méi)有元素咒林，則直接保存熬拒。
? ? ? ?最終存儲(chǔ)位置的確定流程是這樣的：
1. hashCode()
? ? ? ?由 Object 類(lèi)定義的 hashCode()方法確實(shí)會(huì)針對(duì)不同的對(duì)象返回不同的整數(shù)。（這一般是通過(guò)將該對(duì)象的內(nèi)部地址轉(zhuǎn)換成一個(gè)整數(shù)來(lái)實(shí)現(xiàn)的）垫竞。
? ? ? ?返回的整數(shù)（散列值）是一個(gè)int類(lèi)型澎粟，此時(shí)如果直接拿該散列值作為下標(biāo)訪問(wèn)HashMap數(shù)組的話蛀序，考慮到2進(jìn)制32位帶符號(hào)的int值范圍從-2147483648到2147483648。前后加起來(lái)有40億的映射空間活烙，只要哈希函數(shù)映射得比較松散徐裸，一般應(yīng)用是很難出現(xiàn)碰撞的。
? ? ? ?但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組啸盏，內(nèi)存是放不下的重贺。HashMap的初始數(shù)組大小才只有16。所以這個(gè)散列值是不能直接用的回懦，需要進(jìn)行一系列的運(yùn)算气笙。
2. hash() 摘自JKD1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
? ? ? ?上面這段代碼稱(chēng)為“擾動(dòng)函數(shù)”（后面會(huì)講到為什么需要這一步）。
3. indexFor()
static int indexFor(int h, int length) {
return h & (length - 1);
}
? ? ? ?h即為hash()函數(shù)的返回值怯晕，indexFor()函數(shù)就是將散列值和數(shù)組長(zhǎng)度做了一個(gè)“與”操作潜圃。
? ? ? ?這也正好解釋了為什么HashMap的數(shù)組長(zhǎng)度要取2的整次冪。因?yàn)檫@樣（數(shù)組長(zhǎng)度-1）正好相當(dāng)于一個(gè)“低位掩碼”舟茶√菲冢“與”操作的結(jié)果就是散列值的高位全部歸零，只保留低位值稚晚，用來(lái)做數(shù)組下標(biāo)訪問(wèn)崇堵。以初始長(zhǎng)度16為例，16-1=15客燕。2進(jìn)制表示為00000000 00000000 00001111鸳劳。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值也搓。
? ? ? ?但此時(shí)問(wèn)題就來(lái)了赏廓，這樣就算我的散列值分布再松散，要是只取最后幾位的話傍妒，沖突也會(huì)很?chē)?yán)重幔摸。而此時(shí)便體現(xiàn)了“擾動(dòng)函數(shù)”（hash()）的作用。
? ? ? ?右移16位颤练，正好是32bit（java中int占4字節(jié)既忆，32位）的一半，將自己的高半?yún)^(qū)和低半?yún)^(qū)做異或嗦玖，就是為了混合原始哈希嗎的高位和低位患雇，以此來(lái)加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征宇挫，這樣高位的信息也被變相保留下來(lái)苛吱。
GET取出元素
? ? ? ?get方法的實(shí)現(xiàn)相對(duì)簡(jiǎn)單，key(hashcode-返回int)-->hash-->indexFor-->最終索引位置器瘪，找到對(duì)應(yīng)位置table[i]翠储，再查看是否有鏈表绘雁，遍歷鏈表，通過(guò)key的equals方法比對(duì)查找對(duì)應(yīng)的記錄援所。（&length-1也將范圍較大的hash值縮小到了length內(nèi)）庐舟。
modCount字段
? ? ? ?我們知道java.util.HashMap不是線程安全的，因此如果在使用迭代器的過(guò)程中有其他線程修改了map住拭，那么將拋出ConcurrentModificationException继阻，這就是所謂fail-fast策略。這一策略在源碼中的實(shí)現(xiàn)是通過(guò)modCount域废酷，modCount顧名思義就是修改次數(shù)瘟檩，對(duì)HashMap內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過(guò)程中會(huì)將這個(gè)值賦給迭代器的expectedModCount澈蟆。在迭代過(guò)程中墨辛，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map趴俘。
HashMap的存放自定義類(lèi)時(shí)睹簇，需要重寫(xiě)自定義類(lèi)的hashCode()和equals()方法
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果對(duì)應(yīng)數(shù)據(jù)已存在，執(zhí)行覆蓋操作寥闪。用新value替換舊value太惠，并返回舊value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
? ? ? ?上面的代碼摘自Put()方法中，已經(jīng)找到對(duì)應(yīng)的table[i]后疲憋，遍歷鏈表時(shí)凿渊。其中hash都是經(jīng)過(guò)hashCode()和hash()函數(shù)的。
? ? ? ?如果不重寫(xiě)equals()方法缚柳，HashMap沒(méi)有判斷兩個(gè)對(duì)象相等的標(biāo)準(zhǔn)埃脏。如果不重寫(xiě)hashCode()，將對(duì)用object默認(rèn)的hashCode()方法（根據(jù)對(duì)象地址生成hashCode）秋忙，如果new了兩個(gè)對(duì)象彩掐，它們的屬性均相同，但由于是兩個(gè)對(duì)象灰追，所以object生成的hashCode不同堵幽，但在HashMap中這兩個(gè)key應(yīng)該當(dāng)做相同的key，但不重寫(xiě)hashCode()則無(wú)法實(shí)現(xiàn)弹澎。
? ? ? ?Get和put方法通過(guò)key的equals方法比對(duì)查找對(duì)應(yīng)的記錄朴下。要注意的是，有人覺(jué)得上面在定位到數(shù)組位置之后然后遍歷鏈表的時(shí)候裁奇，e.hash == hash這個(gè)判斷沒(méi)必要桐猬，僅通過(guò)equals判斷就可以麦撵。其實(shí)不然刽肠，試想一下溃肪，如果傳入的key對(duì)象重寫(xiě)了equals()方法卻沒(méi)有重寫(xiě)hashCode()，而恰巧此對(duì)象定位到這個(gè)數(shù)組位置音五，如果僅僅用equals()判斷可能是相等的惫撰，但其hashCode和當(dāng)前對(duì)象不一致，這種情況躺涝，根據(jù)Object的hashCode的約定厨钻，不能返回當(dāng)前對(duì)象，而應(yīng)該返回null（規(guī)定坚嗜，相等的對(duì)象夯膀，hashcode必須相同）。
多線程同時(shí)操作hashmap時(shí)
? ? ? ?會(huì)產(chǎn)生死循環(huán)苍蔬，如果多個(gè)線程同時(shí)擴(kuò)容诱建，產(chǎn)生兩個(gè)新的table，形成一個(gè)閉環(huán)碟绑。
以上內(nèi)容基于舊版本的jdk俺猿，jdk1.8中對(duì)HashMap的優(yōu)化，請(qǐng)看下篇文章格仲。
JDK1.8中對(duì)HashMap的優(yōu)化
參考文獻(xiàn)
http://www.cnblogs.com/chengxiao/p/6059914.html
https://www.zhihu.com/question/20733617
http://blog.csdn.net/richard_jason/article/details/53887222
http://ifeve.com/hashmap-infinite-loop/
