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 7 June 2018.
HTML page formatted Mon Jun 18 09:05:31 2018.
Cite this as:
Paul E. Black, "tabulation hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 June 2018. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/tabulationHashing.html