I would really appreciate if someone could help solve this problem. The question is: Consider the following hash function: h(k, i) = (h’(k) + (1/2) (i + i^2 )) mod m, where m = 2^p for some positive integer p. Prove or disprove that for any k, the probe sequence is a permutation of <0, 1, 2, ...,m – 1>
Asked
Active
Viewed 1,727 times
1
-
What does h'(k) denote? – Pavel Oct 25 '16 at 12:55
-
its is a hash function – Jamal Ahmed Oct 25 '16 at 12:55
-
the initial hash function, which remains constant throughout, something like (k mod 11) – Jamal Ahmed Oct 25 '16 at 13:06
-
2"Please do my homework for me" is a poor question for Stack Overflow. – Toby Speight Oct 25 '16 at 13:18
-
What is a "probe sequence"? – kraskevich Oct 25 '16 at 13:37
-
– Jamal Ahmed Oct 25 '16 at 13:43
-
this is a probe sequence – Jamal Ahmed Oct 25 '16 at 13:43
-
This has an answer [here](http://stackoverflow.com/questions/2348187/moving-from-linear-probing-to-quadratic-probing-hash-collisons/2349774#2349774). – Ami Tavory Oct 25 '16 at 14:06
-
Thank you! This is exactly what I needed! – Jamal Ahmed Oct 25 '16 at 14:14
1 Answers
2
Yes, it is.
Let's assume that h(k, i) = h(k, j).
Then h'(k) + 1/2 * i * (i + 1) = h'(k) + 1/2 * j * (j + 1) (mod m) <=>
1/2 * i * (i + 1) = 1/2 * j * (j + 1) (mod m) => i * (i + 1) = j * (j + 1) (mod 2m) <=> i * i - j * j + i - j = 0 (mod 2m) <=> (i - j) * (i + j + 1) = 0 (mod 2m). The second term is odd and 2m = 2^(p + 1), thus i = j (mod 2m) => i = j (mod m).
kraskevich
- 18,368
- 4
- 33
- 45