CODEWITHSUNDEEP
pythondictionary
James Sapam
James Sapam

Reputation: 16940

Does dictionary do resize when we delete an item?

In python when we delete an item from dictionary, does the dictionary resize or rebuild the dictionary table? From some websites and blogs what I learned is that when we delete an item from the dictionary, Python inserts a dummy key to the deleted key to fill the dictionary entries, later, python will clean the dummy key by calling some cleanup function.

Could some one guide to any good site or document which explained dictionary implementation in Python under the hood?

Upvotes: 3

Views: 3384

Answers (2)

Martijn Pieters
Martijn Pieters

Reputation: 1122252

Yes, the dictionary size will change when you remove keys, in that the outward length changes. This means that an exception will be thrown when looping over a dictionary while deleting keys inside the loop.

Yes, a sentinel value (named dummy) is used to replace the deleted key, so that hash collision tests for still existing values still find the existing values.

However, the table is not rebuilt; rebuilding is only done for insertions. Yes, this means that a large dictionary table will keep using some memory after a lot of deletions from it; you can force a resize by replacing the dictionary with a copy, or by inserting new values until the table is 2/3rds full (at which point a resize can end up shrinking the table).

If you are curious, and understand C well enough, take a look at the C implementation for all the (well documented) details. You could also watch this Pycon 2010 presentation by Brandon Rhodes about how CPython dict works, or pick up a copy of Beautiful Code, which includes a chapter on the implementation written by Andrew Kuchling.

Upvotes: 9

pradyunsg
pradyunsg

Reputation: 19416

Yes. A dummy key is inserted and removed, just like you said.

Here's a blog post by Laurent Luce on the topic: http://www.laurentluce.com/posts/python-dictionary-implementation/ .

The last section answers your question.

Upvotes: 0

Related Questions