The Full Wiki

More info on Lazy deletion

Lazy deletion: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

In computer science, lazy deletion refers to a method of deleting elements from a hash table that uses open addressing. In this method, deletions are done by marking an element as deleted, rather than erasing it entirely. Deleted locations are treated as empty when inserting and as occupied during a search.

The problem with this scheme is that as the number of delete/insert operations increases the cost of a successful search increases. To improve this when an element is searched and found in the table the element is relocated to the first location marked for deletion that was probed during the search. Instead of finding an element to relocate when the deletion occurs, the relocation occurs lazily during the next search.[1]

References

  1. ^ Celis, Pedro; Franco, John (1995), The Analysis of Hashing with Lazy Deletions, Computer Science Department, Indiana University, Technical Report CS-86-14, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.9637  

bbb


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message