NIST

twisted tabulation hashing

(algorithm)

Definition: Similar to tabulation hashing, except that the last table is indexed by the xor of the last character and a twister value from the rest of the string.

Formal Definition:
(t, hr(c)) = ⊕ni=2 T*i[ci]
h(c) = hr(c) ⊕ T1[c1 ⊕ t]
where ⊕ is the xor operation, T*i is the ith table, and ci is the ith character.

Aggregate child (... is a part of or used in me.)
tabulation hashing.

Note: The twister value and the intermediate hash value can be accumulated in the same integer, since the combining operation is xor.

The tables have additional twister values, compared to tables used in tabulation hashing.

It doesn't matter whether it is the first or the last character that is treated specially.

Author: PEB

More information

Mihai Pătraşcu and Mikkel Thorup, Twisted Tabulation Hashing, Proc. 24th annual ACM-SIAM Symposium On Discrete Algorithms (SODA '13), Pages 209-228, 2013.


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 7 June 2018.
HTML page formatted Thu Jun 7 13:10:19 2018.

Cite this as:
Paul E. Black, "twisted 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/twistedTabulationHashing.html