close
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 ^ 2 + 4 * 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)
全站熱搜
留言列表
電腦 (9)
