Confusion about linear probe method based Open Addressing in hashtables?

Question

Suppose array index according to hashing function for string "temp" is 155 and location 155 is pre-occupied then location 156 is tried. Suppose location 156 is available, so this entry is saved in location 156 instead of 155. Later I find another string "another_temp", which maps to location 156. Again this is saved in next available location 157.

The question is : Later if I want to find out location of "another_temp", how I would know that it is 157 not 156, even though hash function returned 156?

Thanks.

Answer 1

You need to compare the key, not just the hash code. In a hash table, you anyway need to store the key ("temp" and "another_temp" in your case). It's not enough to just store and compare the hash value, because hash values are not unique.

There are a few problems with open addressing. One is: what to do after deleting an entry? Usually you store a special "deleted" marker. Another problem is: if there is a collision, should you increment the hash code? You will find more details in Wikipedia.