为什么字典在删除后不调整大小？

Question

显然，删除字典中的条目不会触发任何大小调整。只有在添加条目后才会触发调整大小。

从下面可以看出：

# Drastic example, nobody does such 
# things with dicts FWIK
from sys import getsizeof

d = {i:i for i in range(100)}
print(getsizeof(d))  # 4704
for i in range(100):
    del d[i]  # similarly with pop
print(getsizeof(d))  # 4704
d[0] = 1 # triggers resize

以及来自 a question on SO（根据我的发现）。 sets 的行为方式类似，预计会与指令一致。

lists，另一方面，当新大小变为已分配大小的一半时调整大小；这是在 list_resize comment:

中说明的

/* Bypass realloc() when a previous overallocation is large enough
   to accommodate the newsize.  If the newsize falls lower than half
   the allocated size, then proceed with the realloc() to shrink the list.
*/

为什么字典（以及间接地集合）不使用类似的技巧而是等待插入新条目？描述的行为适用于 Python 2.7 和 3.x（直到 Python 3.7.0a0）。

Answer 1

这在 Objects/dictnotes.txt 中有所解释，这是一个包含有关 dict 实现的各种注释的配套文件：

Dictionary operations involving only a single key can be O(1) unless resizing is possible. By checking for a resize only when the dictionary can grow (and may require resizing), other operations remain O(1), and the odds of resize thrashing or memory fragmentation are reduced. In particular, an algorithm that empties a dictionary by repeatedly invoking .pop will see no resizing, which might not be necessary at all because the dictionary is eventually discarded entirely.

一个重要的考虑因素是缩小列表的缓冲区非常容易，而缩小字典的内部哈希 table 是一个复杂得多的操作。

为什么字典在删除后不调整大小？

Why don't dictionaries resize after deletions?

python

dictionary

python-internals