| Title | Perfect Tabular Hashing in Pseudolinear Time |
| Publication Type | Conference Paper |
| Year of Publication | 2021 |
| Authors | Palit, Shekhar, Wortman, Kevin A. |
| Conference Name | 2021 IEEE 11th Annual Computing and Communication Workshop and Conference (CCWC) |
| Keywords | 2SAT, compositionality, Conferences, hash algorithms, Hash Function, Hash functions, hash table, perfect hashing, Prototypes, pubcrawl, resilience, Resiliency, SAT, tabulation hashing, Time complexity |
| Abstract | 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. |
| DOI | 10.1109/CCWC51732.2021.9375992 |
| Citation Key | palit_perfect_2021 |
Perfect Tabular Hashing in Pseudolinear Time