Biblio
Filters: Keyword is tabulation hashing [Clear All Filters]
.
2021. Perfect Tabular Hashing in Pseudolinear Time. 2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC). :0228–0232.
We present an algorithm for generating perfect tabulation hashing functions by reduction to Boolean satisfaction (SAT). Tabulation hashing is a high-performance family of hash functions for hash tables that involves computing the XOR of random lookup tables. Given n keys of word size W, we show how to compute a perfect hash function in O(nW) worst-case time. This is competitive with other perfect hashing methods, and the resultant hash functions are simple and performant.