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

Question

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

我的代码：

int HashFunc1 (char *key,int size)
{
    int i = 0,value = 0;

    for(i = 0 ; key[i] != '[=10=]'; 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] != '[=10=]'; 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 中的散列 table 的双重散列来编写代码来搜索已经存在的用户名？我认为遍历整个哈希 table 不是一个好习惯..是吗？

Answer 1

你的散列table是固定大小S，所以你最多可以输入S个元素。

哈希码H1和H2的双哈希的思路是：如果位置H1已经有条目，则遍历哈希宽度步长H2。大小 S 是素数。这意味着除了 H2 = 0 之外的任何步幅 H2 < S，您最终将在完整循环之前访问所有条目。

当然，如果你找到一个空位，你就拿下它。在稀疏填充的哈希中，您通常只需从原始值开始几步即可找到一个空槽。

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

还要注意您代码中的这些问题：您可能会为步长生成一个散列值 0，如果您的散列 table 已满，您对空槽的搜索将无限循环。也没有必要通过引用传递散列 table，因为您永远不会更改指针本身，只是它的结构成员。你甚至可以让 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;
}

此代码 returns 一个特殊值 -1 表示散列中没有任何空槽 table。

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

中

此函数 returns 指向用户数据的指针（我将其类型命名为 struct data；您没有显示散列 table 结构的定义）密钥或 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;
}

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

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

how to search using double hash in c

c

pointers

hash

hashtable

double-hashing