Universal Hashing definition
I am trying to learn the hashing algorithms, but feel stuck at universal
hashing. As per the definition, the probability that the hash function of
two distinct keys x and y will collide is 1/m where m is total number of
slots. I get this as any key can be mapped to any slot independently of
the other and equally likely for any slot.This is also the case for simple
uniform hashing. My question is that from the very start of analysis for
hashing, we have assumed simple uniform hashing, then are we using the
same assumption for Universal hashing , or is it something different, i.e
the number of collisions between two different keys is calculated in some
other way(I was thinking on the lines of simple uniform hashing).
Thanks....
No comments:
Post a Comment