k‐independent hashing





     k‐independent  or  k‐universal:  select  a function from the
family randomly. hash codes of  k  keys  are  independent  random
variables.

purpose:  for  good  average case performance in randomized algo‐
rithms

strongly 2‐universal: pairwise independence

generalized: k‐independent hashing