如何在c中使用双哈希进行搜索

我有一台服务器来接收来自多个客户端的请求。 我用线程完成了这个。 我想在哈希表中插入一些用户名和密码。 为此，我使用双哈希方法。 它已成功插入。 但是我想知道当用户输入用户名时，我需要在哈希表上搜索该用户名是否已经存在。 但我现在不能这样做。 我知道使用散列的概​​念。 使用hashfunction1通过用户名获取索引并使用像这样的双哈希。 但是我该如何编写该代码呢？

我的代码：

int HashFunc1 (char *key,int size) { int i = 0,value = 0; for(i = 0 ; key[i] != '\0'; i++) { value += ( key[i] + ( i + 1 ) ); } return value % size; } int HashFunc2 (char *key,int size) { int i = 0,value = 0; for(i = 0; key[i] != '\0'; i++) { value += ( key[i] + ( i + 1 ) ); } return (value * size - 1) % size; } int Findindex(char *key,struct HashTable **htable) { int hashVal = 0, stepSize = 0; hashVal = HashFunc1(key, (*htable)->size); stepSize= HashFunc2(key, (*htable)->size); /*to avoid collisions)*/ while ( (*htable)->table[hashVal].username != NULL) { /*double hahsing process*/ hashVal = hashVal + stepSize; hashVal = hashVal % (*htable)->size; } return hashVal; } int insert_to_hashtable(char *key,char *password,struct HashTable **htable) { int pos = 0; /*find the index to insert new user datas*/ pos = Findindex(key,htable); //code to insert to coresponding data if this empty } 

如何使用C中哈希表的双哈希来编写用于搜索用户名的代码？ 我觉得遍历整个哈希表不是很好的做法..是吗？

Answer 1

您的哈希表具有固定大小S，因此您最多可以输入S个元素。

具有哈希码H1和H2的双重哈希的想法是：如果在位置H1处已经存在条目，则遍历步幅H2的哈希宽度。 大小S是素数。 这意味着除了H2 = 0之外任何步幅H2

当然，如果你找到一个空槽，你可以拿它。 在稀疏填充的散列中，您通常只需要从原始值开始几步即可找到一个emty插槽。

您的哈希填充越多，密钥搜索的效率就越低。 一种解决方案是跟踪元素的数量并将哈希值调整为更大的大小，例如，超过75％的条目被占用。 当然，新尺寸也必须是最重要的。

还要注意代码中的这些问题：您可能会为步长生成哈希值0，如果哈希表已满，则搜索空槽将无限循环。 也没有必要通过引用传递哈希表，因为您永远不会更改指针本身，只更改其结构成员。 你甚至可以同时制作key和htable const 。

所以：

 int Findindex(const char *key, const struct HashTable *htable) { int hashVal, stepSize, startVal; hashVal = HashFunc1(key, htable->size); if (htable->table[hashVal].username == NULL) return hashVal; startVal = hashVal; stepSize = HashFunc2(key, (*htable)->size - 1) + 1; do { hashVal = (hashVal + stepSize) % htable->size; if (hashVal == startVal) return -1; } while (htable->table[hashVal].username); return hashVal; } 

此代码返回特殊值-1，表示哈希表中没有任何空槽。

如果要查找用户名，请使用相同的策略。 在这里，您还必须比较每个节点的密钥，因为不同的密钥可能共享相同的哈希代码。 如果找到空槽，则该条目不在表中。

此函数返回一个指向用户数据的指针（其类型我已命名为struct data ;您不显示与该键相关联的散列表结构的定义），如果找不到该用户，则返回NULL ：

 struct data *FindKey(const char *key, const struct HashTable *htable) { int hashVal, stepSize, startVal; hashVal = HashFunc1(key, htable->size); if (htable->table[hashVal].username == NULL) return NULL; if (strcmp(htable->table[hashval].username, key) == 0) { return &htable->table[hashVal]; } startVal = hashVal; stepSize = HashFunc2(key, (*htable)->size - 1) + 1; for(;;) { hashVal = (hashVal + stepSize) % htable->size; if (hashVal == startVal) return NULL; if (htable->table[hashVal].username == NULL) return NULL; if (strcmp(htable->table[hashval].username, key) == 0) { return &htable->table[hashVal]; } } return NULL; } 

警告：我没有测试过这段代码，但我希望你能理解基本的工作原理。