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.
(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.)
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.
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.
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