Hash Tables With Finite Buckets Are Less Resistant to Deletions
Source: Columbia University
The authors show that when memory is bounded, i.e., buckets are finite, dynamic hash tables that allow insertions and deletions behave significantly worse than their static counterparts that only allow insertions. This behavior differs from previous results in which, when memory is unbounded, the two models behave similarly. They show the decrease in performance in dynamic hash tables using several hash-table schemes. They also provide tight upper and lower bounds on the achievable overflow fractions in these schemes. Finally, they propose an architecture with Content-Addressable Memory (CAM), which mitigates this decrease in performance.