CODEWITHSUNDEEP
data-structureshash
Sai Prasanna
Sai Prasanna

Reputation: 694

Can Dynamic resizing alone preserve correctness of Hash table?

I was looking through MIT Open courseware 6.006 , It had the following question,

Alyssa decides to implement both collision resolution and dynamic resizing for her hash table. However, she doesn’t want to do more work than necessary, so she wonders. If she needs both to maintain the correctness and performance she expects. After all, If she has dynamic resizing, she can resize to avoid collisions; and if she has collision resolution, collisions don’t cause correctness issues. Which statement about these two properties true?

  1. Dynamic resizing alone will preserve both properties.
  2. Dynamic resizing alone will preserve correctness, but not performance.
  3. Collision resolution alone will preserve performance, but not correctness.
  4. Both are necessary to maintain performance and correctness.

The correct answer was given in solution as 4,

"Without collision resolution, no correctness: could have an actual hash collision, and then no amount of resizing will let both be entered into the table."

This is where I get confused if we keep increasing the table size and our hash function is simple uniform hashing , then wont the values of hash change eventually?

if h(k1) = h(k2) => k1 mod size1 = k2 mod size1

if k1, k2 are unique, then 

for some size x

h(k1) != h(k2)

right?

Upvotes: 0

Views: 339

Answers (1)

Wormbo
Wormbo

Reputation: 4992

Hash functions already have an upper bound on the size of the calculated hash. A hash function will calculate a fixed-length value from some potentially variable-length value, i.e. there will always be the chance of collisions, no matter how large your hash table is.

Simply because you are mapping a larger number of values to a smaller number of slots, slots will have more than one item assigned. That's a collision and it's unavoidable.

Upvotes: 1

Related Questions