On Dec 9, 2012, at 10:03 PM, MRAB <pyt...@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
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
