tabulation hashing

(algorithm)

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

Formal Definition: h(c) = ⊕ⁿ_i=1 T_i[c_i], where ⊕ is the xor operation, T_i is the i^th table, and c_i is the i^th character.

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

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

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

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 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