Deletion algorithms for hashing that preserve randomness

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.