Background K-independent hashing

the goal of hashing map keys large domain (universe)



u


{\displaystyle u}

smaller range, such



m


{\displaystyle m}

bins (labelled



[
m
]
=
{
0
,
…
,
m
−
1
}


{\displaystyle [m]=\{0,\dots ,m-1\}}

). in analysis of randomized algorithms , data structures, desirable hash codes of various keys behave randomly . instance, if hash code of each key independent random choice in



[
m
]


{\displaystyle [m]}

, number of keys per bin analyzed using chernoff bound. deterministic hash function cannot offer such guarantee in adversarial setting, adversary may choose keys precisely preimage of bin. furthermore, deterministic hash function not allow rehashing: input data turns out bad hash function (e.g. there many collisions), 1 change hash function.

the solution these problems pick function randomly large family of hash functions. randomness in choosing hash function can used guarantee desired random behavior of hash codes of keys of interest. first definition along these lines universal hashing, guarantees low collision probability 2 designated keys. concept of



k


{\displaystyle k}

-independent hashing, introduced wegman , carter in 1981, strengthens guarantees of random behavior families of



k


{\displaystyle k}

designated keys, , adds guarantee on uniform distribution of hash codes.