[Python-Dev] More compact dictionaries with faster iteration

[Raymond Hettinger]

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
at http://code.activestate.com/recipes/578375

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


Raymond

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20121209/3bae7321/attachment.html>