我的散列函数有什么问题？

我想创建一个哈希表。这里是我的代码：我的散列函数有什么问题？

#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

我的散列函数有什么问题？

回答

相关问题