使用线性探测插入哈希表

Question

我在研究hackerearth上的哈希表，在那里我遇到了用线性探测实现哈希表的代码。我对这段代码有两个疑问：-

1）为什么他们声明大小为21（而不是大小为20）的hashTable最多容纳20个元素？

2） 在Insert函数中，当循环无限运行时，如果在连续迭代之后，索引的值变为索引的初始值，不是吗？

链接至黑客主页：-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循环有时会继续搜索无穷大。

要点2：
不！虽然循环不会无限运行，因为元素/字符串的数量最多为20个，给定的数组可以容纳21个元素/字符串。所以哈希表[索引]总是有一个索引保存“”/空字符串。

注：

在该算法中，字符串的存储位置由其哈希值决定。但是一些字符串可以具有相似的哈希值。这就是为什么它用循环方式搜索下一个未占用的索引。

当它搜索一个字符串时，无论它是否在哈希表中，它都会搜索到存储空字符串的索引，因为如果字符串在哈希表中，那么它将至少存储在该空位置。