C smdb散列值％tableSize重复计算为相同的值？ （用不同的输入。）

Question

试图使用smdb算法做一个哈希表（因为我听到这是明智的，不要试图写我自己的。）我敢肯定，我是完全错误的。我提到我是C新手吗？

我的hashFunction（）％size在第一次调用时返回一个数字，如35，然后在第二次调用，第三次调用，第四次调用时返回65，并返回65。我只是将这些数字用作任意的例子。试图用调试器来弄明白后，我发现散列函数将返回不同的多头，但它们使用相同的最后2个数字全部结束......像这样......

4460735 4526335 4591935

所以我想这是为什么当我散列％大小时，每次都会得到相同的输出结果。这违背了均匀分布键的想法，对吧？

请随便找我。我知道SO上的野蛮人可以如何。

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

typedef struct node 
{ 
    char* str; 
    struct node* next; 
} 
node; 

void insertItem(char* number, node** list); 
unsigned long hashFunction(char* str); 

int main(void) 
{ 

    int size = 100; 
    int index = 0; 

    node* buckets[size]; 

    for (int i = 0; i < size; i++) 
    { 
     char c = i + 'A'; 
     index = hashFunction(&c) % size; 
     insertItem(&c, &buckets[index]); 
    } 

} 

void insertItem(char* str, node** list) 
{ 
    node* newItem = malloc(sizeof(node)); 
    newItem->str = str; 
    newItem->next = *list; 
    *list = newItem; 
} 

unsigned long hashFunction(char* str) 
{ 
    //sdbm hash function adapted (incorrectly?) from here: http://www.cse.yorku.ca/~oz/hash.html 
    unsigned long hash = 0; 
    int c; 

    while ((c = *str++)) 
     hash = c + (hash << 6) + (hash << 16) - hash; 

    return hash; 
} 

Answer 1

问题是你对字符而不是字符串进行测试。

如果你用真正的字符串提供算法，那么你会得到更重要的东西。例如，下面的更改代码：

char mystring[] = "Any string will do !"; 

for (int i = 0; i < size; i++) 
{ 
    mystring[0] = i; // simple hack to change the string a bit, well ... a byte ;) 
    index = hashFunction(mystring) % size; 
    insertItem(mystring, &buckets[index]); 
} 

如果打印index你会得到一个更合适的指标。

编辑：

真正的问题是，你的散列函数旨在帮助C字符串作为参数（一个char *指向必须是空值终止的缓冲区，即与'\0'结束）。在给出单个字符的地址时，第一个解除引用是可以的，但是使用指向非真实分配对象的下一个地址（在++之后）是undefined behavior。

积分：见moooeeeep answer，和评论。

Answer 2

散列函数需要一个指向以空字符结尾的字符串作为输入参数的指针。您将指针传递给单个字符。该函数然后迭代无效内存，直到它到达一个随机空字节。

char c = i + 'A'; 
index = hashFunction(&c) % size; 

您需要将指针传递给字符串。例如：

char arr[] = "Hello World"; 
index = hashFunction(arr) % size; 

也可以考虑设置你的size为增加随机性素数。进一步阅读：

• Why should hash functions use a prime number modulus?
• Hash table: why size should be prime?