1

I have a server to receive request from multiple client. I have done this with threads. I want to insert some user name and password to hash table. For that I am using double hash method. It was inserted successfully. But I want to know when user enter a user name, I need to search on hash table whether this username already present. But I can't do it now. I know the concept like using hashing. Get the index using hashfunction1 through username and use double hash like this. But how can I write that code ?

My code:

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 
}

How can I write code to search a username is already present using double hashing from hash table in C? I think traverse whole hash table is not good practice ..is it?

4

1 回答 1

2

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

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

当然，如果你找到一个空槽，你就拿下它。在一个稀疏的散列中，你通常只需要从原始值走几步就可以找到一个空槽。

您的哈希填充得越多，关键搜索的效率就越低。一种解决方案是跟踪元素的数量并将散列调整为更大的大小，例如，当超过 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;
}

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

于 2015-05-09T06:16:25.310 回答