Lockless Hash Tables with Low False Negatives

Hash tables are efficient storage data structures widely used in many types of high-performance computer-related problems. In their design, optimal trade-offs must be made to accommodate for the specific characteristics of the application. In this paper we present lock-free low-false-negative (LFN) tables, a family of hash tables designed to address one such type of tradeoff. LFN tables sacrifice a low probability of false negatives and a very low (or negligible) probability of false positives to achieve higher performance access time in concurrent shared memory applications.

For information on Reservoir’s technology related to this paper, visit Algorithms.