在Python中，当我们从字典中删除一个条目时，字典会重新调整大小或重构字典表吗？从一些网站和博客上了解到，当我们从字典中删除一个条目时，Python会插入一个虚拟键来填充字典条目的删除键，稍后Python将通过调用一些清理函数来清除虚拟键。能否有人指导一下哪个好的网站或文档可以在Python幕后解释字典实现呢？
当我们删除一个项目时，字典是否会进行调整大小？
3
- James Sapam
2
强大的字典 - Ashwini Chaudhary
谢谢，我需要检查一下。 - James Sapam
2个回答
9
是的，当您删除键时，字典的大小会改变，即外部长度会发生变化。这意味着在循环遍历字典时删除其中的键将抛出异常。
是的，一个名为dummy的哨兵值被用来替换已删除的键，以便对于仍存在的值进行哈希冲突测试时能找到这些现有值。
然而，表格不会被重建；只有插入操作才会重新构建表格。是的，这意味着大型字典表格将在经过许多删除操作之后仍使用一些内存；您可以通过将该字典替换为副本或插入新值直到表格达到2/3满的程度（此时调整大小可能会缩小表格）来强制执行调整大小。
如果您感到好奇，并且足够了解C，请查看C实现，了解所有（说明得很清楚的）细节。您也可以观看Brandon Rhodes在Pycon 2010演讲，了解CPython dict的工作原理，或者阅读《优美代码》中由Andrew Kuchling撰写的一章关于字典实现的内容。
- Martijn Pieters
6
所以，在这里，阈值是字典哈希表的大小或者？ - James Sapam
@yopy：没错，我重新验证了一下，删除时没有任何阈值来调整表格大小。 - Martijn Pieters
@MartijnPieters，你所说的虚拟值是指垃圾值吗？ - user2290820
@user2290820：不是，使用了特定的“槽为空”值。源代码将其命名为“dummy”。 - Martijn Pieters
@MartijnPieters 我不明白 (&_dummy_struct) 是什么？ - user2290820
1@user2290820：只是一个非常高效、尽可能紧凑的数据类型，用于表示哨兵值。它曾经是一个单例字符串对象，但这样更加紧凑。 - Martijn Pieters
0
是的，就像你说的那样，会插入和删除虚拟键。
这是Laurent Luce关于该主题的博客文章：http://www.laurentluce.com/posts/python-dictionary-implementation/。
最后一节回答了你的问题。
这是Laurent Luce关于该主题的博客文章：http://www.laurentluce.com/posts/python-dictionary-implementation/。
最后一节回答了你的问题。
- pradyunsg
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接