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 ...)
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.
Albert L. Zobrist, A New Hashing Method With Application for Game Playing, University of Wisconsin-Madison Department of Computer Sciences, TR88, 1970.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 19 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "tabulation hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 19 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/tabulationHashing.html