Wait, if it is held in a separate dense array, is removal of a key from a dictio...

dilap · on Feb 8, 2020

You don't actually remove the entry, you just mark it as deleted.

Eventually if too many things are deleted you repack the array. Still amortized O(1). (No different than a hash table in general, which will need to recopy the underlying array when it grows.)

jameshart · on Feb 8, 2020

Brilliant: Now your map contains an allocator and a garbage collector.

dilap · on Feb 9, 2020

sure, but as mentioned in the parenthetical, that was already true even for a non-ordered hash table

Rapzid · on Feb 8, 2020

I _think_ this may be the implementation: https://github.com/python/cpython/blob/60ac6ed5579f6666130fc...

There are copious notes in there about the implementation and it indicates linked lists are used.

EDIT: Blargh, it's here: https://github.com/python/cpython/blob/60ac6ed5579f6666130fc... . That file references this blog post which indicates they may be flagging and repacking as dilap commented: https://morepypy.blogspot.com/2015/01/faster-more-memory-eff...

Rapzid · on Feb 8, 2020

You can use memcpy to remove items from the middle of a memory segment. It's probably not a single memory segment either; I imagine it works more like a Golang slice.

jameshart · on Feb 8, 2020

Great, you recovered the memory. But now you have to update all the pointers to the array in the hashmap....

ummonk · on Feb 8, 2020

Memcpy is certainly O(N). But yeah, if they implement it with multiple slices (e.g. a B tree) it could be fast.

Rapzid · on Feb 8, 2020

Hrm, I'm pretty sure I meant memmove: https://golang.org/src/runtime/slice.go

EDIT: I could have sworn they were shifting entire pages around without using a cycle per byte but I can't find any reference to that now haha.