Visible to the public Biblio

Filters: Author is Wortman, Kevin A.  [Clear All Filters]
2022-06-09
Palit, Shekhar, Wortman, Kevin A..  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.