全文均為轉(zhuǎn)載作為積累，原文：哈希表 · 筆試面試知識(shí)整理

哈希表（Hash Table，也叫散列表），是根據(jù)關(guān)鍵碼值 (Key-Value) 而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。哈希表的實(shí)現(xiàn)主要需要解決兩個(gè)問題，哈希函數(shù)和沖突解決。

哈希函數(shù)

哈希函數(shù)也叫散列函數(shù)，它對(duì)不同的輸出值得到一個(gè)固定長度的消息摘要。理想的哈希函數(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í)候便需要解決沖突。

常見的沖突解決方法有開放定址法，鏈地址法，建立公共溢出區(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)哈希表長度為 10 時(shí)，采用鏈地址法解決沖突的哈希表如下圖所示：