散列表（Hash table宣蠕，也叫哈希表）脖捻，是根據(jù)鍵（Key）而直接訪(fǎng)問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)夺溢。也就是說(shuō)论巍，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢(xún)的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄风响，這加快了查找速度嘉汰。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表状勤。
一個(gè)通俗的例子是鞋怀，為了查找電話(huà)簿中某人的號(hào)碼，可以創(chuàng)建一個(gè)按照人名首字母順序排列的表（即建立人名 到首字母
的一個(gè)函數(shù)關(guān)系）持搜，在首字母為W的表中查找“王”姓的電話(huà)號(hào)碼密似，顯然比直接查找就要快得多。這里使用人名作為關(guān)鍵字葫盼，“取首字母”是這個(gè)例子中散列函數(shù)的函數(shù)法則
残腌，存放首字母的表對(duì)應(yīng)散列表。關(guān)鍵字和函數(shù)法則理論上可以任意確定贫导。
1.基本概念
- 若關(guān)鍵字為
抛猫，則其值存放在
的存儲(chǔ)位置上。由此脱盲，不需比較便可直接取得所查記錄邑滨。稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系 f 為散列函數(shù)日缨，按這個(gè)思想建立的表為散列表钱反。
- 對(duì)不同的關(guān)鍵字
，而
面哥，這種現(xiàn)象稱(chēng)為沖突（或碰撞哎壳，英語(yǔ)：Collision）。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱(chēng)做同義詞尚卫。綜上所述归榕，根據(jù)散列函數(shù)
- 若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字特石，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱(chēng)此類(lèi)散列函數(shù)為均勻散列函數(shù)（Uniform Hash function）鳖链，這就使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)“隨機(jī)的地址”姆蘸，從而減少?zèng)_突。
2.構(gòu)造散列函數(shù)的方法
散列函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪(fǎng)問(wèn)過(guò)程更加迅速有效芙委，通過(guò)散列函數(shù)逞敷，數(shù)據(jù)元素將被更快定位。
-
直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線(xiàn)性函數(shù)值為散列地址灌侣。即
或
, 其中
為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）
- 數(shù)字分析法：假設(shè)關(guān)鍵字是以r為基的數(shù)推捐，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址侧啼。
- 平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址玖姑。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適慨菱，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)焰络，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的。取的位數(shù)由表長(zhǎng)決定符喝。
- 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）闪彼，然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。
-
除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址协饲。即 即
,
畏腕。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊法茉稠、平方取中法等運(yùn)算之后取模描馅。對(duì)
的選擇很重要，一般取素?cái)?shù)或
而线，若
3.處理沖突
為了知道沖突產(chǎn)生的相同散列函數(shù)地址所對(duì)應(yīng)的關(guān)鍵字，必須選用另外的散列函數(shù)嘹狞，或者對(duì)沖突結(jié)果進(jìn)行處理岂膳，而不發(fā)生沖突的可能性是非常之小的，所以通常對(duì)沖突進(jìn)行處理磅网。常用方法有以下幾種：
開(kāi)放尋址法(open addressing)谈截。想象一下，有一趟對(duì)號(hào)入座的火車(chē)涧偷，假設(shè)它只有一節(jié)車(chē)廂簸喂，上來(lái)一位坐7號(hào)座位的旅客。過(guò)了一會(huì)兒燎潮，又上來(lái)一位旅客娘赴，他買(mǎi)到的是一張假票，也是7號(hào)座位跟啤，這時(shí)怎么辦呢诽表？列車(chē)長(zhǎng)想了想，讓拿假票的旅客去坐8號(hào)座位隅肥。過(guò)了一會(huì)兒竿奏，應(yīng)該坐8號(hào)座位的旅客上來(lái)了，列車(chē)長(zhǎng)對(duì)他說(shuō)8號(hào)座位已經(jīng)有人了腥放，你去坐9號(hào)座位吧泛啸。哦？9號(hào)早就有人了秃症？10號(hào)也有人了候址？那你去坐11號(hào)吧≈指蹋可以想見(jiàn)岗仑，越到后來(lái)，當(dāng)空座越來(lái)越少時(shí)聚请，碰撞的幾率就越大荠雕，尋找空座愈發(fā)地費(fèi)勁。但是驶赏，如果是火車(chē)的上座率只有50%或者更少的情況呢炸卑？也許真正坐8號(hào)座位的乘客永遠(yuǎn)不會(huì)上車(chē)，那么讓拿假票的乘客坐8號(hào)座位就是一個(gè)很好的策略了煤傍。所以盖文，這是一個(gè)空間換時(shí)間的游戲。玩好這個(gè)游戲的關(guān)鍵是蚯姆，讓旅客分散地坐在車(chē)廂里五续。如何才能做到這一點(diǎn)呢洒敏？答案是，對(duì)于每位不同的旅客使用不同的探查序列返帕。例如，對(duì)于旅客 A篙挽，探查座位 7荆萤，8，23铣卡，56……直到找到一個(gè)空位链韭；對(duì)于旅客B，探查座位 25煮落，66敞峭，77，1蝉仇，3……直到找到一個(gè)空位旋讹。如果有 m 個(gè)座位，每位旅客可以使用 的
個(gè)排列中的一個(gè)轿衔。
顯而易見(jiàn)沉迹，最好減少兩個(gè)旅客使用相同的探查序列的情況。也就是說(shuō)害驹，希望把每位旅客盡量分散地映射到 m! 種探查序列上鞭呕。換句話(huà)說(shuō)，理想狀態(tài)下宛官，如果能夠讓每個(gè)上車(chē)的旅客葫松，使用 個(gè)探查序列中的任意一個(gè)的可能性是相同的，我們就說(shuō)實(shí)現(xiàn)了一致散列底洗。（這里沒(méi)有用“隨機(jī)”這個(gè)詞兒腋么，因?yàn)閷?shí)際是不可能隨機(jī)取一個(gè)探查序列的，因?yàn)樵诓檎疫@名旅客時(shí)還要使用相同的探查序列）亥揖。
線(xiàn)性探查：最簡(jiǎn)單的方法是党晋，如果發(fā)現(xiàn) values[8] 已經(jīng)被占用了，就看看 values[9] 是否空著徐块，如果 values[9] 也被占用了未玻，就看看 values[0] 是不是還空著。完整的描述是胡控，先使用 H() 函數(shù)獲取 k 的第一個(gè)地址扳剿，如果這個(gè)地址已被占用，就探查下一個(gè)緊挨著的地址昼激，如果還是不能用庇绽，就探查下一個(gè)緊挨著的地址锡搜，如果到達(dá)了數(shù)組的末尾，就卷繞到數(shù)組的開(kāi)頭瞧掺，如果探查了 m 次還是沒(méi)有找到空槽耕餐，就說(shuō)明數(shù)組已經(jīng)滿(mǎn)了，這就是線(xiàn)性探查（linear probing）
真正的一致散列是難以實(shí)現(xiàn)的辟狈，實(shí)踐中肠缔，常常采用它的一些近似方法。常用的產(chǎn)生探查序列的方法有：線(xiàn)性探查哼转，平方探測(cè)明未，以及雙重散列探查。這些方法都不能實(shí)現(xiàn)一致散列壹蔓，因?yàn)樗鼈兡墚a(chǎn)生的不同探查序列數(shù)都不超過(guò) 個(gè)（一致散列要求有
個(gè)探查序列）趟妥。在這三種方法中，雙重散列能產(chǎn)生的探查序列數(shù)最多佣蓉，因而能給出最好的結(jié)果披摄。
顯示線(xiàn)性探測(cè)填裝一個(gè)散列表的過(guò)程：
關(guān)鍵字為{89,18,49,58,69}插入到一個(gè)散列表中的情況。此時(shí)線(xiàn)性探測(cè)的方法是取 勇凭。并假定取關(guān)鍵字除以10的余數(shù)為散列函數(shù)法則行疏。
第一次沖突發(fā)生在填裝49的時(shí)候。地址為9的單元已經(jīng)填裝了89這個(gè)關(guān)鍵字套像，所以取 酿联，往下查找一個(gè)單位，發(fā)現(xiàn)為空夺巩，所以將49填裝在地址為0的空單元贞让。
第二次沖突則發(fā)生在58上，取柳譬，往下查找3個(gè)單位喳张，將58填裝在地址為1的空單元。69同理美澳。
表的大小選取至關(guān)重要销部，此處選取10作為大小，發(fā)生沖突的幾率就比選擇質(zhì)數(shù)11作為大小的可能性大制跟。越是質(zhì)數(shù)舅桩，mod取余就越可能均勻分布在表的各處。
聚集（Cluster雨膨，也翻譯做“堆積”）的意思是擂涛，在函數(shù)地址的表中，散列函數(shù)的結(jié)果不均勻地占據(jù)表的單元聊记，形成區(qū)塊撒妈，造成線(xiàn)性探測(cè)產(chǎn)生一次聚集（primary clustering）和平方探測(cè)的二次聚集（secondary clustering）恢暖，散列到區(qū)塊中的任何關(guān)鍵字需要查找多次試選單元才能插入表中，解決沖突狰右，造成時(shí)間浪費(fèi)杰捂。對(duì)于開(kāi)放定址法，聚集會(huì)造成性能的災(zāi)難性損失棋蚌，是必須避免的嫁佳。
轉(zhuǎn)載請(qǐng)注明出處
