A Question on Universality vs. Pair-Wise independence: The output of a hash function is used to map a particular value to a particular slot. The same output value hashes to the same slot. h(x) = h(y) means that the output of the hashing function for key x is the same as the output for the hashing function for key y. If the outputs are the same, the keys will hash to the same slot; if they are different, they will hash to different slots. In pair-wise independence, the probability that h(x1) maps to a particular slot t1 is 1/m. The probability that h(x2) maps to the SAME slot is 1/m and to a different slot is (m-1)/m. Therefore, the probability that the two outputs have the same output value is 1/(m^2). I've just asserted that the probability for the same event (two items hashing to the same slot) can be two different things, (1/m and 1/m^2) which is clearly wrong. Where am I getting tripped up on this? Thank you in advance!
The probability that h(x) = h(y) = t for some specific t is 1/m^2 (since this is the intersection of independent events h(x) = t, h(y) = t), but if you consider all m possibilities for t, the total is 1/m^2 * m = 1/m, which gives the probability that h(x) = h(y).
A Question on Universality vs. Pair-Wise independence:
The output of a hash function is used to map a particular value to a particular slot. The same output value hashes to the same slot.
h(x) = h(y) means that the output of the hashing function for key x is the same as the output for the hashing function for key y. If the outputs are the same, the keys will hash to the same slot; if they are different, they will hash to different slots.
In pair-wise independence, the probability that h(x1) maps to a particular slot t1 is 1/m. The probability that h(x2) maps to the SAME slot is 1/m and to a different slot is (m-1)/m. Therefore, the probability that the two outputs have the same output value is 1/(m^2).
I've just asserted that the probability for the same event (two items hashing to the same slot) can be two different things, (1/m and 1/m^2) which is clearly wrong.
Where am I getting tripped up on this?
Thank you in advance!
The probability that h(x) = h(y) = t for some specific t is 1/m^2 (since this is the intersection of independent events h(x) = t, h(y) = t), but if you consider all m possibilities for t, the total is 1/m^2 * m = 1/m, which gives the probability that h(x) = h(y).
1:09:17
cuckoo hashing
great lecture!
🎉
😲😲😲
:)