[C 範例代碼] 尋找演算法 : 哈希查找

前言 :
編程實現哈希查找, 要求如下 :
已知哈希表長度為11, 哈希函數為 H(key) = key%11, 隨機產生散列的小於50的 8 個元素, 同時採用線性探測再散列的方法處理衝突, 接著輸入要查找的數據, 無論找到與否都提示訊息.

技術要點 :
哈希函數的構造方法通常有五種, 分別是數字分析法, 平分取中法, 分段疊加, 偽隨機數法和餘數法, 這裡餘數法比較常用. 因為本例中已給出哈希函數所以不必構造, 直接使用題中給的哈希函數來運算便可. 雖然通過構造好的哈希函數可以減少衝突, 但是衝突是不可避免的, 所以就產生了相應處理哈希衝突常用的四種方法 :

1. 開放定址法 (線性探測再散列, 二次探測再散列)
2. 鏈地址法
3. 在哈希法
4. 建立公共溢出區

開放定址法中的線性探測再散列比較常用, 該方法事衝突發生時, 順序查看表中下一單元, 直到找到一個空單元或是該哈希表已滿.

範例代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4. #include   
5.   
6. using namespace std;  
7. #define MAX_HASH_SIZE 11  
8. #define N 8  
9. int hashTable[MAX_HASH_SIZE];  
10.   
11. int _func(int value) {  
12.     return value%MAX_HASH_SIZE;  
13. }  
14.   
15. int _search(int key) {  
16.     int t, pos;  
17.     pos = _func(key);  
18.     t = pos;  
19.     while(hashTable[t]!=key && hashTable[t]!=-1) {  
20.         t = (t+1) % MAX_HASH_SIZE;  
21.         if(pos==t) {  
22.             return -1;  
23.         }  
24.     }  
25.     if(hashTable[t]==-1)  
26.         return -1;  
27.     else  
28.         return t;  // 找到目標值  
29. }  
30.   
31. void _createHash(int key) {  
32.     int pos,t;  
33.     pos = _func(key); // 哈希函數確定元素位置  
34.     t = pos;  
35.     while(hashTable[t]!=-1) { // 如果該位置有元素存在則進行線性探測再散列  
36.         t = (t+1) % MAX_HASH_SIZE;  
37.         if(pos == t) { // 如果衝突處理後確定位置與原來位置相同說明哈希表已滿  
38.             printf("Hash Table is full.\n");  
39.             return;  
40.         }  
41.     }  
42.     hashTable[t] = key;  
43. }  
44.   
45. void main() {  
46.     int flag[50] = {0};  
47.     for(int i=0; i
48.         hashTable[i] = -1;  
49.     srand((unsigned long)time(0));  
50.     int j=0,t;  
51.     while(j!=N) {  
52.         t = rand() % 50;  
53.         if(flag[t] == 0) {  
54.             _createHash(t);  
55.             printf("%2d: ", t);  
56.             for(int i=0; i
57.                 printf("(%2d) ", hashTable[i]);  
58.             printf("\n");             
59.             flag[t] = 1;  
60.             j++;  
61.         }         
62.     }  
63.     t=0;  
64.     while(t>=0){  
65.         printf("Please input number which you want to search: ");  
66.         cin >> t;  
67.         if(t>=0 && t<50) {  
68.             int i = _search(t);  
69.             if(i>=0) {  
70.                 printf("Success!(%d)\n", i);  
71.             } else {  
72.                 printf("Sorry, not found!\n");  
73.             }  
74.         }  
75.     }  
76. }  

執行結果 :

16: (-1) (-1) (-1) (-1) (-1) (16) (-1) (-1) (-1) (-1) (-1)
3: (-1) (-1) (-1) ( 3) (-1) (16) (-1) (-1) (-1) (-1) (-1)
46: (-1) (-1) (46) ( 3) (-1) (16) (-1) (-1) (-1) (-1) (-1)
12: (-1) (12) (46) ( 3) (-1) (16) (-1) (-1) (-1) (-1) (-1)
13: (-1) (12) (46) ( 3) (13) (16) (-1) (-1) (-1) (-1) (-1)
47: (-1) (12) (46) ( 3) (13) (16) (47) (-1) (-1) (-1) (-1)
41: (-1) (12) (46) ( 3) (13) (16) (47) (-1) (41) (-1) (-1)
38: (-1) (12) (46) ( 3) (13) (16) (47) (38) (41) (-1) (-1)
Please input number which you want to search: 2 <輸入搜尋數字>
Sorry, not found!
Please input number which you want to search: 16
Success!(5) <出現在第5個slot>

補充說明 :
* Wiki : HashTable

In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys, (e.g., a person's name) to their associated values (e.g., their telephone number). The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.
Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after creation). Most hash table designs assume that hash collisions—the situation where different keys happen to have the same hash value—are normal occurrences and must be accommodated in some way.

This message was edited 2 times. Last update was at 04/06/2010 09:49:41