2 ms·
I suppose that most people don't ever erase anything from a Python dictionary? Erasing items would lower the effective load factor of the array (or be O(n) so
by pclmulqdq 5y ago
I suppose that most people don't ever erase anything from a Python dictionary? Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy). It's interesting that this highlights how Python users use dictionaries very differently from how I use hash tables (as a C and C++ programmer).
In the last few years, people have been designing hash tables to run at much higher load factors, but if the decision was made before ~2018, I can see why the iteration speed argument would result in a structure like this.
- 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).