HashTable With Double Ha sh - Стандартная реализация для метода Contains - PullRequest
Новая
       64

HashTable With Double Ha sh - Стандартная реализация для метода Contains

1 голос
/ 27 мая 2020

Я создаю таблицу ha sh с двойной реализацией ha sh на С ++. Я хочу проверить, находятся ли определенные ключевые слова внутри хеш-таблицы. Я делаю это, сначала хешируя слово, и если место уже занято, я постоянно повторяю sh со второй функцией в al oop, пока не найдет открытое место, например: 

int index = hash(word) % size;

if(arr[index] == "")
{
    arr[index] = word;
}
//index already contains something, rehash until find better spot
else
{
    int factor = 1;
    while(arr[index] != "")
    {
        index = (hash(word) + (factor*hash2(word))) % size;
        factor++;
    }
}

As Прямо сейчас будет al oop, который будет работать непрерывно, пока не найдет ключ внутри хэш-таблицы.

Мне трудно понять, как я могу реализовать метод contains. Моя проблема в том, что если этого слова НЕТ в таблице?

Прямо сейчас, единственная реализация, которую я могу придумать, - это удвоить ha sh определенное количество времени перед тем, как выполнить линейный зонд. Таким образом, я знаю, что конечный случай l oop при поиске ключа будет, когда я вернусь к исходному ha sh. Но мне кажется, что это слишком неэффективно. Есть ли другой способ сделать это?

...