1. 什么是哈希表
散列表（Hash table舍肠，也叫哈希表）括堤，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu).也就是說羡宙，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄烁登，以加快查找的速度贫导。這個映射函數(shù)叫做散列函數(shù)抱完，存放記錄的數(shù)組叫做散列表贼陶。
也是基于數(shù)組來實(shí)現(xiàn)。
Hash表也稱散列表，也有直接譯作哈希表每界，Hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)捅僵，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別眨层，它能夠快速定位到想要查找的記錄庙楚，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來進(jìn)行查找。這個源于Hash表設(shè)計(jì)的特殊性趴樱，它采用了函數(shù)映射的思想將記錄的存儲位置與記錄的關(guān)鍵字關(guān)聯(lián)起來馒闷，從而能夠很快速地進(jìn)行查找。
1.Hash表的設(shè)計(jì)思想
對于一般的線性表叁征，比如鏈表纳账，如果要存儲聯(lián)系人信息：
張三 13980593357
李四 15828662334
王五 13409821234
張帥 13890583472
那么可能會設(shè)計(jì)一個結(jié)構(gòu)體包含姓名，手機(jī)號碼這些信息捺疼，然后把4個聯(lián)系人的信息存到一張鏈表中疏虫。當(dāng)要查找”李四 15828662334“這條記錄是否在這張鏈表中或者想要得到李四的手機(jī)號碼時，可能會從鏈表的頭結(jié)點(diǎn)開始遍歷啤呼，依次將每個結(jié)點(diǎn)中的姓名同”李四“進(jìn)行比較卧秘，直到查找成功或者失敗為止，這種做法的時間復(fù)雜度為O(n)官扣。即使采用二叉排序樹進(jìn)行存儲翅敌，也最多為O(logn)。假設(shè)能夠通過”李四“這個信息直接獲取到該記錄在表中的存儲位置惕蹄，就能省掉中間關(guān)鍵字比較的這個環(huán)節(jié)蚯涮，復(fù)雜度直接降到O(1)。Hash表就能夠達(dá)到這樣的效果卖陵。
Hash表采用一個映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲位置遭顶，從而在想要查找該記錄時，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲位置泪蔫，通常情況下棒旗，這種映射關(guān)系稱作為Hash函數(shù)，而通過Hash函數(shù)和關(guān)鍵字計(jì)算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置鸥滨，并不是實(shí)際的物理地址)稱作為Hash地址嗦哆。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲婿滓，則當(dāng)想要找到“李四”的信息時老速，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可。下面討論一下Hash表設(shè)計(jì)中的幾個關(guān)鍵問題凸主。
1.1. Hash函數(shù)的設(shè)計(jì)
Hash函數(shù)設(shè)計(jì)的好壞直接影響到對Hash表的操作效率橘券。下面舉例說明：
假如對上述的聯(lián)系人信息進(jìn)行存儲時，采用的Hash函數(shù)為：姓名的每個字的拼音開頭大寫字母的ASCII碼之和。
因此address(張三)=ASCII(Z)+ASCII(S)=90+83=173;
address(李四)=ASCII(L)+ASCII(S)=76+83=159;
address(王五)=ASCII(W)+ASCII(W)=87+87=174;
address(張帥)=ASCII(Z)+ASCII(S)=90+83=173;
假如只有這4個聯(lián)系人信息需要進(jìn)行存儲旁舰，這個Hash函數(shù)設(shè)計(jì)的很糟糕锋华。首先，它浪費(fèi)了大量的存儲空間箭窜，假如采用char型數(shù)組存儲聯(lián)系人信息的話毯焕，則至少需要開辟174*12字節(jié)的空間，空間利用率只有4/174磺樱，不到5%纳猫；另外，根據(jù)Hash函數(shù)計(jì)算結(jié)果之后竹捉，address(張三)和address(李四)具有相同的地址芜辕，這種現(xiàn)象稱作沖突，對于174個存儲空間中只需要存儲4條記錄就發(fā)生了沖突块差，這樣的Hash函數(shù)設(shè)計(jì)是很不合理的侵续。所以在構(gòu)造Hash函數(shù)時應(yīng)盡量考慮關(guān)鍵字的分布特點(diǎn)來設(shè)計(jì)函數(shù)使得Hash地址隨機(jī)均勻地分布在整個地址空間當(dāng)中。通常有以下幾種構(gòu)造Hash函數(shù)的方法：
1)直接定址法
取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)為Hash地址憨闰，即address(key)=a*key+b;如知道學(xué)生的學(xué)號從2000開始状蜗，最大為4000，則可以將address(key)=key-2000作為Hash地址起趾。
2)平方取中法
對關(guān)鍵字進(jìn)行平方運(yùn)算诗舰，然后取結(jié)果的中間幾位作為Hash地址警儒。假如有以下關(guān)鍵字序列{421训裆，423，436}蜀铲，平方之后的結(jié)果為{177241边琉，178929，190096}记劝，那么可以取{72变姨，89，00}作為Hash地址厌丑。
3)折疊法
將關(guān)鍵字拆分成幾部分定欧，然后將這幾部分組合在一起，以特定的方式進(jìn)行轉(zhuǎn)化形成Hash地址怒竿。假如知道圖書的ISBN號為8903-241-23砍鸠，可以將address(key)=89+03+24+12+3作為Hash地址。
4)除留取余法
如果知道Hash表的最大長度為m耕驰，可以取不大于m的最大質(zhì)數(shù)p爷辱，然后對關(guān)鍵字進(jìn)行取余運(yùn)算，address(key)=key%p。
在這里p的選取非常關(guān)鍵饭弓，p選擇的好的話双饥，能夠最大程度地減少沖突，p一般取不大于m的最大質(zhì)數(shù)弟断。
2.Hash表大小的確定
Hash表大小的確定也非常關(guān)鍵咏花，如果Hash表的空間遠(yuǎn)遠(yuǎn)大于最后實(shí)際存儲的記錄個數(shù)，則造成了很大的空間浪費(fèi)阀趴，如果選取小了的話迟螺，則容易造成沖突。在實(shí)際情況中舍咖，一般需要根據(jù)最終記錄存儲個數(shù)和關(guān)鍵字的分布特點(diǎn)來確定Hash表的大小矩父。還有一種情況時可能事先不知道最終需要存儲的記錄個數(shù)，則需要動態(tài)維護(hù)Hash表的容量排霉，此時可能需要重新計(jì)算Hash地址窍株。
3.沖突的解決
在上述例子中，發(fā)生了沖突現(xiàn)象攻柠，因此需要辦法來解決球订，否則記錄無法進(jìn)行正確的存儲。通常情況下有2種解決辦法：
1)開放定址法
即當(dāng)一個關(guān)鍵字和另一個關(guān)鍵字發(fā)生沖突時瑰钮，使用某種探測技術(shù)在Hash表中形成一個探測序列冒滩，然后沿著這個探測序列依次查找下去，當(dāng)碰到一個空的單元時浪谴，則插入其中开睡。比較常用的探測方法有線性探測法，比如有一組關(guān)鍵字{12苟耻，13篇恒，25，23凶杖，38胁艰，34，6智蝠，84腾么，91}，Hash表長為14杈湾，Hash函數(shù)為address(key)=key%11解虱，當(dāng)插入12，13毛秘，25時可以直接插入饭寺，而當(dāng)插入23時阻课，地址1被占用了，因此沿著地址1依次往下探測(探測步長可以根據(jù)情況而定)艰匙，直到探測到地址4限煞，發(fā)現(xiàn)為空，則將23插入其中员凝。
2)鏈地址法
采用數(shù)組和鏈表相結(jié)合的辦法署驻，將Hash地址相同的記錄存儲在一張線性表中，而每張表的表頭的序號即為計(jì)算得到的Hash地址健霹。如上述例子中旺上，采用鏈地址法形成的Hash表存儲表示為：
雖然能夠采用一些辦法去減少沖突，但是沖突是無法完全避免的糖埋。因此需要根據(jù)實(shí)際情況選取解決沖突的辦法宣吱。
4.Hash表的平均查找長度
Hash表的平均查找長度包括查找成功時的平均查找長度和查找失敗時的平均查找長度。
查找成功時的平均查找長度=表中每個元素查找成功時的比較次數(shù)之和/表中元素個數(shù)瞳别；
查找不成功時的平均查找長度相當(dāng)于在表中查找元素不成功時的平均比較次數(shù)征候，可以理解為向表中插入某個元素，該元素在每個位置都有可能祟敛，然后計(jì)算出在每個位置能夠插入時需要比較的次數(shù)疤坝，再除以表長即為查找不成功時的平均查找長度。
下面舉個例子：
有一組關(guān)鍵字{23馆铁，12跑揉，14，2埠巨，3历谍，5}，表長為14乖订，Hash函數(shù)為key%11扮饶，則關(guān)鍵字在表中的存儲如下：
地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13
關(guān)鍵字 23 12 14 2 3 5
比較次數(shù) 1 2 1 3 3 2
因此查找成功時的平均查找長度為(1+2+1+3+3+2)/6=11/6具练；
查找失敗時的平均查找長度為(1+7+6+5+4+3+2+1+1+1+1+1+1+1)/14=38/14乍构；
這里有一個概念裝填因子=表中的記錄數(shù)/哈希表的長度，如果裝填因子越小扛点，表明表中還有很多的空單元哥遮，則發(fā)生沖突的可能性越小陵究；而裝填因子越大眠饮，則發(fā)生沖突的可能性就越大，在查找時所耗費(fèi)的時間就越多铜邮。因此仪召，Hash表的平均查找長度和裝填因子有關(guān)寨蹋。有相關(guān)文獻(xiàn)證明當(dāng)裝填因子在0.5左右的時候，Hash的性能能夠達(dá)到最優(yōu)扔茅。因此已旧，一般情況下，裝填因子取經(jīng)驗(yàn)值0.5召娜。
5.Hash表的優(yōu)缺點(diǎn)
Hash表存在的優(yōu)點(diǎn)顯而易見运褪，能夠在常數(shù)級的時間復(fù)雜度上進(jìn)行查找，并且插入數(shù)據(jù)和刪除數(shù)據(jù)比較容易玖瘸。但是它也有某些缺點(diǎn)秸讹，比如不支持排序，一般比用線性表存儲需要更多的空間雅倒，并且記錄的關(guān)鍵字不能重復(fù)璃诀。
借鑒博客：海子
