我的散列函數有什麼問題？

我想創建一個哈希表。這裏是我的代碼：我的散列函數有什麼問題？

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

#define N 19 
#define c1 3 
#define c2 5 
#define m 3000 
int efort; 
int h_table[N]; 

int h(int k, int i) 
{ 
    return (k + i*c1 + i*i*c2) % N; 
} 
void init() 
{ 
    for (int i = 0; i < N; i++) 
     h_table[i] = -1; 
} 
void insert(int k) 
{ 
    int position, i; 
    i = 0; 
    do 
    { 
     position = h(k, i); 
     printf("\n Position %d \n", position); 
     if (h_table[position] == -1) 
     {  
      h_table[position] = k; 
      printf("Inserted :elem %d at %d \n", h_table[position], position); 
      break; 
     } 
     else 
     { 
      i += 1; 
     } 
    } while (i != N); 
} 
void print(int n) 
{ 
    printf("\nTable content: \n"); 
    for (int i = 0; i < n; i++) 
    { 
     printf("%d ", h_table[i]); 
    } 

} 


void test() 
{ 
    int a[100]; 
    int b[100]; 
    init(); 
    memset(b, -1, 100); 
    srand(time(NULL)); 
    for (int i = 0; i < N; i++) 
    { 
     a[i] = rand() % (3000 + 1 - 2000) + 2000; 
    } 
    for (int i = 0; i < N ; i++) 
    { 
     insert(a[i]); 
    } 
    print(N); 
} 
int main() 
{ 
    test(); 
    return 0; 
}

哈希（「H」）的功能和「插入」功能是由帶「算法導論」一書（Cormen）。我不知道什麼是與H功能發生或插入功能。有時它會完全填充我的數組，但有時它不會。這意味着它不起作用。我究竟做錯了什麼？

來源

2017-04-26 SomeoneNew

你用調試器通過你的代碼？ – ryyker

請注意，memset（b，-1，100）不會將所有的b []設置爲-1。 – chux

不要停止在'while（i！= N）'，繼續尋找。也許在'i> = N/2'之後，爲下一個空閒單元線性查找。 – chux

總之，你是生產用於position往往不足以防止只N嘗試之後被填充h_table[]重複值...

僞隨機數生成器不能保證產生一組獨一無二的數字，保證您的h(...)函數不會產生互斥的一組位置值。在生成全部19個職位之前，您可能會生成足夠多的相同職位，導致用完循環。問題在你有可能獲得未使用的頭寸的價值之前，平均需要多少次調用h(...)？應該回答。這可能有助於指導您解決問題。

作爲一個實驗，我增加了循環索引從N在所有100但h(...)功能（以便不溢出h_table[]）。正如預期的那樣，前5個職位立即填補。下一個嘗試3次後再填充。接下來的10次嘗試，等等，直到100次嘗試結束，還有一些不成文的位置。
在下一次運行中，所有表格位置都已填滿。

2可能的解決方案：
1）修改哈希以提高唯一值的概率。
2）增加迭代來填充h_table

來源

2017-04-26 19:18:39 ryyker

good_hash_function() % N一個可重演N重新散列。一個好的散列看起來好像是隨機即使它是確定性的。所以在N嘗試它可能不循環所有的數組元素。

經過多次嘗試後找不到自由數組元素，比如說N/3次嘗試，推薦使用不同的方法。只需查找下一個免費元素。

來源

2017-04-26 19:18:53 chux

我的散列函數有什麼問題？

回答

相關問題