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

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 (根据我的发现)。 set 的行为方式类似，预计会与 dicts 的行为保持一致。

另一方面，

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.

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