# 10. Dictionaries ## 2 thoughts on “10. Dictionaries”

1. Roy lee says:

great lecture!

2. Mace Windu says:

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?