Python字典如何保持键顺序

Question

从Python 3.6开始字典保持插入/键的顺序。

我和一个同事争论这个是如何实现的。他说，这一定是通过使用列表或其他集合来保持键顺序来实现的。我怀疑可能有更微妙的东西在起作用。

我做了以下比较:

# Python 3.4.3
d = {1: 2, 2:3, 3:4}
od = OrderedDict(d)
print(sys.getsizeof(d))   # 288
print(sys.getsizeof(od))  # 1304

# Python 3.6.3
d = {1: 2, 2:3, 3:4}
print(sys.getsizeof(d))   # 240

OderedDict的大小是巨大的，我绝对可以看到它在后台使用这个任务的列表。然而，常规字典的大小没有发生任何变化，所以我对常规字典也使用列表来保持插入顺序的事实持怀疑态度。

那么在新的python版本中，正则字典是如何保持键顺序的呢?

Answer 1

我在dict源代码中发现了一条评论:

保持插入顺序

对于组合表来说很简单。由于dk_entries主要是追加的，我们可以通过迭代dk_entries来获得插入顺序。

和

layout:
+---------------+
| dk_refcnt     |
| dk_log2_size  |
| dk_kind       |
| dk_usable     |
| dk_nentries   |
+---------------+
| dk_indices    |
|               |
+---------------+
| dk_entries    |
|               |
+---------------+

dk_entries是PyDictKeyEntry的数组。它的大小是USABLE_FRACTION(dk_size)。DK_ENTRIES(dk)可以用来获取指向条目的指针。

因此，它似乎维护了一个数组。虽然需要进行更多的挖掘才能获得更多的信息，但这只是一个起点。

Answer 2

严格来说，这是一个实现细节。Python只指定dict记住键顺序，而不指定如何记住键顺序。

Python 3.6不保证键顺序;这是在CPython中实验性地重新实现了dict类型。当这个实验(如预期的那样)被认为是成功的时候，Python本身在Python 3.7中要求键序保存。

在CPython中，dict类型本身的C实现被修改。我不确定是如何的(您可以在这里查看详细信息)，但是在内存中保留一个额外的列表可能比在Python级别执行相同的操作更有效，这正是OrderedDict所做的。它甚至不是保存键的Pythonlist:它是一个纯Python链表，所以内存需求如此之大并不奇怪。

Answer 3

来自python 3.8源代码(参见self.__map)

class _Link(object):
__slots__ = 'prev', 'next', 'key', '__weakref__'
class OrderedDict(dict):
'Dictionary that remembers insertion order'
# An inherited dict maps keys to values.
# The inherited dict provides __getitem__, __len__, __contains__, and get.
# The remaining methods are order-aware.
# Big-O running times for all methods are the same as regular dictionaries.
# The internal self.__map dict maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# The sentinel is in self.__hardroot with a weakref proxy in self.__root.
# The prev links are weakref proxies (to prevent circular references).
# Individual links are kept alive by the hard reference in self.__map.
# Those hard references disappear when a key is deleted from an OrderedDict.
def __init__(self, other=(), /, **kwds):
'''Initialize an ordered dictionary.  The signature is the same as
regular dictionaries.  Keyword argument order is preserved.
'''
try:
self.__root
except AttributeError:
self.__hardroot = _Link()
self.__root = root = _proxy(self.__hardroot)
root.prev = root.next = root
self.__map = {}
self.__update(other, **kwds)