2

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:

  • 4 would go in slot 4.
  • 14 would first try to get into slot 4, but seeing that it's full, it'll go to slot 6 then (+R).
  • 114 would find slot 4 full, going to slot 6 (+R), but since that's full, it'll go to Slot 0 (+2R).

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?

Servy
  • 202,030
  • 26
  • 332
  • 449
forthewinwin
  • 4,455
  • 4
  • 19
  • 17
  • what happens when the entire table is traversed with probing depends how your algorithm is defined, but it is common to have a linked list of values for buckets with collisions. – Mitch Wheat Jun 05 '12 at 04:26

1 Answers1

1

There are three alternatives for unsolvable hash collisions on open addressing hash tables:

  1. Re-hash the entire table with a different hash function, and hope that no new unsolvable hash collisions occur.
  2. Resize the table (with all operations that this might incur), to guarantee some more possible slots.
  3. Keep a separate list for unsolvable hash collisions.

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.

Community
  • 1
  • 1
ReneSac
  • 521
  • 3
  • 9