[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Raymond Hettinger 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 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>

More information about the Python-Dev mailing list