Вставка в хеш-таблицу с линейным зондированием

Question

Я изучал хеш-таблицы на hackerearth, где я столкнулся с этим кодом для реализации хэш-таблицы с линейным зондированием.У меня есть два сомнения в этом коде: -

1) Почему они объявляют hashTable размером 21 (а не размером 20) для хранения максимум 20 элементов?

2) В функции вставки,Разве цикл while работает бесконечно, если после последовательных итераций значение индекса становится таким же, как и начальное значение индекса?

ссылка на страницу hackerearth: - https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

Code:-

//declaring a hashTable to hold not more than 20 elements
 string hashTable[21];
    int hashTableSize = 21;

//Insert function

void insert(string s)
    {
        //Compute the index using the hash function
        int index = hashFunc(s);

/*Search for an unused slot and if the index will exceed the hashTableSize then roll back*/
        //  I have problem in this loop definition        
            while(hashTable[index] != "")   
            index = (index + 1) % hashTableSize;  
        hashTable[index] = s;
    }

Answer 1

Точка 1:
Это из-за функции поиска. Посмотрите на функцию поиска по ссылке, пожалуйста.

    void search(string s)
    {
        //Compute the index using the hash function
        int index = hashFunc(s);
         //Search for an unused slot and if the index will exceed the hashTableSize then roll back
        while(hashTable[index] != s and hashTable[index] != "")
            index = (index + 1) % hashTableSize;
        //Check if the element is present in the hash table
        if(hashTable[index] == s)
            cout << s << " is found!" << endl;
        else
            cout << s << " is not found!" << endl;
    }

Так что, если они использовали размер как 20, то цикл while в поиске иногда продолжается бесконечность, если строка запроса отсутствует в хеш-таблице и в каждом индексе hashTable есть строка.

Точка 2:
Нет! цикл while не будет выполняться бесконечно, потому что количество элементов / строк будет не более 20, а данный массив может содержать 21 элемент / строку. Поэтому всегда будет один индекс, в котором hashTable [index] содержит "" / пустую строку.

Примечание:

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

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