8.雜湊搜尋法(hash searching)
   將資料經過一個已經設計好的函數,將鍵值轉換成儲存位址,然後依搜尋鍵值所放的儲存位址,去尋找要搜尋的值。
   亦稱為散置搜尋法赫序搜尋法,計設好的函數稱為雜湊函數(hashing function)
   1.除法(division)
     h(x) = x % m
     h(x) 代表算術運算的餘數,或儲存位址。
      x     代表被搜尋的每一個鍵值。
      m    為除數,此數通常為質數且稍大於或等於儲存位址的數量。
 
      當位址中同時存放兩個或兩個以上的鍵值,這種現象稱為碰撞(collision)
      解決碰撞的方法有
          (1)循序法
          (2)開放位址法
          (3)亂數法
          (4)重複雜湊法
 
   2.中間數值平方法(mid-square)
      將鍵值平方後,取中間的數值做為儲存位址。
 
   3.折疊相加法(folding method)
      將鍵值分割幾個長度相等的部份,然後將這些部份相加起來,所得的總和視為位址桶
      (1)移位折疊相加法
          範例:
          鍵值 x = 123654798 ,m = 1000,x 折三疊三等分 ,F1 = 123 , F2 = 654 , F3 = 798
          ( F1(123) + F2(654) +F3(798) ) % 1000 = 575 , 位址桶(h(k)) = 575
      (2)邊界折疊相加法
           針對奇或偶數部份的數字翻轉過來,然後將所有數字相加。
          ( F1(321) + F2(654) +F3(897) ) % 1000 = 872 , 位址桶(h(k)) = 872
          ( F1(123) + F2(456) +F3(798) ) % 1000 = 377 , 位址桶(h(k)) = 377
 
   4.基數轉換法(radix transformation)
      將鍵值轉換成其他數的基數,然後取該數的某些位數當做鍵值的位址桶。
      鍵值358345,基數9與轉數10互質。
      3 * 9 ^ 5 + 5 * 9 ^ 4 + 8 * 9 ^ 3 + 3 * 9 ^ 24 * 9 ^ 1 + 5 * 9 ^ 0 = 216068
     取三位數當做鍵值的位址桶,h(k) = 216068 % 1000 = 068 。
 
   5.壓縮法(extraction)
     取鍵值部份的值當做鍵值的位址桶。
     範例:
     x = T123456789,拆成 1234 和 6789 ,取 12  和 89 組成一個鍵值的位址桶 h(k) = 1289 。
 
   6.數值分析法(digit analysis)
      分析所有鍵值,在鍵值中選擇適當的位數,以不會產生碰撞現象為原則,做為雜湊搜尋法的位址。
 

鍵值

位址

 

0

9

3

3

4

1

5

0

1

3

 

51

 

0

9

1

0

1

0

4

2

1

5

 

41

 

0

9

3

7

3

9

6

7

5

8

 

65

 

0

9

1

9

4

7

6

1

7

9

 

67

 

0

9

3

8

1

2

3

5

8

9

 

38

 
     一般而言,雜湊搜尋法是指一個位址桶只有一個槽(slot),每一個槽只能儲存一筆資料
     若一個位址桶放置兩筆以上的資料,除了產生碰撞外,同時也產生溢位(overflow)現象
     如果一個位址桶有數個槽,必頁所有槽被放滿資料,才會有溢位現象。
     載入因數(loading factor),是指雜湊表(hashing table)中存有資料的部份與整個雜湊表所佔的空間比例。
 
     處理溢位現象的方法:
         (1)線性探測法(linear probing),亦稱線性開放位址法(linear open addressing)
        (2)二次方探測法(quadratic probing)
        (3)重複雜湊法(rehashing)
        (4)鏈結串列法(linked list)
arrow
arrow
    全站熱搜

    Jiang Ying-Fu 發表在 痞客邦 留言(0) 人氣()