如何在c中使用双重哈希进行搜索 [英] how to search using double hash in 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 ））; 
} 
返回值％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）; （$ * 
 $ b / *以避免冲突）* / 
 while（（* htable） - > table [hashVal] .username！= NULL）
 {
 / *双哈希处理* / 
 hashVal = hashVal + stepSize; 
 hashVal = hashVal％（* htable） - > size; 
} 
 
 return hashVal; 
 
 
 $ b int insert_to_hashtable（char * key，char * password，struct HashTable ** htable）
 {
 int pos = 0; 
 $ b $ / *找到插入新用户数据的索引* / 
 pos = Findindex（key，htable）; 
 
 //代码插入到相应的数据，如果这个空的
} 
  

我怎样才能编写代码来搜索用户名已经存在使用双哈希从散列表C？我认为遍历整个哈希表是不好的做法..是它吗？

解决方案

您的哈希表是一个固定的大小S，所以最多可以输入S个元素。

使用散列码H1和H2的双重散列的想法是：如果已经有位于H1的条目，则遍历散列宽度H2。 S的大小是素数。这意味着，任何步幅H2 <除H2 = 0之外，你最终会在所有的参赛者进入完整的圈子之前访问所有的参赛作品。

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

散列越多，效率越低关键的搜索将是。一种解决方案是跟踪元素的数量，并在超过75％的条目被占用时将散列大小调整为更大的大小。当然，新的大小也必须是主要的。

还要注意代码中的这些问题：您可能为步长生成散列值0，如果您的散列表已满，您搜索空插槽将无限循环。它也没有必要通过引用传递哈希表，因为你永远不会改变指针本身，只是它的结构成员。你甚至可以同时使键和 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; 
 
 $ / code> 

这段代码返回一个特殊值-1来表示没有任何值空表中的空插槽。

如果您想查找用户名，则使用相同的策略。在这里，您必须另外比较每个节点的密钥，因为不同的密钥可能共享相同的哈希码。

这个函数返回一个指向用户数据的指针（其类型我已经命名为 struct data ;如果用户不能显示关键字或 NULL 的哈希表struct被发现：
$ b $ $ $ $ $ $ $ $ $ $ $ c $ struct结构数据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; （;;）{
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];
}
}

返回NULL;
}


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

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?

解决方案

Your hashtable is of a fixed size S, so you can enter at most S elements.

The idea of the double hash with hash codes H1 and H2 is: If there is already an entry at position H1, traverse the hash width the stride H2. The size S is a prime. That means that with any stride H2 < S except H2 = 0, you will eventually visit all entries before coming full circle.

Of course, if you find an empty slot, you take it. In a sparsely populated hash, you usually have to go only a few steps from the original value to find an emty slot.

The more populated your hash gets, the less efficient the key search will be. One solution is to keep track of the number of elements and resize the hash to a bigger size when, say, more than 75% of entries are occupied. The new size must, of course, also be prime.

Also note these problems in your code: You might generate a hash value of 0 for the step size and if your hash table is full, your search for an empty slot will loop infinitely. It is also not necessary to pass the hash table by reference, because you never change the pointer itself, just its struct members. You can even make both key and htable const.

So:

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

This code returns a special value -1 to indicate that there aren't any empty slots in the hash table.

If you want to look up a username, you use the same strategy. Here, you must additionally compare the key for each node, because different keys may share the same hash code. If you find an empty slot, the entry is not in the table.

This function returns a pointer to the user data (whose type I've named struct data; you don't show thze definition of the hash table struct) associated with the key or NULL if the user can't be found:

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

Caveat: I haven't tested this code, but I hope that you understand the basic working.

这篇关于如何在c中使用双重哈希进行搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！