Something I was curious about from my lecture:
Suppose we want to probe every Rth location for the function x mod 10 and R = 2. Now to hash 4, 14, 114, 1114, and 11114:
But for 1114, it seems to keep going on forever- no matter where it goes, it'll always run into a full slot. What happens in this case?
There are three alternatives for unsolvable hash collisions on open addressing hash tables:
None of those options are good.
What you should do is to carefully chose your probing method in combination with the hash table size. If your table size was odd, with the same constant step, you would not run in this problem while there was still space in the table.
Popular combinations include quadratic probing with a prime-sized hash table, that guarantees insertion success if the table is less than half-full, and quadratic probing with triangular numbers and power of 2 hash table, that guarantees insertion if the table isn't full. Power of 2 sized hash tables have many advantages, the only defect being that they are unforgiving on the quality of the hash algorithm.