(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
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 Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "twisted tabulation hashing", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 7 June 2018. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/twistedTabulationHashing.html