在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;
}

假设没有碰撞，因为要哈希的每个单词都不同。基本上，我想知道我是否错过了任何明显的错误或逻辑缺陷。非常感谢您的任何帮助。谢谢。

- gfppaste

---

这个是否适合在http://codereview.stackexchange.com/上进行更好的审查？ - David Heffernan

哦，我甚至不知道那个存在...谢谢你让我知道！ - gfppaste

你不能仅仅因为每个单词不同就假设没有碰撞。你的哈希函数可能会为多个不同的输入产生相同的输出。 - TJD

另外，如果你假设没有碰撞的话，为什么还要使用带有下一个指针的节点结构体？你可以只使用 char* 数组来处理。 - TJD

所以这都是实现LRU缓存的一个更大项目的一部分...基本上，我们会得到一个.txt文件作为输入，然后我们需要对文件进行标记化，并使用比O(n^2)时间更好的方法搜索文件（因此基本上，线性搜索不可能，我们被鼓励使用哈希表）。 LRU缓存用于包含令牌，并且将是动态的：也就是说，用户指定自己的缓存大小。 - gfppaste

Answer 1

我没有详细阅读代码，但很明显的第一件事是哈希表的大小，100。为了避免冲突，最好使用质数作为哈希表的大小。

- sarnold

---

那是因为它是一个在多个地方出现的魔法数字。 - Fred Larson

@FredLarson：难怪它如此快速地脱颖而出 :) -- gfppaste，一定要用变量或#define替换硬编码的“100”，这样你就可以更轻松地在未来改变表格的大小。 - sarnold

我认为质数在这种情况下并不一定表现更好。如果有足够的分散（K＆R哈希在城里不是最好的选择，但对于合理长度的字符串来说还是可以的），模100将不会比模101差得多。 - wildplasser

鉴于显然没有输入冲突的可能性，这也无关紧要。 :) - sarnold

Answer 2

你似乎有分号的问题：

struct node_
{
    char * word;
    struct node * next;
}   /* <<-- HERE */
typedef struct node_ * node;

但是：

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;
}; /* <<-- NOT here */

此外，我的建议是尽可能使用许多无符号类型：对于哈希值（负操作数如何进行模除运算？）以及大小和索引。

经验法则是：如果它不能为负数，则应使用无符号类型。

- wildplasser