NIST

tabulation hashing

(algorithm)

Definition: The hash value is the xor of values from tables (arrays) indexed by characters.

Formal Definition: h(c) = ⊕ni=1 Ti[ci], where ⊕ is the xor operation, Ti is the ith table, and ci is the ith character.

Generalization (I am a kind of ...)
hash function.

Aggregate parent (I am a part of or used in ...)
twisted tabulation hashing.

See also Pearson's hash, Zobrist hashing [Wikipedia].

Note: The typical hash function is the xor of the representation of characters, that is, h(c) = ⊕ni=1 ci.

The tables may be filled with random values or may have values chosen to avoid collisions or for other properties.

For games, e.g. chess, "characters" are pieces, like pawn, knight, and queen.

Author: PEB

More information

Albert L. Zobrist, A New Hashing Method With Application for Game Playing, University of Wisconsin-Madison Department of Computer Sciences, TR88, 1970.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 20 July 2018.
HTML page formatted Fri Jul 20 16:29:10 2018.

Cite this as:
Paul E. Black, "tabulation hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 July 2018. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/tabulationHashing.html