[Python-Dev] More compact dictionaries with faster iteration
raymond.hettinger at gmail.com
Mon Dec 10 04:30:22 CET 2012
On Dec 9, 2012, at 10:03 PM, MRAB <python at mrabarnett.plus.com> wrote:
> What happens when a key is deleted? Will that leave an empty slot in
> the entry array?
Yes. See the __delitem__() method in the pure python implemention
> If so, will the array be compacted if the proportion
> of entries grows beyond a certain limit?
Yes. Compaction happens during resizing() which triggers when
the dict reaches two-thirds full (including dummy entries).
See the __setitem__() method in the pure python implementation.
> Adding a key would involve simply appending to the entry array (filling
> the last empty slot), but if there could be empty slots in other
> places, would it look for the first?
Yes. See the _next_open_index() helper method in the pure python implemention.
> Actually, as I think about it, you could form a linked list (using the
> 'hash' field) of those empty slots that aren't part of the final
> contiguous block and fill those preferentially.
That's the plan. See the comment above the keylist.index(UNUSED)
line in the _next_open_index() method in the pure python implementation.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-Dev