Как искать, используя двойной хэш в c

Question

У меня есть сервер для получения запроса от нескольких клиентов. Я сделал это с потоками. Я хочу вставить имя пользователя и пароль в хэш-таблицу. Для этого я использую метод двойного хеширования. Он был вставлен успешно. Но я хочу знать, когда пользователь вводит имя пользователя, мне нужно найти в хэш-таблице, присутствует ли это имя пользователя. Но я не могу сделать это сейчас. Я знаю концепцию, как использование хеширования. Получить индекс с помощью 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

Конечно, если вы найдете пустое место, вы берете его. В малонаселенной хэш-памяти вам обычно нужно пройти всего несколько шагов от исходного значения, чтобы найти пустую ячейку.

Чем больше заполнен ваш хэш, тем менее эффективным будет поиск ключа. Одним из решений является отслеживание количества элементов и изменение размера хеша до большего размера, когда, скажем, занято более 75% записей. Новый размер, конечно, также должен быть простым.

Также обратите внимание на следующие проблемы в вашем коде: вы можете сгенерировать хеш-значение 0 для размера шага, и если ваша хеш-таблица заполнена, ваш поиск пустого слота зациклится бесконечно. Также нет необходимости передавать хеш-таблицу по ссылке, потому что вы никогда не меняете сам указатель, а только его элементы структуры. Вы даже можете сделать оба key а также htableconst,

Так:

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

Предостережение: я не тестировал этот код, но надеюсь, что вы понимаете основную работу.