10. Dictionaries

10. Dictionaries

Daniel Ostrander

Related Posts

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?

    Thank you in advance!

Leave a Reply

Your email address will not be published. Required fields are marked *