> 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.
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.