Inserting in hash table with linear probing

Question

I was studying about hash tables on hackerearth , where I encounter this code for Implementing the Hash Table with Linear Probing. I have two doubts in this code:-

1) Why they declare hashTable of size 21 (and not of size 20) to hold maximum of 20 elements ?

2) In Insert function , Isn't while loop run infinitly , if after successive iterations value of index become same of the initial value of Index ?

link to hackerearth page:-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;
    }

May be, question 2 is just the answer of question 1. (One more element as necessary for storing max. number of elements to ensure an element which must finish the otherwise possibly endless loop.) Otherwise, I don't see a reason as well. (The authors should have mentioned this (or another) reason, IMHO.) — Scheff's Cat, Jul 09 '19 at 09:21

mahbubcseju · Answer 1 · 2019-07-09T12:08:40.640

Point 1:
It's because of the search function. Look at the search function of the link please.

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

So if they used the size as 20, then the while loop in search sometimes continue for infinity if the query string is not in the hash table and there is a string in every index of hashTable.

Point 2:
No! the while loop will not run infinitely because the number of element/string will be at most 20 and the given array can hold 21 elements/string . So there will be always one index where hashTable[index] holds ""/empty string.

Note:

In this algorithm , Where the string will be stored is decided from its hash value. But some string can have similar hash value. That's why it searched for the next unoccupied index with circular fashion.

When it search for a string whether it is in the hash table or not it search upto the index where empty string is stored because if the string is on the hashtable then it will stored at least in that empty position.

Inserting in hash table with linear probing

1 Answers1