HiCHT: High-Performance Compact Hash Table

Hash tables represent a fundamental data structure in the field of information retrieval. The optimization of space and performance for this structure is crucial and urgent. Clerry first proposed a compact hash table that allows the use of space close to the information-theoretic lower bound by storing only the quotient part of each key. However, it sacrifices the performance of basic operations due to the overhead of resolving hash conflicts. Subsequent optimized methods use the chaining strategy to handle hash collisions, but they suffer from the slow comparison of each element in the linked list. In this paper, we present HiCHT, a hash table with chaining buckets to minimize the overhead of handling hash collisions. Each bucket stores only the quotient of the key to reduce space and introduces a coarse fingerprint filter to identify elements in the linked list quickly. The experimental results demonstrate that HiCHT is significantly superior to all existing variants based on the compact hash table in terms of performance for basic operations. Moreover, its memory usage is also competitive with the best-performing method.