Talk:Lazy deletion

Delete this article?

Lazy deletion, as described in the accompanying tech reports, doesn't work. For example, suppose you have key K1 whose probe sequence is 11, 22, 33, and is stored at 33. Suppose you have K2 whose probe sequence is 5, 22 and is stored at 22. Then the entry at 5 is marked deleted. Then there's a search for K2, and it moves from 22 to 5, leaving 22 marked as "unoccupied."

Now what happens when someone searches for K1? They look in 11, it's filled with a different key, they look in 22, and it's marked unoccupied (not deleted). So the search stops and erroneously reports that the key isn't there. It still is there, at location 33.

Note that this wikipedia article is based on the work of a single pair of researchers, who don't report ever implementing it.

Martin (talk) 12:39, 22 October 2012 (UTC)

Good point, Martin.

Lazy deletion *could* work with a little extra effort to avoid the problem you point out.

Perhaps when K2 is moved from 22 to 5, the search algorithm *doesn't* mark 22 as "unoccupied", but instead it marks 22 as "deleted". Then when someone searches for K1, the search algorithm finds 11 has a different key, 22 is marked deleted, and it continues searching until it successfully finds K1 at 33. Then, similar to the search for K2, the search algorithm moves K1 to 22, and the search algorithm marks 33 as "deleted" (not "unoccupied").

The description at linear probing § Deletion seems to imply that leads to a different problem -- deleted entries slowly accumulate, degrading the performance until they are somehow cleaned out (perhaps by re-hashing the entire table). --DavidCary (talk) 22:25, 19 February 2022 (UTC)

eager deletion

Is eager deletion where the delete just happens straight up, and you're left with lost elements? Fresheneesz 06:04, 31 October 2007 (UTC)

Actually, I think eager deletion involves with filling the hole with a value previously gotten, that matches the chain sequence. This would involve testing the next element found by probing and checking if its key would map to that spot.. etc... that would take foreeeever. Fresheneesz 06:30, 31 October 2007 (UTC)

Fresheneesz, with linear probing, eager deletion is pretty quick. It involves scanning all the values from the deleted value to the end of the cluster: O(cluster_length), which is exactly the same values scanned for lookups. The linear probing § Deletion describes the exact algorithm. Many implementations of linear-probe hash tables, in order to keep lookups fast (which also makes deletes relatively fast), automatically grow the hash table or switch to a different hash function whenever clusters get too long. --DavidCary (talk) 22:25, 19 February 2022 (UTC)

Not Complete

Lazy deletion can happen in a lot of data structure, not only in hashing. so this article should better be updated. Visame (talk) 19:45, 7 June 2008 (UTC)