數(shù)據(jù)結(jié)構(gòu)課件ch9哈希表

1、9.3 哈希表 動(dòng)態(tài)查找表1哈希查找也稱為散列查找它不同于前面介紹的幾種查找方法。上述方法都是把查找建立在比較的基礎(chǔ)上，而哈希查找則是通過(guò)計(jì)算存儲(chǔ)地址的方法進(jìn)行查找的。29.3.1什么是哈希表縱觀以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)，有一個(gè)共同點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，因此，查找的過(guò)程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。因此，用這類方法表示的查找表，其平均查找長(zhǎng)度ASL都不為零，不同表示方法的差別僅在于：和給定值進(jìn)行比較的關(guān)鍵字的順序不同。 3對(duì)于頻繁使用的查找表，希望ASL=0。即不需要從“比較”的結(jié)果來(lái)確

2、定查找成功，只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，也就是說(shuō)，記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。4例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為xx000 xx999(前兩位為年份)。則可以下標(biāo)為000 999 的順序表表示之。由于關(guān)鍵字和記錄在表中的序號(hào)相同，則不需要經(jīng)過(guò)比較即可確定待查關(guān)鍵字。數(shù)據(jù)元素存儲(chǔ)位置5但是，對(duì)于動(dòng)態(tài)查找表而言，1) 表長(zhǎng)不確定；2)在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。因此，一般情況，需建立一個(gè)函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)f(key)為哈希函數(shù)。注意：這個(gè)函數(shù)并不

3、一定是數(shù)學(xué)函數(shù)。 6例如：對(duì)于如下9個(gè)關(guān)鍵字 Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ14151617181920212223242526 13設(shè) f(key) = (Ord(第一個(gè)字母)-Ord(A)+1)/282961114127哈希表：ChenDeiHanLiQianSunChenYeZhao12345678910111213.8從這個(gè)例子可見(jiàn)，哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍

4、即可;由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1 key2，而 f(key1) = f(key2)。并且，改進(jìn)哈希函數(shù)只能減少?zèng)_突，而不能避免沖突。因此，在設(shè)計(jì)哈希函數(shù)時(shí)，一方面要考慮選擇一個(gè)“好”的哈希函數(shù);另一方面要選擇一種處理沖突的方法。 9所謂“好”的哈希函數(shù)，指的是，對(duì)于集合中的任意一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)“映象”到地址集合中任何一個(gè)地址的概率是相同的。稱這類哈希函數(shù)為“均勻的”哈希函數(shù)。哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)

5、記錄在表中的存儲(chǔ)位置，這種表被稱為哈希表。所得存儲(chǔ)位置稱為哈希地址(又稱散列地址)。109.3.2哈希函數(shù)的構(gòu)造方法對(duì)數(shù)字的關(guān)鍵字可有下列哈希函數(shù)的構(gòu)造方法，若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。111. 直接定址法哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b如：k1, k2 分別有值 10 、1000；選10、1000 作為存放地址。簡(jiǎn)單、不經(jīng)濟(jì)。僅限于：地址集合的大小 = 關(guān)鍵字集合的大小自身函數(shù)122.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(k1, k2, , kn)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若

6、干位或它們的組合作為地址。僅限于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度，它完全依賴于關(guān)鍵字集合。如果換一個(gè)關(guān)鍵字集合，選擇哪幾位要重新決定。133平方取中法此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象，則先求關(guān)鍵字的平方值，以通過(guò)“平方”擴(kuò)大差別，同時(shí)平方值的中間幾位受到整個(gè)關(guān)鍵字中各位的影響;14設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長(zhǎng)的內(nèi)碼表示。因?yàn)閮?nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定，所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的散列地址大多不相同，即使其中有些字符相同。

7、在平方取中法中，一般取散列地址為 2 的某次冪。例如，若散列地址總數(shù)取為 m = 2r，則對(duì)內(nèi)碼的平方數(shù)取中間的 r 位。如果 r = 3，所取得的散列地址參看下圖的最右一列。15標(biāo)識(shí)符 內(nèi)碼 內(nèi)碼的平方 散列地址A 01 01 001A1 0134 20420 042A9 0144 23420 342 B 02 4 004 DMAX 04150130 21526443617100 443DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236AMAX1 0115013034 3454246522151420 65

8、2標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值164. 折疊法此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。把這些部分的數(shù)據(jù)疊加起來(lái)，就可以得到具有該關(guān)鍵字的記錄的散列地址。有兩種疊加方法：移位法把各部分的最后一位對(duì)齊相加；分界法各部分不折斷，沿各部分的分界來(lái)回折疊，然后對(duì)齊相加，將相加的結(jié)果當(dāng)做散列地址。17示例：設(shè)給定的關(guān)鍵碼為 key = 23938587841，若存儲(chǔ)空間限定 3 位, 則劃分結(jié)果為每段 3 位. 上述關(guān)鍵碼可劃分為 4段： 239 385 878 41把超出地址位數(shù)的最高位刪去, 僅保留最低的3位，做為可用的散列

9、地址。185.除留余數(shù)法 H(key) = key MOD p pm (表長(zhǎng))最簡(jiǎn)單最常用的構(gòu)造哈希函數(shù)的方法：關(guān)鍵問(wèn)題是：如何選取 p ? p 應(yīng)為不大于m 的質(zhì)數(shù)或是不含20以下的質(zhì)因數(shù)的合數(shù)不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。19質(zhì)數(shù):在所有比1大的整數(shù)中，除了1和它本身以外，不再有別的約數(shù)，這種整數(shù)叫做質(zhì)數(shù)，質(zhì)數(shù)又叫做素?cái)?shù)。 合數(shù):合數(shù)是除了1和它本身還能被其他的正整數(shù)整除的正整數(shù)。除2之外的偶數(shù)都是合數(shù)。 20例：key = 12, 39, 18, 24, 33, 21 時(shí)，若取 p=9, 則使所有含質(zhì)因子3的關(guān)鍵字均映射到地址0, 3, 6 上，從而增加了

10、“沖突”的可能性21例：有一個(gè)關(guān)鍵字 key = 962148，散列表大小 m = 25，取質(zhì)數(shù) p= 23。散列函數(shù) H( key ) = key % p。則散列地址為H ( 962148 ) = 962148 % 23 = 12。需要注意的是，使用上面的散列函數(shù)計(jì)算出來(lái)的地址范圍是 0到 22，因此，從23到24這幾個(gè)散列地址實(shí)際上在一開(kāi)始是不可能用散列函數(shù)計(jì)算出來(lái)的，只可能在處理溢出時(shí)達(dá)到這些地址。1234567891011121314151617181920212223242522例假設(shè)哈希表長(zhǎng)度m=13,采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表：16,74,60,43,54,

11、90,46,31,29,88,77。 解：n=11,m=13,除留余數(shù)法的哈希函數(shù)為f(k)=k mod p,p應(yīng)為小于等于m的素?cái)?shù),假設(shè)p取值13。則有： f(16)=3,f(74)=9,f(60)=8,f(43)=4, f(54)=2,f(90)=12,f(46)=7,f(31)=5, f(29)=3, f(88)=10,f(77)=12。 注意：存在沖突。236.隨機(jī)數(shù)法 H(key) = Random(key)適用于關(guān)鍵字長(zhǎng)度不等實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。 24實(shí)際造表時(shí)，考

12、慮的因素：計(jì)算哈希函數(shù)所需時(shí)間；關(guān)鍵字的長(zhǎng)度；哈希表的大??；關(guān)鍵字的分布情況；記錄的查找頻率259.3.3處理沖突的方法假設(shè)哈希表的地址集為0(n-1)，沖突是指由關(guān)鍵字得到的哈希地址為j(0jn-1)的位置上已存在記錄，則處理沖突就是為該關(guān)鍵字的記錄找到另一個(gè)“空”的哈希地址。處理沖突的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。26在處理沖突的過(guò)程中可能得到一個(gè)地址序列Hi(i=1，2，k，hi0，n-1)。即在處理哈希地址的沖突時(shí)，若得到的另外一個(gè)哈希地址Hi任然發(fā)生沖突，則再求下一個(gè)地址H2，若H2任然沖突，再求得H3。依次類推，直至Hk不發(fā)生沖突為止，則Hk為記錄在表中的地址。2

13、7解決沖突的方法又稱為溢出處理技術(shù)。因?yàn)槿我环N散列函數(shù)也不能避免產(chǎn)生沖突，因此選擇好的解決沖突溢出的方法十分重要。281.開(kāi)放定址法 為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列： H0, H1, H2, , Hs 1sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, ,s增量 di 有三種取法：(1)線性探測(cè)再散列：di = ci。最簡(jiǎn)單的情況 c=1(2)平方探測(cè)再散列：di = 12, -12, 22, -22, ,(3)隨機(jī)探測(cè)再散列：di 是一組偽隨機(jī)數(shù)列29注意：增量di應(yīng)具有“完備性”。即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的s(

14、m-1)個(gè)Hi值能覆蓋哈希表中所有的地址。則要求： 平方探測(cè)時(shí)的表長(zhǎng)m必為4j+3的質(zhì)數(shù)； 隨機(jī)探測(cè)時(shí)的m和di沒(méi)有公因子。線性探測(cè)容易產(chǎn)生二次聚集，一次聚集的產(chǎn)生主要取決于哈希函數(shù)，在哈希函數(shù)均勻的前提下，可以認(rèn)為沒(méi)有一次聚集。30線性探測(cè): 假定采用的H函數(shù)為：H(key)= keyMOD11，關(guān)鍵字序列為：17、60、29、38 31當(dāng)散列 38 時(shí)發(fā)生沖突，同 60 爭(zhēng)奪第 5 個(gè)單元解決辦法 ：探測(cè)下一個(gè)空單元，步長(zhǎng)：1 H(key) = ( key+di) MOD 11，其中：di 為 1、210 注意：可取其它步長(zhǎng)，如 3 沖突：初級(jí)沖突：不同關(guān)鍵字值的結(jié)點(diǎn)得到同一個(gè)散列地址。二

15、次聚集：同不同散列地址的結(jié)點(diǎn)爭(zhēng)奪同一個(gè)單元。結(jié)果：沖突加劇，最壞時(shí)可能達(dá)到 O（n）級(jí)代價(jià)。32解決辦法：改變步長(zhǎng)：選和 m 互質(zhì)的數(shù)作為步長(zhǎng)，如 3、5、7 如選步長(zhǎng)為 5，用 H(key) = ( key+5) MOD 11 H(key) = ( key+ 52) MOD 11 H(key) = ( key+ 53) MOD 11 等進(jìn)行下一個(gè)空的單元，直到找到為止。隨機(jī)地改變步長(zhǎng)，如取步長(zhǎng)序列：2，7，4，3，6，1，5，如用 H(key) = ( key+2) MOD 11 H(key) = ( key+7) MOD 11 H(key) = ( key+ 4) MOD 11 等進(jìn)行探測(cè)

16、下一個(gè)空的單元，直到找到為止。33例假設(shè)哈希表長(zhǎng)度m=13,采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77。34對(duì)構(gòu)造的哈希表采用線性探查法解決沖突。解： h(16)=3,h(74)=9,h(60)=8,h(43)=4, h(54)=2,h(90)=12,h(46)=7,h(31)=5, h(29)=3 沖突 d0=3,d1=(3+1) mod 13=4 仍沖突 d2=(4+1) mod 13=5 仍沖突 d3=(5+1) mod 13=6 h(88)=10 h(77)=12 沖突 d0=12,d1=(12+1) mod 13

17、=035下標(biāo)0123456789101112k7754164331294660748890探查次數(shù)21111411111哈希表ha0.12 建立的哈希表ha0.12如下表所示。362.再哈希法出現(xiàn)沖突時(shí)，采用多個(gè)哈希函數(shù)計(jì)算散列地址，直到找到空單元為止?；蛘哂昧硪粋€(gè)哈希函數(shù)作為步長(zhǎng)進(jìn)行探測(cè)，找到下一個(gè)空單元。如：H1(key) = key MOD 11 H2(key) = ( key+ MOD 9)1示例：給出一組表項(xiàng)關(guān)鍵字 22, 41, 53, 46, 30, 13, 01, 67 。散列函數(shù)為：H(x)(3x) % 11。散列表為 HT0.10，m = 11。因此，再散列函數(shù)為 RH(x

18、) = (7x) % 10 +1。 Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2, 37 H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6 H0(30) = 2 沖突 H1 = (2+1) = 3 H0(13) = 6 沖突 H1 = (6+2) = 8 H0(01) = 3 沖突 H1 = (3+8) = 0 H2 = (0+8) = 8 H3 = (8+8) = 5 H4 = (5+8) = 2 H5 = (2+8) = 10 H0(67) = 3 沖突 H1 = (3+10) = 2 H2 = (2+10)

19、= 1 383.鏈地址法將所有哈希地址相同的記錄都鏈接在同一鏈表中。鏈地址肯定不會(huì)產(chǎn)生二次聚集。39例.對(duì)上例構(gòu)造的哈希表采用拉鏈法解決沖突。解：采用拉鏈法解決沖突建立的鏈表如下圖所示。404.公共溢出區(qū)法： 將發(fā)生沖突的結(jié)點(diǎn)都存放在一個(gè)公共溢出區(qū)內(nèi)。41四、哈希表的查找查找過(guò)程和造表過(guò)程一致。假設(shè)采用開(kāi)放定址處理沖突，則查找過(guò)程為: 對(duì)于給定值K, 計(jì)算哈希地址 i = H(K)若ri = NULL 則查找不成功若 ri.key = K 則查找成功否則 求下一地址Hi，直至 rHi = NULL (查找不成功)或 rHi.key = K (查找成功)為止。42 決定哈希表查找的ASL的因素：(1) 選用的哈希函數(shù);(2) 選用的處理沖突的方法;(3)哈希表飽和的程度，裝載因子 值的大小裝填因子=表中填入的記錄數(shù)哈希表的長(zhǎng)度哈希表的ASL是處理沖突方法和裝載因子的函數(shù)。43作 業(yè)在地址空間為016的散列區(qū)中，對(duì)以下關(guān)鍵字序列構(gòu)造兩個(gè)哈希表：（Jan, Feb, M