1、上章回顧,常見的排序算法有哪些 其中那種算法的效率最高 對大量的數(shù)據(jù)進行排序的化最好使用那種排序算法,哈希表,第七章,預習檢查,哈希表的定義 處理沖突的方法有那些,本章結(jié)構(gòu),處理沖突的方法,哈希表,哈希函數(shù)的構(gòu)造方法,什么是哈希表,課程目標,了解什么是哈希表 掌握如何構(gòu)造哈希函數(shù) 處理沖突的方式 哈希表的查找及分析,2020/7/29,6,7.1 哈希表,哈希表又稱散列表。 哈希表存儲的基本思想是：以數(shù)據(jù)表中的每個記錄的關(guān)鍵字 k為自變量，通過一種函數(shù)H(k)計算出函數(shù)值。把這個值解釋為一塊連續(xù)存儲空間（即數(shù)組空間）的單元地址（即下標），將該記錄存儲到這個單元中。在此稱該函數(shù)H為哈希函數(shù)或散列

2、函數(shù)。按這種方法建立的表稱為哈希表或散列表。,2020/7/29,7,例如，要將關(guān)鍵字值序列（3，15，22，24），存儲到編號為0到4的表長為5的哈希表中。 計算存儲地址的哈希函數(shù)可取除5的取余數(shù)算法H(k)=k % 5。則構(gòu)造好的哈希表如圖所示。,7.1 哈希表,2020/7/29,8,理想情況下，哈希函數(shù)在關(guān)鍵字和地址之間建立了一個一一對應關(guān)系，從而使得查找只需一次計算即可完成。由于關(guān)鍵字值的某種隨機性，使得這種一一對應關(guān)系難以發(fā)現(xiàn)或構(gòu)造。因而可能會出現(xiàn)不同的關(guān)鍵字對應一個存儲地址。即k1k2，但H(k1)=H(k2)，這種現(xiàn)象稱為沖突。 把這種具有不同關(guān)鍵字值而具有相同哈希地址的對象稱

3、“同義詞”。 在大多數(shù)情況下，沖突是不能完全避免的。這是因為所有可能的關(guān)鍵字的集合可能比較大，而對應的地址數(shù)則可能比較少。 對于哈希技術(shù)，主要研究兩個問題： （1）如何設(shè)計哈希函數(shù)以使沖突盡可能少地發(fā)生。 （2）發(fā)生沖突后如何解決。,7.1 哈希表,2020/7/29,9,構(gòu)造好的哈希函數(shù)的方法，應能使沖突盡可能地少，因而應具有較好的隨機性。這樣可使一組關(guān)鍵字的散列地址均勻地分布在整個地址空間。根據(jù)關(guān)鍵字的結(jié)構(gòu)和分布的不同，可構(gòu)造出許多不同的哈希函數(shù)。 1直接定址法 直接定址法是以關(guān)鍵字k本身或關(guān)鍵字加上某個數(shù)值常量c作為哈希地址的方法。該哈希函數(shù)H(k)為： H(k)=k+c (c0) 這種

4、哈希函數(shù)計算簡單，并且不可能有沖突發(fā)生。當關(guān)鍵字的分布基本連續(xù)時，可使用直接定址法的哈希函數(shù)。否則，若關(guān)鍵字分布不連續(xù)將造成內(nèi)存單元的大量浪費。,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,10,例：統(tǒng)計某地區(qū)從1949年到1995年每年出生的人數(shù)，列在一張表中。年份為關(guān)鍵字，因共有47年，所以表中位置范圍是147。 設(shè)置H(k)=k-1948即可，其中k為年份數(shù)。 這樣的哈希表示意如下：,若要查1970年的出生人數(shù)，則根據(jù)（1970-1948=22）計算，在表的第22個位置即可找到。,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,11,2除留余數(shù)法 取關(guān)鍵字k除以哈希表長度m所

5、得余數(shù)作為哈希函數(shù)地址的方法。即： H(k)=km 這是一種較簡單、也是較常見的構(gòu)造方法。這種方法的關(guān)鍵是選擇好哈希表的長度m。使得數(shù)據(jù)集合中的每一個關(guān)鍵字通過該函數(shù)轉(zhuǎn)化后映射到哈希表的任意地址上的概率相等。理論研究表明，在m取值為素數(shù)（質(zhì)數(shù)）時，沖突可能性相對較少。,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,12,3平方取中法 取關(guān)鍵字平方后的中間幾位作為哈希函數(shù)地址（若超出范圍時，可再取模）。 設(shè)有一組關(guān)鍵字ABC，BCD,CDE，DEF，其對應的機內(nèi)碼如表所示。假定地址空間的大小為1000，編號為0-999?，F(xiàn)按平方取中法構(gòu)造哈希函數(shù)，則可取關(guān)鍵字機內(nèi)碼平方后的中間三位作為存儲

6、位置。計算過程如下表所示：,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,13,4折疊法 這種方法適合在關(guān)鍵字的位數(shù)較多，而地址區(qū)間較小的情況。 將關(guān)鍵字分隔成位數(shù)相同的幾部分。然后將這幾部分的疊加和作為哈希地址（若超出范圍，可再取模）。 例如，假設(shè)關(guān)鍵字為某人身份證號碼430104681015355，則可以用4位為一組進行疊加。即有5355+8101+1046+430=14932，舍去高位。 則有H(430104681015355)=4932 為該身份證關(guān)鍵字的哈希函數(shù)地址。,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,14,5數(shù)值分析法 若事先知道所有可能的關(guān)鍵字的取值時，可

7、通過對這些關(guān)鍵字進行分析，發(fā)現(xiàn)其變化規(guī)律，構(gòu)造出相應的哈希函數(shù)。 例：對如下一組關(guān)鍵字通過分析可知：每個關(guān)鍵字從左到右的第l，2，3位和第6位取值較集中，不宜作哈希地址。 剩余的第4，5，7和8位取值較分散，可根據(jù)實際需要取其中的若干位作為哈希地址。,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,15,若取最后兩位作為哈希地址，則哈希地址的集合為下表所示：,7.1.1 哈希函數(shù)的構(gòu)造方法,2020/7/29,16,7.1.2 沖突的解決方法,假設(shè)哈希表的地址范圍為0m-l，當對給定的關(guān)鍵字k，由哈希函數(shù)H(k)算出的哈希地址為i（0im-1）的位置上已存有記錄，這種情況就是沖突現(xiàn)象。 處

8、理沖突就是為該關(guān)鍵字的記錄找到另一個“空”的哈希地址。即通過一個新的哈希函數(shù)得到一個新的哈希地址。如果仍然發(fā)生沖突，則再求下一個，依次類推。直至新的哈希地址不再發(fā)生沖突為止。 常用的處理沖突的方法有開放地址法、鏈地址法兩大類,2020/7/29,17,1開放定址法 用開放定址法處理沖突就是當沖突發(fā)生時，形成一個地址序列。沿著這個序列逐個探測，直到找出一個“空”的開放地址。將發(fā)生沖突的關(guān)鍵字值存放到該地址中去。 如 Hi=(H(k)+d（i）) % m, i=1，2，k (km-1) 其中H(k)為哈希函數(shù)，m為哈希表長，d為增量函數(shù)，d(i)=dl，d2dn-l。 增量序列的取法不同，可得到不

9、同的開放地址處理沖突探測方法。,7.1.2 沖突的解決方法,2020/7/29,18,（1）線性探測法 線性探測法是從發(fā)生沖突的地址（設(shè)為d）開始，依次探查d+l，d+2，m-1（當達到表尾m-1時，又從0開始探查）等地址，直到找到一個空閑位置來存放沖突處的關(guān)鍵字。 若整個地址都找遍仍無空地址，則產(chǎn)生溢出。 線性探查法的數(shù)學遞推描述公式為： d0=H(k) di=(di-1+1)% m (1im-1),7.1.2 沖突的解決方法,2020/7/29,19,【例】已知哈希表地址區(qū)間為010，給定關(guān)鍵字序列（20，30，70，15，8，12，18，63，19）。哈希函數(shù)為H(k)=kll，采用線性

10、探測法處理沖突，則將以上關(guān)鍵字依次存儲到哈希表中。試構(gòu)造出該哈希表，并求出等概率情況下的平均查找長度。 假設(shè)數(shù)組為A, 本題中各元素的存放過程如下： H(20)=9，可直接存放到A9中去。 H(30)=8，可直接存放到A8中去。 H(70)=4，可直接存放到A4中去。 H(15)=4，沖突； d0=4 d1=(4+1)%11=5，將15放入到A5中。 H(8)=8，沖突； d0=8 d1=(8+1)%11=9，仍沖突； d2=(8+2)%11=10，將8放入到A10中。,7.1.2 沖突的解決方法,2020/7/29,20,H(12)=l，可直接存放到A1中去。 H(18)=7，可直接存放到A

11、7中去。 H(63)=8，沖突； d0=8 d1=(8+1)%11=9，仍沖突; d2=(8+2)%11=10，仍沖突; d3=(8+3)%11=0，將63放入到A0中。 H(19)=8，沖突； d0=8 d1=(8+1)%11=9，仍沖突; d2=(8+2)%11=10，仍沖突; d3=(8+3)%11=0，仍沖突; d4=(8+4)%11=1，仍沖突; d5=(8+5)%11=2，將19放入到A2中。,7.1.2 沖突的解決方法,2020/7/29,21,由此得哈希表如圖所示,在等概率情況下成功的平均查找長度為： （1*5+2+3+4+6）/9 =20/9 利用線性探查法處理沖突容易造成關(guān)

12、鍵字的“堆積”問題。這是因為當連續(xù)n個單元被占用后，再散列到這些單元上的關(guān)鍵字和直接散列到后面一個空閑單元上的關(guān)鍵字都要占用這個空閑單元，致使該空閑單元很容易被占用，從而發(fā)生非同義沖突。造成平均查找長度的增加。 為了克服堆積現(xiàn)象的發(fā)生，可以用下面的方法替代線性探查法。,7.1.2 沖突的解決方法,2020/7/29,22,（2）平方探查法 設(shè)發(fā)生沖突的地址為d，則平方探查法的探查序列為：d+12，d+22，直到找到一個空閑位置為止。 平方探查法的數(shù)學描述公式為： d0=H(k) di=(d0+i2) % m (1im-1),7.1.2 沖突的解決方法,2020/7/29,23,【例】已知哈希表

13、地址區(qū)間為010，給定關(guān)鍵字序列（20，30，70，15，8，12，18，63，19）。哈希函數(shù)為H(k)=kll，采用平方探查法處理沖突。 【解】 H(20)=9，可直接存放到A9中去。 H(30)=8，可直接存放到A8中去。 H(70)=4，可直接存放到A4中去。 H(15)=4，沖突； d0=4 d1=(4+12) % 11=5，放到A5中。,7.1.2 沖突的解決方法,2020/7/29,24,H(8)=8，沖突； d0=8 d1=(8+12) % 11=9，仍沖突 d2=(8+22) % 11=1 放到A1中。 H(12)=l，沖突； d0=1 d1=(1+12) % 11=2，放到

14、A2中。 H(18)=7，可直接存放到A7中去。,7.1.2 沖突的解決方法,2020/7/29,25,H(63)=8，沖突； d0=8 d1=(8+12) % 11=9，仍沖突 d2=(8+22) % 11=1，仍沖突 d3=(8+32) % 11=6，放到A6中。 H(19)=8，沖突； d0=8 d1=(8+12) % 11=9，仍沖突 d2=(8+22) % 11=1，仍沖突 d3=(8+32) % 11=6，仍沖突 d4=(8+42)% 11= 2，仍沖突 d5=(8+52) % 11=0，放到A0中,7.1.2 沖突的解決方法,2020/7/29,26,建立的哈希表如圖所示：,在等

15、概率情況下成功的平均查找長度為： （1*4+2*2+3+4+6）/9 =21/9 平方探查法是一種較好的處理沖突的方法，可以避免出現(xiàn)堆積問題。它的缺點是不能探查到哈希表上的所有單元，但至少能探查到一半單元。 例如，若表長m=13，假設(shè)在第3個位置發(fā)生沖突，則后面探查的位置依次為4、7、12、6、2、0，即可以探查到一半單元。 若解決沖突時，探查到一半單元仍找不到一個空閑單元。則表明此哈希表太滿，需重新建立哈希表。,7.1.2 沖突的解決方法,2020/7/29,27,2鏈地址法 用鏈地址法解決沖突的方法是：把所有關(guān)鍵字為同義詞的記錄存儲在一個線性鏈表中，這個鏈表稱為同義詞鏈表。并將這些鏈表的表

16、頭指針放在數(shù)組中（下標從0到m-1）。這類似于圖中的鄰接表和樹中孩子鏈表的結(jié)構(gòu)。,7.1.2 沖突的解決方法,2020/7/29,28,鏈地址法查找分析,由于在各鏈表中的第一個元素的查找長度為l，第二個元素的查找長度為2，依此類推。因此，在等概率情況下成功的平均查找長度為： (1*5+2*2+3*l+4*1)9=169 雖然鏈地址法要多費一些存儲空間，但是徹底解決了“堆積”問題，大大提高了查找效率。,7.1.2 沖突的解決方法,2020/7/29,29,哈希法是利用關(guān)鍵字進行計算后直接求出存儲地址的。當哈希函數(shù)能得到均勻的地址分布時，不需要進行任何比較就可以直接找到所要查的記錄。但實際上不可能

17、完全避免沖突，因此查找時還需要進行探測比較。 在哈希表中，雖然沖突很難避免，但發(fā)生沖突的可能性卻有大有小。這主要與三個因素有關(guān)。 第一:與裝填因子有關(guān) 所謂裝填因子是指哈希表中己存入的元素個數(shù)n與哈希表的大小m的比值，即 =n/m。 當 越小時，發(fā)生沖突的可能性越小，越大（最大為1）時，發(fā)生沖突的可能性就越大。,7.1.3 哈希表的查找及性能分析,2020/7/29,30,第二:與所構(gòu)造的哈希函數(shù)有關(guān) 若哈希函數(shù)選擇得當，就可使哈希地址盡可能均勻地分布在哈希地址空間上，從而減少沖突的發(fā)生。否則，若哈希函數(shù)選擇不當，就可能使哈希地址集中于某些區(qū)域，從而加大沖突的發(fā)生。 第三:與解決沖突的哈希沖突

18、函數(shù)有關(guān) 哈希沖突函數(shù)選擇的好壞也將減少或增加發(fā)生沖突的可能性。,7.1.3 哈希表的查找及性能分析,2020/7/29,31,有關(guān)哈希表的算法,1基于開放地址法的哈希表的建立 #define NIL -1 #define M 997 /表長度 typedef int KeyType; typedef struct node /哈希表結(jié)點類型 KeyType key; /其他數(shù)據(jù)域 HashType; 用除余法求K的哈希地址的函數(shù)h int h(KeyType K) return K%M; ,2020/7/29,32,Increment是求增量序列的函數(shù),它依賴于解決沖突的方法 int Inc

19、rement(int i) /用線性探查法求第i個增量di return i; 求在哈希表T0.M-1中第i次探查的哈希地址hi，0iM-1 int Hash(KeyType k,int i) return (h(k)+Increment(i)%M; 在哈希表T0.M-1中查找K,成功時返回1。失敗有兩種情況：找到一個開放址時返回0;表滿未找到時返回-1 int HashSearch(HashType T,KeyType K,int *pos) int i=0; /記錄探查次數(shù) do *pos=Hash(K,i); /求探查地址hi if(T*pos.key=K) return 1; if(T

20、*pos.key=NIL) return 0; /查找到空結(jié)點返回 while(+iM); /最多做M次探查 return -1; /表滿且未找到時,查找失敗,2020/7/29,33,將新結(jié)點newnode插入哈希表T0.M-1中 void Hashlnsert(HashType T,HashType newnode) int pos,sign; sign=HashSearch(T,newnode.key, ,2020/7/29,34,根據(jù)A0.n-1中結(jié)點建立哈希表T0.M-1 void CreateHashTable(HashType T,HashType A,int n) if(nM) /用開放定址法處理沖突時，裝填因子須不大于1 printf(裝填因子須不大于1); exit(0); for(i=0;iM;i+) Ti.key=NIL; /將各關(guān)鍵字清空，使地址i為開放地址 for(i=0;in;i+) /依次將A0.n-1插入到哈希表T0.m-1中 Hashlnsert(T,Ai); ,2020/7/29,35,2基于鏈地址法的哈希表的建立 #define M 997 typedef int KeyType; typedef struct chain KeyType key; struct chain *next; ChainType; int h(KeyT