全文均為轉(zhuǎn)載作為積累居暖，原文：哈希表 · 筆試面試知識(shí)整理
哈希表（Hash Table，也叫散列表）镊绪，是根據(jù)關(guān)鍵碼值 (Key-Value) 而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)夹攒。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄邮府，以加快查找的速度荧关。哈希表的實(shí)現(xiàn)主要需要解決兩個(gè)問(wèn)題，哈希函數(shù)和沖突解決褂傀。
哈希函數(shù)
哈希函數(shù)也叫散列函數(shù)忍啤，它對(duì)不同的輸出值得到一個(gè)固定長(zhǎng)度的消息摘要。理想的哈希函數(shù)對(duì)于不同的輸入應(yīng)該產(chǎn)生不同的結(jié)構(gòu)仙辟，同時(shí)散列結(jié)果應(yīng)當(dāng)具有同一性（輸出值盡量均勻）和雪崩效應(yīng)（微小的輸入值變化使得輸出值發(fā)生巨大的變化）同波。
沖突解決
現(xiàn)實(shí)中的哈希函數(shù)不是完美的，當(dāng)兩個(gè)不同的輸入值對(duì)應(yīng)一個(gè)輸出值時(shí)叠国，就會(huì)產(chǎn)生“碰撞”未檩，這個(gè)時(shí)候便需要解決沖突。
常見(jiàn)的沖突解決方法有開(kāi)放定址法煎饼，鏈地址法讹挎，建立公共溢出區(qū)等。實(shí)際的哈希表實(shí)現(xiàn)中吆玖，使用最多的是鏈地址法
鏈地址法
鏈地址法的基本思想是筒溃，為每個(gè) Hash 值建立一個(gè)單鏈表，當(dāng)發(fā)生沖突時(shí)沾乘，將記錄插入到鏈表中怜奖。
例 ?設(shè)有 8 個(gè)元素 { a,b,c,d,e,f,g,h } ，采用某種哈希函數(shù)得到的地址分別為： {0 翅阵， 2 歪玲， 4 ， 1 掷匠， 0 滥崩， 8 ， 7 讹语， 2} 钙皮，當(dāng)哈希表長(zhǎng)度為 10 時(shí)，采用鏈地址法解決沖突的哈希表如下圖所示：
