2

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

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

2) 在 Insert 函数中，如果在连续迭代后 index 的值与 Index 的初始值相同，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;
    }
4

1 回答 1

0

第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点：
不！while 循环不会无限运行，因为元素/字符串的数量最多为 20，并且给定的数组可以容纳 21 个元素/字符串。所以总会有一个索引，其中 hashTable[index] 保存“”/空字符串。

笔记：

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

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

于 2019-07-09T11:58:45.133 回答