10. Dictionaries

[@macewindu1827]

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!

[@digama0]

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).

[@roylee3196]

great lecture!

[@EN-hm6zx]

1:09:17 cuckoo hashing

[@lukaszplachecki8723]

🎉

[@DEFINITELYNOTBORED]

😲😲😲

[@xagent6327]

:)