Hash Table Linear Probing

Question

I'm making a hash table with one String array single dimension and a 2 dimensional int array. I'm using linear probing for my collision detection and was really steaming through this program when I realized if a collision is detected the word's hashCode would no longer be the index. How would I go about saving that index for later use?

Answer 1

That is one of the disadvantages of linear probing. If there is a collision you need to move on to the next available index but this does not insure that the next element will be the one you are looking for thus resulting in your complexity to be O(n) and not the expected O(1). You could maybe consider having a bucket for each of your indexes. If if there is a collision you will still have the right index to go, you will just have to iterate through a LinkedList for instance to find the value you are looking for.

Linear probing is more for devices with limited storage. If you are writing your program on a desktop I would suggest the bucket approach or the official term Separate Chaining. Hope this helps

Answer 2

In open addressing, linear probing isn't just used to resolve collisions; it is also used to search for the key being looked up. You always start from the index derived from hash code and move on until you find what you're looking for, or reach either an empty slot or an entry with a different hash code. This really isn't any different from separate chaining, where you also need to follow the chain until you find the key.