logoalt Hacker News

cb321last Tuesday at 7:58 PM1 replyview on HN

This is true of the common tombstone approach to deletions in hash tables { which also require rehashing (like in resizing) if there are too many tombstones }.

Somehow dissemination of Knuth v3,chapter6.4 Algorithm D has been weak, though it has lately become known as "backshift deletion" - unsure who coined that. It is limited to linear probing (but then these days that also creates the least memory traffic/potential latency). With this approach, there is no real specialized form of "hash tables that can delete". You may already know all of this and not disagreeing with anything. Just a natural follow-up.


Replies

monkeyelitelast Wednesday at 12:20 AM

If we look at the major standard libraries for hash tables, you're telling me there will be no overhead to supporting the ability to delete keys?

Isn't resizing logic already a counterexample?

show 1 reply