A Queueing Analysis of Hashing with Lazy Deletion

DOI10.1137/0216073MaRDI QIDQ3029974zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Larry Shepp, Christopher J. Van Wyk, John A. Morrison

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://repository.upenn.edu/statistics_papers/409

zbMATH Keywords

storagedynamic dictionaryfirst passge timeslazy deletion

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Recommendations

• The complexity of hashing with lazy deletion
• Maximum queue size and hashing with lazy deletion
• The effect of deletions on different insertion disciplines for hash tables
• On deletions in open addressing hashing
• Deletion Algorithms for Coalesced Hashing

Cited in

(8)

• Busy periods in a system with heterogeneous servers or channels
• Maximum queue size and hashing with lazy deletion
• Exact results for the distribution of the partial busy period for a multi-server queue
• An approximate analysis of the performance of extendible hashing with elastic buckets
• Hashing lazy numbers
• Busy periods in M/M/\(\infty\) systems with heterogeneous servers
• The complexity of hashing with lazy deletion
• Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions

This page was built for publication: A Queueing Analysis of Hashing with Lazy Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3029974)