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?