c - C 中的哈希结构

Question

所以我正在尝试实现一个哈希表，该哈希表将对包含单词的结构进行哈希处理。

结构将与此类似:

#ifndef HASHTABLE_H
#def HASHTABLE_H

typedef int (*HashFunctionT) (char* string, int upperbound);

struct node_
{
    char * word;
    struct node * next;
}
typedef struct node_ * node;

struct nodehash_
{
    int size;
    struct node * hash[100];
}
typedef struct nodehash_ * nodehash;

Hashtable createHashTable();
void addtohash(node list, nodehash hash);
#endif

我希望散列函数像这样工作:

#include "hashtable.h"

int hashFunction(char *word, int hashTableSize)
{
    int length = strlen(word);
    int h = 0;
    int i;  
    for(i = 0; i<length; i++)
    {
        h=31 *h  + word[i];
    }
    return h % hashTableSize;
};

nodehash createHashtable()
{
    nodehash hashtable;    
    hashtable = malloc(sizeof(struct nodehash_));

    hashtable->size = 100;
    hashtable->hash = malloc(100 * sizeof (node));
    int i;   
    for (i = 0; i < hashtable->size; i++)
    {
            hashtable->table[i] = NULL;
    }
    return hashtable;
};

void addtohash(node list, nodehash hashtable)
{
    int nodehashnumber;
    nodehashnumber = hashfunction(list->word, hash->size);
    hashtable->hash[nodehasnumber] = list;
};

主要功能看起来像这样(假设已经创建并填充了节点结构的链表)。

int main()
{
    nodehash hashtable = createhashtable();
    node nodelist;
    /* here the nodelist would be created and filled and such and such*/
    while (nodelist->next != NULL)
    {
        addtohash(nodelist, hashtable);
    }
    return;
}

假设不会有冲突，因为每个要散列的单词都是不同的。

基本上，我想知道我是否遗漏了明显的明显错误或逻辑缺陷。

如有任何帮助，我们将不胜感激。

谢谢。

Answer 1

我没有详细阅读代码，但首先非常明显的是哈希表的大小，100。最好使用 prime number for the size of your hash tables以帮助避免碰撞。