Maximum Size of a Dynamic Data Structure: Hashing with Lazy Deletion Revisited
David Aldous, Micha Hofri, Wojciech Szpankowski · SIAM Journal on Computing · 1992
The dynamic data structure management technique called hashing with lazy deletion (HwLD) is studied. A table managed under HwLD is built by a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible but keeps more items in the data structure than would be the case with immediate-deletion strategies. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead—in space and time—for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. This paper investigates the maximum size and the excess space used by HwLD, under general probabilistic assumptions, by using the methodology of queueing theory. In particular, for the Poisson arrivals and general lifetime distribution of items, the excess space does not exceed the number of buckets in HwLD. As a byproduct of the analysis, the limiting distribution of the maximum queue length in an $M|G|\infty $ queueing system is also derived. The results generalize previous work in this area.