tabulation hashing


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