Skip Navigation

The Computer Journal 1986 29(5):436-450; doi:10.1093/comjnl/29.5.436
© 1986 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Chen, W. C.
Right arrow Articles by Vitter, J. S.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Deletion Algorithms for Coalesced Hashing*

W. C. Chen and J. S. Vitter §

Department of Computer Science, Brown University, Providence, R.I. 02912, USA

We present efficient deletion algorithms for three variants of coalesced chaining – late insertion (LICH), early insertion (EICH), and varied insertion (VICH). Our approach is uniform in the sense that each deletion algorithm works simultaneously for all three variants, though the implementation details are of course different. Deletion algorithms for coalesced hashing when there is a cellar have not been studied previously in the literature; these algorithms are useful because coalesced hashing is most efficient when a cellar is utilised.

First we present and analyse a deletion algorithm that preserves randomness – in that deleting a record is in some sense like never having inserted it. In particular, the formulas for the average search times after N random insertions intermixed with d random deletions are the same as the formulas for the average search times after N-d random insertions. This answers an open question in the literature. We then present two deletion algorithms that require fewer pointer fields per table slot; the latter one does not relocate records once inserted. These two algorithms do not preserve randomness, but simulations suggest that search times remain good after repeated deletions and insertions.

Received January 1985.

* This research was supported in part by an IBM research contract. The first author's current address is GTE Laboratories Incorporated, 40 Sylvan Road, MA 02254. The current address of the second author (to whom correspondence should be addressed) is Department of Computer Science, Brown University, Providence, RI 02912.

§ The Second author was also supported in part by National Science Foundation grants MCS 81-05324 and DCR 84-03613, a National Science Foundation Presidential Young Investigator Award, an IBM Faculty Development Award, and ONR and DARPA under Contract N00014 83-K-0146 and ARPA order No.4786.

Department of Computer Science, Brown University, Providence, R.I. 02912, USA


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.