Tabulation hashing

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, tabulation hashing is a method for constructing <a href="/facts/Universal_hashing/NICffew4">universal families of hash functions</a> by combining <a href="/facts/Lookup_table/ULPEAGTJ">table lookup</a> with <a href="/facts/Exclusive_or/FHyr7hGQ">exclusive or</a> operations. It was first studied in the form of <a href="/facts/Zobrist_hashing/CTfD0GWd">Zobrist hashing</a> for computer games; later work by Carter and <a href="/facts/Mark_N._Wegman/YSedJyb9">Wegman</a> extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings.
Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is <a href="/facts/K-independent_hashing/xRDnzsPa">3-independent</a>: every 3-tuple of keys is equally likely to be mapped to any 3-tuple of hash values. However, it is not 4-independent. More sophisticated but slower variants of tabulation hashing extend the method to higher degrees of independence.
Because of its high degree of independence, tabulation hashing is usable with hashing methods that require a high-quality hash function, including <a href="/facts/Hopscotch_hashing/NDhG1LyL">hopscotch hashing</a>, <a href="/facts/Cuckoo_hashing/jGAUexI1">cuckoo hashing</a>, and the <a href="/facts/MinHash/NL6bV6SV">MinHash</a> technique for estimating the size of set intersections.

Tabulation hashing open-in-new

Tabulation hashing