logoalt Hacker News

monkeyelitelast Tuesday at 7:22 PM1 replyview on HN

> And I don't think there's that many fundamental data structures out there

No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions.

One I am aware of is a hash map that doesn’t need to delete individual keys.


Replies

cb321last Tuesday at 7:58 PM

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.

show 1 reply