數(shù)據(jù)結(jié)構(gòu)-計中文課件

1、1 第8章 哈希表查找表 是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。2對查找表經(jīng)常進(jìn)行的操作：4) 從查找表中刪去某個數(shù)據(jù)元素。1) 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2) 檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3) 在查找表中插入一個數(shù)據(jù)元素；3靜態(tài)查找表 僅作查詢和檢索操作的查找表動態(tài)查找表 有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入查找表；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。4查找 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）； 若查找表中存在這樣一個記錄，則稱“查找成功”，查找結(jié)果：給出整個記錄

2、的信息，或指示該記錄在查找表中的位置； 否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”5關(guān)鍵字 是根據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）； 若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”； 若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。6如何查找？ 然而，查找表本身是一種很松散的結(jié)構(gòu)，因此，為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。 取決于查找表的結(jié)構(gòu)。如何查找？ Array（數(shù)組存儲） :順序查找法 O ( n )二分法查找 O ( log n ) 前提：按關(guān)鍵字有序，

3、排序O(nlogn)。 Linked List（鏈表） :順序查找法 O ( n ) Binary Search Tree（二叉搜索樹）-1維數(shù)據(jù):Insertion O( log n )Deletion O( log n )Find O( log n ) KD-Tree-K維數(shù)據(jù):Insertion O( log n )Deletion O( log n )Find O( log n )8一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法四、哈希表的查找主要內(nèi)容9 一、哈希表是什么？以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)，有一個共同點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系

4、，因此，查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個數(shù)。10 用這類方法表示的查找表，其平均查找長度都不為零，不同表示方法的差別僅在于：和給定值進(jìn)行比較的關(guān)鍵字的順序不同。11 對于頻繁使用的查找表，希望ASL=0。只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，也就是說，記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。12 例如： 為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為xx000 xx999（前兩位為年份）。則可以下標(biāo)為000999的順序表表示之。由于關(guān)鍵字和記錄在表中的序號相同，則不需要經(jīng)過比較即可確定待查關(guān)鍵字。13但是，

5、對于動態(tài)查找表而言：1) 表長不確定；2) 在設(shè)計查找表時，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。 因此，一般情況，需建立一個函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。14 簡單地說，哈希表是基于哈希函數(shù)建立的一種查找表。Hash Tables01 s1 ht 0 ht 1 ht b1 b bucketss slots For each identifier x, we define a hash function f ( x ) = position of x in ht (i.e. the index of the bucke

6、t that contains x ) T := total number of distinct possible values for x n := total number of identifiers in ht identifier density := n / T loading density := n / (s b) A collision occurs when we hash two nonidentical identifiers into the same bucket, i.e. f ( i1 ) = f ( i2 ) when i1 i2 . An overflow

7、 occurs when we hash a new identifier into a full bucket.Collision and overflow happen simultaneously if s = 1.Example Mapping n = 10 C library functions into a hash table ht with b = 26 buckets and s = 2.Slot 1Slot 0012345625Loading density = ?10 / 52 = 0.19To map the letters a z to 0 25, we may de

8、fine f ( x ) = ? x 0 aacosacosdefinedefinefloatfloatexpexpcharcharatanatanceilceilfloorfloorclockctimeWithout overflow, Tsearch = Tinsert = Tdelete = O( 1 )17從這個例子可見，1) 哈希函數(shù)是一個映象，即： 將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可；182) 由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：keykey2，而f(key1)=f(key2)并且，改

9、進(jìn)哈希函數(shù)只能減少沖突，而不能避免沖突。 因此，在設(shè)計哈希函數(shù)時，一方面要考慮選擇一個“好”的哈希函數(shù)；另一方面要選擇一種處理沖突的方法。19 二、哈希函數(shù)的構(gòu)造方法 對數(shù)字的關(guān)鍵字可有下列哈希函數(shù)的構(gòu)造方法， 若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。20 取關(guān)鍵字的某個線性函數(shù)值為哈希地址。即： H(key)=key或H(key) akey+b直接定址法21數(shù)字分析法Example Given size of a hash table = 100010.x1 = 1 2 3 4 5 6 10 x2 = 1 4 5 3 1 8 10 x3 = 1 2 2 1 6 2 10 x4 = 1 4

10、 9 2 8 0 10 The range of address is 0, 999 f ( x ) = x2100 + x410 + x522平方取中法Given x, first compute x2. Then fm = r bits in the middle of x2.Example A x = 0100 x2 = 0010000 fm(A) = 010J x = 1200 x2 = 1440000 fm(J) = 440Q3 x = 2163 x2 = 4745651 fm(Q3) = 745Note:中間的各位通常與關(guān)鍵字的所有各位相關(guān)。因此，不同的關(guān)鍵字產(chǎn)生不同的哈希地址的概

11、率高。 (2) 所取中間位的數(shù)目依賴于表的長度，如果取r位，則表長應(yīng)為2r。23折疊法Example x = 6 2 3 2 0 3 2 4 1 1 1 2 2 0移位疊加6 2 32 0 32 4 11 1 2 2 01 1 9 9 fF ( x ) = 1 9 9間界疊加6 2 32 0 32 4 11 1 2 2 03 0 22 1 11 3 9 7 fF ( x ) = 3 9 724除留余數(shù)法 fD = x % M. Hence the table size is M.關(guān)鍵是M的選擇Suggestion: 一般情況下，可以選M為質(zhì)數(shù)或不包含小于20的質(zhì)因素的合數(shù)。25 實際造表時，采

12、用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況（包括關(guān)鍵字的范圍和形態(tài)），總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。26 三、處理沖突的方法 處理沖突的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。271、開放定址法 為產(chǎn)生沖突的地址H(key)求得一個地址序列： H0,H1,H2,.,Hs 1sm-1其中H0=H(key) Hi=(H(key)+di)mod m i=1,2,.s，m為哈希表的表長28增量di有三種取法： 1) 線性探測再散列 di=ci 最簡單的情況 c=12) 二次探測再散列 di=12,-12,22,-22,.,或 di=12,22,32,.,3) 隨機(jī)探測再

13、散列 di是一組偽隨機(jī)數(shù)列或者di=iH(key)292.鏈地址法 將所有哈希地址相同的記錄都鏈接在同一鏈表中。30四、哈希表的查找 查找過程和造表過程一致。假設(shè)采用開放定址處理沖空，則查找過程為：對于給定值K，計算哈希地址HiH(K) 若ri.key=NULLKEY則查找不成功 若ri.key=K 則查找成功 否則，求下一地址Hi，直至ri.key=NULLKEY(查找不成功)或ri.key=K(查找成功)為止。31決定哈希表查找的ASL的因素：1) 選用的哈希函數(shù)；2) 選用的處理沖突的方法；3) 哈希表飽和的程度，裝載因子=n/m值的大小。 一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”的，則在討論ASL時，可以不考慮它的