Description

使用線性探測法（Linear?Probing）可以解決哈希中的沖突問題，其基本思想是：設哈希函數為h(key)?=d，并且假定哈希的存儲結構是循環數組，則當沖突發生時，繼續探測d+1,d+2,…，直到沖突得到解決。

例如，現有關鍵碼集為{47，7，29，11，16，92，22，8，3}，設哈希表表長為m=11，哈希函數為Hash(key)=key?mod?11，采用線性探測法處理沖突。

建哈希表如下：

0	1	2	3	4	5	6	7	8	9	10
11	22	?	47	92	16	3	7	29	8	?

現在給定哈希函數為Hash(key)=key?mod?m，要求按照上述規則，使用線性探測法處理沖突。要求建立起相應哈希表，并按要求打印。

Input

僅有一個測試用例，第1行為整數n與m（1<=?n,?m<=10,000），n代表key的總數，m代表哈希表的長度，并且令哈希函數為Hash(key)=key?mod?m。

接下來n行，每行一個整數，代表一個key，其中key與key兩兩不相同（0<=key<=10,000）。

Output

?

輸出建立好的hash表，比如下表：

0	1	2	3	4	5	6	7	8	9	10
11	22	?	47	92	16	3	7	29	8	?

應輸出

0#11

1#22

2#NULL

3#47

4#92

5#16

6#3

7#7

8#29

9#8

10#NULL

?

Sample Input 3 5 1 5 6 Sample Output 0#5 1#1 2#6 3#NULL 4#NULL

直接上代碼： 1 #include <iostream> 2 using namespace std; 3 4 int hash(int key, int len) { 5 return (key % len); 6 } 7 8 int hashTable[10000]; 9 10 void initializeHash(int size, int lenOfHash) { 11 int temp; 12 13 for (int i = 0; i < size; i++) { 14 cin >> temp; 15 16 if (hashTable[hash(temp, lenOfHash)] == -1) { 17 hashTable[hash(temp, lenOfHash)] = temp; 18 } else { 19 int pos = hash(temp, lenOfHash); 20 while (hashTable[pos] != -1) { 21 pos = (pos + 1) % lenOfHash; 22 } 23 24 hashTable[pos] = temp; 25 } 26 } 27 } 28 29 void print(int lenOfHash) { 30 for (int i = 0; i < lenOfHash; i++) { 31 if (hashTable[i] != -1) { 32 cout << i << "#" << hashTable[i] << endl; 33 } else { 34 cout << i << "#NULL" << endl; 35 } 36 } 37 } 38 39 int main() 40 { 41 int numOfKey, lenOfHash; 42 43 cin >> numOfKey; 44 cin >> lenOfHash; 45 46 for (int i = 0; i < lenOfHash; i++) { 47 hashTable[i] = -1; 48 } 49 50 initializeHash(numOfKey, lenOfHash); 51 52 print(lenOfHash); 53 54 return 0; 55 }

?

轉載于:https://www.cnblogs.com/IT-nerd/p/3462370.html

總結

以上是生活随笔為你收集整理的简单哈希1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。