Deletion algorithms for hashing that preserve randomness
- 1 October 1981
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper studies the problem of finding efficient deletion algorithms for the coalesced hashing method, in which a portion of memory (called the address region) serves as the range of the hash function while the rest of memory (called the cellar) is devoted solely to storing records that collide when inserted. We present a deletion algorithm, which solves the open problem described in [Knu73, §6.4-23]. The main result of this paper, Theorem 3, shows that the deletion algorithm preserves randomness for the special case of standard coalesced hashing, in that deleting a record is in some sense like never having inserted it. This means that the formulas for the search times (which are analyzed in [Vit80a] and [Vit80b]) are still valid after deletions. There is as yet no known deletion algorithm that preserves randomness for the general case (when there is a cellar). We give some reasons why and then discuss some heuristics that seem to make deletions practical anyway.Keywords
This publication has 4 references indexed in Scilit:
- Tuning the coalesced hashing method to obtain optimum performancePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Deletions That Preserve RandomnessIEEE Transactions on Software Engineering, 1977
- Some Combinatorial Properties of Certain Trees With Applications to Searching and SortingJournal of the ACM, 1962
- Handling identifies as internal symbols in language processorsCommunications of the ACM, 1959