python 字典中的内存分配是如何工作的？

Question

我想了解在向字典添加新数据时 python 中的内存分配是如何工作的。在下面的代码中，我一直在等待每个新添加的数据都堆叠在最后，但它并没有发生。

repetitions = {}
for item in new_deltas:
    list_aux = []
    if float(item[1]) <= 30:
        if float(item[0]) in repetitions:
            aux = repetitions[float(item[0])]
            aux.append(item[1])
            repetitions[float(item[0])] = aux
        else:
            list_aux.append(item[1])
            repetitions[float(item[0])] = list_aux
    print(repetitions)

我得到的结果如下。因此，我想了解为什么新的附加数据没有添加到堆栈的末尾，而是添加到堆栈的中间。

我的输入数据是：

new_deltas = [[1.452, 3.292182683944702], [1.449, 4.7438647747039795], [1.494, 6.192960977554321], [1.429, 7.686920166015625]]

打印行输出：

{1.452: [3.292182683944702]}
{1.452: [3.292182683944702], 1.449: [4.7438647747039795]}
{1.452: [3.292182683944702], 1.494: [6.192960977554321], 1.449: [4.7438647747039795]}
{1.429: [7.686920166015625], 1.452: [3.292182683944702], 1.494: [6.192960977554321], 1.449: [4.7438647747039795]}

Answer 1

在 Python 3.6 之前，字典没有排序（请参阅 Whosebug thread for more on that). If you are using Python 3.6 or lower (in CPython 3.6 the fact that order is maintained is an implementation detail, but with Python 3.7 it became a language feature), you can use the OrderedDict 以获得您想要的行为。

例如，您可以将代码段的开头更改为以下内容：

from collections import OrderedDict
repetitions = OrderedDict()
...

Answer 2

简答

字典被实现为 hash tables 而不是堆栈。

没有采取可能打乱密钥顺序的额外措施

哈希表

在 Python 3.6 之前，字典中的排序是通过哈希函数随机化的。大致来说，它是这样工作的：

d = {}        # Make a new dictionary
              # Internally 8 buckets are formed:
              #    [ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ]
d['a'] = 10   # hash('a') % s gives perhaps bucket 5:
              #    [ [ ] [ ] [ ] [ ] [ ] [('a', 10)] [ ] [ ] ]
d['b'] = 20   # hash('b') % s gives perhaps bucket 2:
              #    [ [ ] [ ] [('b', 20)] [ ] [ ] [('a', 10)] [ ] [ ] ]

因此，您可以看到此字典的顺序会将 'b' 放在 'a' 之前，因为哈希函数将 'b' 放在较早的存储桶中。

较新的哈希表记住插入顺序

从 Python 3.6 开始，还添加了一个堆栈。请参阅此 proof-of-concept 以更好地了解其工作原理。

因此，dict 开始记住插入顺序，并且这种行为在 Python 3.7 及更高版本中得到保证。

在旧的 Python 实现上使用 OrderedDict

3.7之前的版本，可以使用collections.OrderedDict()达到同样的效果

深入研究

对于那些有兴趣进一步了解它是如何工作的人，我有一个 37 minute video 从基本原理展示了用于制作现代 Python 词典的所有技术。

python 字典中的内存分配是如何工作的？

How does the memory allocation work in python dictionaries?

python

algorithm

dictionary

hashtable

python-3.x