Article ID Journal Published Year Pages File Type
450903 Computer Networks 2012 14 Pages PDF
Abstract

We show that when memory is bounded, i.e. memory 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.We show the decrease in performance in dynamic hash tables using several hash-table schemes. We also provide tight upper and lower bounds on the achievable overflow fractions in these schemes. Finally, we propose an architecture with content-addressable memory (CAM), which mitigates this decrease in performance.

Related Topics
Physical Sciences and Engineering Computer Science Computer Networks and Communications
Authors
, , ,