Question

Please review the hash technique. I give you this phrase : If quadratic probing is used, and the table size is prime, then a new element can always be inserted if the table is at least half empty. If you disagree with this phrase, please give or provide a counter example to prove that it is in fact an incorrect statement. However, if you think that is it right, please show your reasoning behind it and prove it. Please type answer if you can

Answer 1

About Quadratic Probing:

• If the table is even one more than half full, the insertion could fail (although this is extremely unlikely).
• It is also crucial that the table size be prime.
• If the table size is not prime, the number of alternate locations can be severely reduced.
• Standard deletion cannot be performed in a closed hash table, because the cell might have caused a collision to go past it.
• Closed hash tables require lazy deletion.

Let's see why this is the case, using a proof by contradiction.

1. Say that the theorem is wrong. Then that means there are two values a and b such that 0 <= a < b < floor[M/2] that probe the same position.

2. h_a(q) and h_b(q) must probe the same position, by (1), so h_a(q) = h_b(q).

3. h_a(q) = h_b(q) ==> h(q) + c(a) = h(q) + c(b), mod M.

4. The h(q) on both sides cancel. Our c(i) is just c(i) = i^2, so we have a^2 = b^2.

5. Solving the quadratic equation in (4) gives us a^2 - b^2 = 0, mod M. This is a difference of two squares, so the solution is (a - b)(a + b) = 0, mod M.

6. But remember, we said M was a prime number. The only way that (a - b)(a + b) can be zero mod M is if [case I] (a - b) is zero, or [case II] (a + b) is zero mod M.

7. Case I can't be right, because we said that a != b, so a - b must be something other than zero.

8. The only way for (a + b) to be zero mod M is for a + b to be equal to be a multiple of M or zero. They clearly can't be zero, since they're both bigger than zero. And since they're both less than floor[M/2], their sum must be less than M. So case II can't be right either.

Thus, if the theorem were wrong, one of two quantities must be zero, neither of which can possibly be zero -- a contradiction! QED: quadratic probing doesn't satisfy property two once your table is more than half full and if your table size is a prime number. The proof is complete!