当我们删除一个项目时，字典是否会调整大小？ [英] Does dictionary do resize when we delete an item?

问题描述

在python中，当我们从字典中删除一个项目时，字典是否会调整大小或重建字典表。从某些网站和博客中我学到的是，当我们从字典中删除一个项目时，python将一个虚拟键插入到已删除的键中以填充字典条目，之后一个python将通过调用一些清理函数来清理虚拟键。 p>

可能有一个指导，任何好的网站或文档解释字典实现在python的引擎盖下。

解决方案

是的，当您删除键时，字典大小会改变，因为向外的长度改变。这意味着在循环中循环一个字典时会抛出异常。

是的，一个哨兵值（名为 dummy ）用于替换已删除的密钥，以便对仍存在的值进行哈希冲突测试仍然找到现有值。

但是，表是不重建;重建只适用于插入。是的，这意味着一个大型的字典表会在大量的删除之后继续使用一些内存;您可以通过使用副本替换字典来强制调整大小，或者通过插入新值直到该表为2/3满（此时调整大小可能会最终缩小表）。

如果您好奇，并且C很好地了解，请查看 C实施所有（详细记录）的细节。您也可以观看此关于如何CPython dict 的Pyon 2010演示文稿由Brandon Rhodes 作品，或者提供美丽代码，其中包括由Andrew Kuchling撰写的实施章节。

In python when we delete an item from dictionary, does the dictionary will resize or rebuild the dictionary table. From some site and blogs what I learned is that when we delete an item from the dictionary, python insert a dummy key to the deleted key to fill the dictionary entries, later one 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.

解决方案

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.

这篇关于当我们删除一个项目时，字典是否会调整大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！