python - 字典大小在增加一个元素时减少

Question

我跑了这个：

import sys

diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1}
print sys.getsizeof(diii)
# output: 1048

diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1,'key8':2}
print sys.getsizeof(diii)
# output: 664  

在询问之前，我重新启动了我的python shell，并在网上进行了尝试，得到了相同的结果。
我认为一个多元素的字典将给出与输出相同的字节或更多的字节，而不是一个少元素的字典。
知道我做错什么了吗？

Answer 1

前面的答案已经提到了您不必担心，所以我将深入了解一些更详细的技术细节。很长，但请你忍受我。
这与调整大小的算法有关。每个resize都分配2**i内存，其中2**i > requested_size; 2**i >= 8，但是如果有2/3的槽被填满，那么每个insert都会进一步调整基础表的大小，但这次是new_size = old_size * 4。这样，您的第一个字典最终分配了32个单元格，而第二个字典则只分配了16个（因为前面的初始大小更大）。
答：正如@snakecharmerb在评论中指出的，这取决于词典的创建方式。为了简洁起见，让我参考一下this, excellent blog post，它解释了在python字节码和cpython实现级别上，dict()构造函数和dict literal{}之间的区别。
让我们从8把钥匙的神奇数字开始。结果发现它是一个常量，在头文件中为python的2.7实现预定义。
-python字典的最小大小：

/* PyDict_MINSIZE is the minimum size of a dictionary.  This many slots are
 * allocated directly in the dict object (in the ma_smalltable member).
 * It must be a power of 2, and at least 4.  8 allows dicts with no more
 * than 5 active entries to live in ma_smalltable (and so avoid an
 * additional malloc); instrumentation suggested this suffices for the
 * majority of dicts (consisting mostly of usually-small instance dicts and
 * usually-small dicts created to pass keyword arguments).
 */
#define PyDict_MINSIZE 8

因此，在特定的Python实现之间可能会有所不同，但我们假设都使用相同的cpython版本。不过，8号的dict预计只包含5个元素；不要担心，因为这种特定的优化对我们来说并不像看上去那么重要。
现在，当您使用dict literal创建字典时，cpython使用快捷方式（与调用 {}构造函数时的显式创建相比）。简化一点，字节码操作会得到解决，它会导致调用 dict函数，该函数将构造一个字典，我们已经预先知道其大小：

/* Create a new dictionary pre-sized to hold an estimated number of elements.
   Underestimates are okay because the dictionary will resize as necessary.
   Overestimates just mean the dictionary will be more sparse than usual.
*/

PyObject *
_PyDict_NewPresized(Py_ssize_t minused)
{
    PyObject *op = PyDict_New();

    if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
        Py_DECREF(op);
        return NULL;
    }
    return op;
}

此函数调用普通dict构造函数（ BUILD_MAP）并请求调整新创建的dict的大小-但前提是该函数应包含5个以上的元素。这是由于一种优化，允许python通过将数据保存在预先分配的“smalltable”中来加快某些速度，而无需调用昂贵的内存分配和取消分配函数。
然后， _PyDict_NewPresized将尝试确定新字典的最小大小。它还将使用幻数8-作为起点，并迭代乘以2，直到找到大于请求大小的最小大小。对于第一个字典，这仅仅是8，但是对于第二个字典（以及所有由dict literal创建的、键数少于15的字典），它是16。
现在，在 PyDict_New函数中，前者的 dictobject.h更小，这意味着要提出前面提到的优化（使用“小表”来减少内存操作操作）。但是，因为不需要调整新创建的dict的大小（例如，到目前为止没有删除任何元素，因此表是“干净的”），所以实际上什么都不会发生。
相反，当 dictresize时，通常会执行重新分配哈希表的过程。最后会分配一个新表来存储
“大”字典。虽然这是直观的（更大的口述有一个更大的桌子），这似乎还没有推动我们前进到观察到的行为-但是，请再忍受我一分钟。
一旦我们有了预先分配的dict，store-map optcodes就会告诉解释器插入连续的键值对。这是通过 dictresize函数实现的，如果超过2/3的槽已经用完，该函数在每次增加大小（即成功插入）后，都会调整字典的大小。大小将增加x4（ a special case，对于大型dict，仅增加x2）。
下面是使用7个元素创建dict时所发生的情况：

# note 2/3 = 0.(6)
BUILD_MAP   # initial_size = 8, filled = 0
STORE_MAP   # 'key_1' ratio_filled = 1/8 = 0.125, not resizing
STORE_MAP   # 'key_2' ratio_filled = 2/8 = 0.250, not resizing
STORE_MAP   # 'key_3' ratio_filled = 3/8 = 0.375, not resizing
STORE_MAP   # 'key_4' ratio_filled = 4/8 = 0.500, not resizing
STORE_MAP   # 'key_5' ratio_filled = 5/8 = 0.625, not resizing
STORE_MAP   # 'key_6' ratio_filled = 6/8 = 0.750, RESIZING! new_size = 8*4 = 32
STORE_MAP   # 'key_7' ratio_filled = 7/32 = 0.21875

最后得到的是哈希表中总大小为32个元素的dict。
但是，当添加八个元素时，初始大小将是原来的两倍（16），因此我们永远不会调整大小，因为条件永远不会满足。
这就是为什么在第二种情况下你会得到一张小桌子。