python 字典容量是否动态增加？

Question

假设在 python3 中，我们使用字典作为：

my_dct = {}
...
for i in range(100):
  my_dct[i] = True
...
for s in "potentially long string":
  my_dct[s] = True

我的问题是，当我们通过python解释器运行上面的python程序时，解释器在第一行创建的容量容器是多少？根据此大小，在 第一次或第二次 for 循环 期间容量会增加吗？

This link shows capacity 8. While this根据类型显示128、2^15等作为python中字典实例化时容器的容量。

非常感谢任何解释，谢谢。

Answer 1

dict 存储如何随着它的增长而调整是一个实现细节，大多数用户不需要知道。如果您是开发人员，或者想用 C 编写自己的代码，那么详细信息可能会有用。但是对于在列表和字典之间进行选择，它们并不重要。

列表和字典的重要区别在于它们的索引方式。列表由整数（或切片）索引，'contains' 所有值直到它的 len。字典由键索引，键可以是任何可散列的对象。字符串最常见。

In [1]: import sys

表面上这两个对象是等价的：

In [2]: adict = {i:True for i in range(100)}
In [3]: alist = [i for i in range(100)]

两者都有 len() 100，并且可以通过相同的方式进行索引：

In [4]: adict[50]
Out[4]: True
In [5]: alist[50]
Out[5]: 50

糟糕，我打算使用 alist = [True for i in range(100)]，一个包含 100 个 True 值的列表，而不是 list(range(100))。但这并没有改变下面的讨论。

一个关键区别是列表索引必须是连续的。也就是说，如果我们想使用 alist[200]，我们将不得不向列表中添加另外 101 个值。而 adict[200]=False 只是将 200 添加到散列 table，新的 len 为 101.

底层存储完全不同。

alist 有一个包含 100 个值的引用的 C 数组，加上一些 'head room' 以允许 alist.append(...).

快速增长

adict 有一个散列 table，以某种方式存储对键和值的引用。

在这两种情况下，随着它们的增长，存储空间 ('container'?) 在填满时必须重新分配。同样，细节取决于实现，并且在很大程度上对用户不可见 - 除非我们仔细跟踪内存或时间。

我已经看到许多尝试比较列表和数组的 getsizeof 的 SO 问题。答案总是指出这种比较的价值有限，因为它衡量的是非常不同的东西。

In [8]: sys.getsizeof(alist)
Out[8]: 904
In [9]: sys.getsizeof(adict)
Out[9]: 4696

对于list，getsizeof基本上是存储值引用的C数组的大小。对于 100 的 len(alist)，这是 8*100 字节，大致增长 space 13 个值 - 在这一点上它必须重新分配。

添加 6 个值不会改变大小：

In [11]: alist.extend([True]*6)
In [12]: len(alist)
Out[12]: 106
In [13]: sys.getsizeof(alist)
Out[13]: 904

再添加 6，强制重新分配，头部更大 space（参考 27）：

In [14]: alist.extend([True]*6)
In [15]: len(alist)
Out[15]: 112
In [16]: sys.getsizeof(alist)
Out[16]: 1112

我假设 getsizeof(adict) 测量散列的大小 table。那是相当大了。

向 adict 添加 12 个键不会改变大小。有足够的 space 来处理这些值而不会发生冲突。

In [21]: adict.update({i:True for i in range(100,106)})
In [22]: len(adict)
Out[22]: 106
In [23]: sys.getsizeof(adict)
Out[23]: 4696
In [24]: adict.update({i:True for i in range(106,112)})
In [25]: sys.getsizeof(adict)
Out[25]: 4696

对于总内存占用，我们还必须考虑键和值的内存使用。在这些示例中，这并不多，因为对 True 的所有引用都引用同一个对象。并且最大 255 的整数也是预先分配的并且是唯一的。但键可以是字符串、元组或更复杂的对象。值可以是一个对象，尽管将它们添加到列表或字典中确实会增加内存使用。它们是通过引用而不是值存储的。

python 字典容量是否动态增加？

Does python dictionary capacity increase dynamically?

dictionary

cpython

hashmap

python-3.x