hash表及其應(yīng)用課件

1、HASH函數(shù)及其應(yīng)用雅禮中學(xué) 朱全民第1頁(yè)，共18頁(yè)。什么是HASH？哈希表是一種高效的數(shù)據(jù)結(jié)構(gòu) 。散列方法是使用函數(shù)h將U映射到表T0.m-1的下標(biāo)上（m=O(|U|)）。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。第2頁(yè)，共18頁(yè)。一、整數(shù)的Hash函數(shù) 構(gòu)造方法（1）1直接取余法關(guān)鍵字k除以m，取余數(shù)作為在Hash表中的位置。函數(shù)表達(dá)式可以寫成：h(k)=k mod m一般m選擇為素?cái)?shù)第3頁(yè)，共18頁(yè)。一、整數(shù)的Hash函數(shù) 構(gòu)造方法（2）2乘積取整法關(guān)鍵字k乘以一個(gè)在(0,1)中的實(shí)數(shù)（最好是無理數(shù)），得到一個(gè)(0,1)之

2、間的實(shí)數(shù)；取出其小數(shù)部分，乘以m，再取整數(shù)部分，即得K在Hash表中的位置。函數(shù)表達(dá)式可以寫成：例如 就是一個(gè)好的選擇。第4頁(yè)，共18頁(yè)。一、整數(shù)的Hash函數(shù) 構(gòu)造方法（3）3平方取中法把關(guān)鍵字K平方，然后取中間的 位作為Hash函數(shù)值返回。由于K的每一位都會(huì)對(duì)其平方中間的若干位產(chǎn)生影響，因此這個(gè)方法的效果也是不錯(cuò)的。但是對(duì)于比較小的K值效果并不是很理想，實(shí)現(xiàn)起來也比較繁瑣。為了充分利用Hash表的空間，M最好取2的整數(shù)次冪。例如,表容量M=24=16，關(guān)鍵值K=100，那么 h(k)=8第5頁(yè)，共18頁(yè)。二、字符串的Hash函數(shù) 構(gòu)造方法字符串本身就可以看成一個(gè)256進(jìn)制（ANSI字符串為

3、128進(jìn)制）的大整數(shù)，因此我們可以利用直接取余法，在線性時(shí)間內(nèi)直接算出Hash函數(shù)值。為了保證效果，仍然不能選擇太接近2n的數(shù)；尤其是當(dāng)我們把字符串看成一個(gè)2p進(jìn)制數(shù)的時(shí)候，選擇m= 2p -1會(huì)使得該字符串的任意一個(gè)排列的Hash函數(shù)值都相同。 第6頁(yè)，共18頁(yè)。排列的Hash函數(shù) 讓排列與數(shù)1-A(m,n)之間建立一一對(duì)應(yīng)的關(guān)系。引理 從0到n!-1的任何自然數(shù)可唯一地表示為全排列與自然數(shù)之一一對(duì)應(yīng)不妨設(shè)n個(gè)元素為1,2,.,n。對(duì)應(yīng)的規(guī)則如下:設(shè)序列 (an-1 , a1) 對(duì)應(yīng)的某一排列，其中ai可以看做是排列p中數(shù)i+1所在位置右邊比i+1小的數(shù)的個(gè)數(shù)。以排列4213為例，它是元素1

4、,2,3,4的一個(gè)排列。4的右邊比4小的數(shù)的數(shù)目為3，所以a3=3。3右邊比3小的數(shù)的數(shù)目為0，即a2=0 。同理a1=1 。所以排列4213對(duì)應(yīng)于變進(jìn)制的301，也就是十進(jìn)制的19；反過來也可以從19反推到301，再反推到排列4213。第7頁(yè)，共18頁(yè)。Hash函數(shù)的沖突沖突 兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。 安全避免沖突的條件最理想的解決沖突的方法是安全避免沖突。要做到這一點(diǎn)必須滿足兩個(gè)條件：其一是|U|m其二是選擇合適的散列函數(shù)。 這只適用于|U|較小，且關(guān)鍵字均事先已知的情況，此時(shí)經(jīng)過精心設(shè)計(jì)散列函數(shù)h有可能完

5、全避免沖突。影響沖突的因素 沖突的頻繁程度除了與h相關(guān)外，還與表的填滿程度相關(guān)。 設(shè)m和n分別表示表長(zhǎng)和表中填人的結(jié)點(diǎn)數(shù)，則將=n/m定義為散列表的裝填因子(Load Factor)。越大，表越滿，沖突的機(jī)會(huì)也越大。通常取1。第8頁(yè)，共18頁(yè)。用開放定址法處理沖突沖突發(fā)生時(shí)，使用某種探查(亦稱探測(cè))技術(shù)在散列表中形成一個(gè)探查(測(cè))序列。沿此序列逐個(gè)單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個(gè)開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點(diǎn)存人該地址單元）。查找時(shí)探查到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。開放定址法的一般形式為：hi=(h(ke

6、y)+di)m 1im-1其中： h(key)為散列函數(shù)，di為增量序列，m為表長(zhǎng)。 h(key)是初始的探查位置，后續(xù)的探查位置依次是hl，h2，hm-1，即h(key)，hl，h2，hm-1形成了一個(gè)探查序列。 若令開放地址一般形式的i從0開始，并令d0=0，則h0=h(key)，則有： hi=(h(key)+di)m 0im-1 探查序列可簡(jiǎn)記為hi(0im-1)。第9頁(yè)，共18頁(yè)。HASH應(yīng)用（1）給定兩個(gè)集合A、B，集合內(nèi)的任一元素x滿足1 x 109，并且每個(gè)集合的元素個(gè)數(shù)不大于 104個(gè)。我們希望求出A、B之間的關(guān)系。只需確定在B 中但是不在 A 中的元素的個(gè)數(shù)即可。 第10頁(yè)，

7、共18頁(yè)。分析我們先不管A 與 B 的具體關(guān)系如何，注意到這個(gè)問題的本質(zhì)就是對(duì)于給定的集合A ，確定B 中的元素是否在 A 中。所以，我們使用哈希表來處理。至于哈希函數(shù)，只要按照除余法就行了，由于故意擴(kuò)大了原題的數(shù)據(jù)規(guī)模， H(x) = x mod 15889; 第11頁(yè)，共18頁(yè)。HASH應(yīng)用（2）找名字 給定一個(gè)全部由字符串組成的字典，字符串全部由大寫字母構(gòu)成。其中為每個(gè)字符串編寫密碼，編寫的方式是對(duì)于 n 位字符串，給定一個(gè) n 位數(shù)，大寫字母與數(shù)字的對(duì)應(yīng)方式按照電話鍵盤的方式：2: A,B,C 5: J,K,L 8: T,U,V3: D,E,F 6: M,N,O 9: W,X,Y4:

8、G,H,I 7: P,R,S題目給出一個(gè) 1-12 位的數(shù)，找出在字典中出現(xiàn)且密碼是這個(gè)數(shù)的所有字符串。字典中字符串的個(gè)數(shù)不超過 8000 。 第12頁(yè)，共18頁(yè)。分析 對(duì)于給定的編碼，只需要一個(gè)回溯的過程，所有可能的原字符串都可以被列舉出來，剩下的就是檢查這個(gè)字符串是否在給定的字典中了。所以這個(gè)問題需要的還是“某個(gè)元素是否在已知集合中？”由于給出的“姓名”都是字符串，因此我們可以利用字符的 ASCII 碼。那么，如何設(shè)計(jì)這個(gè)哈希函數(shù)呢？注意到題目給出的字典中，最多能有5000 個(gè)不同元素，而一個(gè)字符的 ASCII 碼只能有26 種不同的取值，因此至少需要用在3個(gè)位置上的字符（263 5000

9、，但是 262 5000 ），于是我們就選取3個(gè)位置上的字符。由于給定的字符串的長(zhǎng)度從 1-12 都有可能，為了容易實(shí)現(xiàn)，選取最開始的1個(gè)字符和最末尾的2個(gè)字符。讓這3個(gè)字符組成27進(jìn)制的3位數(shù)，則這個(gè)數(shù)的值就是這個(gè)字符串的編碼。這樣哈希函數(shù)就設(shè)計(jì)出來了！第13頁(yè)，共18頁(yè)。HASH應(yīng)用（3）轉(zhuǎn)花盆 給定兩個(gè)正6邊形的花壇，要求求出從第一個(gè)變化到第二個(gè)的最小操作次數(shù)以及操作方式。一次操作是：選定不在邊上的一盆花，將這盆花周圍的6盆花按照順時(shí)針或者逆時(shí)針的順序依次移動(dòng)一個(gè)單位。限定一個(gè)花壇里擺放的不同種類的花不超過3種，對(duì)于任意兩種花，數(shù)量多的花的盆數(shù)至少是數(shù)量少的花的2倍。第14頁(yè)，共18頁(yè)。

10、分析 首先確定本題可以用廣度優(yōu)先搜索處理，然后來看問題的規(guī)模。正6邊形共有19個(gè)格子可以用來放花，而且根據(jù)最后一句限定條件，至多只能存在 C(2,19) * C(5,17) = 1058148 種狀態(tài)，用搜索完全可行。然而操作的時(shí)候，可以預(yù)料產(chǎn)生的重復(fù)節(jié)點(diǎn)是相當(dāng)多的，需要迅速判重才能在限定時(shí)間內(nèi)出解，因此想到了哈希表。那么這個(gè)哈希函數(shù)如何設(shè)計(jì)呢？注意到19個(gè)格子組成6邊形是有順序的，而且每一個(gè)格子只有3種可能情況，那么用3進(jìn)制19位數(shù)最大 320-1=3486784400 ，完全可以承受。于是我們將每一個(gè)狀態(tài)與一個(gè)整數(shù)對(duì)應(yīng)起來，使用除余法就可以了。 第15頁(yè)，共18頁(yè)。HASH應(yīng)用（4）方程的

11、解數(shù) 已知一個(gè)n元高次方程： 其中：x1, x2 xn是未知數(shù)， k1,k2 kn是系數(shù)， p1,p2 pn是指數(shù)，且方程中的所有數(shù)均為整數(shù)。假設(shè)未知數(shù)1 xiM, i=1,2,n，求這個(gè)方程的整數(shù)解的個(gè)數(shù)。約束條件1n6；1M150；方程的整數(shù)解的個(gè)數(shù)小于231第16頁(yè)，共18頁(yè)。分析（1）題目要求出給定的方程解的個(gè)數(shù)，這個(gè)方程在最壞的情況下可以有6個(gè)未知數(shù)，而且次數(shù)由輸入決定。這樣就不能利用數(shù)學(xué)方法直接求出解的個(gè)數(shù)，而且注意到解的范圍最多150個(gè)數(shù)，因此恐怕只能使用枚舉法了。最簡(jiǎn)單的思路是窮舉所有未知數(shù)的取值，這樣時(shí)間復(fù)雜度是 O(M6) ，無法承受。否縮小枚舉的范圍呢？第17頁(yè)，共18頁(yè)。分析(2)我們?cè)俅巫⒁獾組 的范圍，若想不超時(shí)，似乎算法的復(fù)雜度上限應(yīng)該是 O(M3) 左右，這是因?yàn)?1503 10000000 。這就啟示我們能否僅僅通過枚舉3個(gè)未知數(shù)的值來找到答案呢？如果這樣，前一半式子的值 S 可以確定，這時(shí)只要枚舉后3 個(gè)數(shù)的值，檢查他們的和是否等于 -S 即可。這樣只相當(dāng)于在 O(M3) 前面加了一個(gè)系數(shù)，當(dāng)然還需要預(yù)先算出 1 到 150