 <p>There are three alternatives for unsolvable hash collisions on open addressing hash tables:</p> <ol> <li>Re-hash the entire table with a different hash function, and hope that no new unsolvable hash collisions occur.</li> <li>Resize the table (with all operations that this might incur), to guarantee some more possible slots.</li> <li>Keep a separate list for unsolvable hash collisions.</li> </ol> <p>None of those options are good. </p> <p>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.</p> <p>Popular combinations include quadratic probing with a prime-sized hash table, that guarantees insertion success if the table is less than half-full, and <a href="http://stackoverflow.com/a/2349774/1157317">quadratic probing with triangular numbers and power of 2 hash table</a>, 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.</p>