2 ms·
> I suppose that most people don't ever erase anything from a Python dictionary? It's the tombstoning mentioned in both my comment and the essay (tombstoning i
by masklinn 5y ago
> I suppose that most people don't ever erase anything from a Python dictionary?
It's the tombstoning mentioned in both my comment and the essay (tombstoning is basically the amortisation of deletion), however you need a lot of deletion to fuck up your branching as much as a middling-load-factor hashmap does.
> Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy).
It will, however:
* maps which get items deleted from are a minority, more so for those which both get items deleted from and get iterated
* once enough items have been deleted, the buffer can be shrunk in order to remove the tombstones (converting it back to a very dense array).