blocks|key|1305344|text|来自python3.8源代码(参见self.__map)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1305345|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)|code-block|syntax|javascript|1305346|entityMap^0|H|A|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

From python 3.8 source code (see <code>self.__map</code>)
<pre><code>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)
</code></pre>

blocks|key|1305486|text|严格地说，这是一个实现细节。Python只指定dict确实记住键顺序，而不是它是如何执行的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1305487|Python3.6没有保证键顺序；这是dict类型在CPython中的实验性重新实现。当(如预期的)该实验被认为是成功的时候，Python本身就需要在Python3.7中保存密钥顺序。|1305488|在CPython中，修改dict类型本身的C实现。我不确定具体的方法(您可以查看细节这里)，但是在内存中保留一个额外的列表可能比在OrderedDict级别执行等效的操作更有效，这正是OrderedDict所做的。它甚至不是保存键的Python+list：它是一个纯Python链接列表，因此内存需求如此之大并不令人惊讶。|1305489|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/python/cpython/blob/main/Objects/dictobject.c^0|N|4|0|J|4|0|C|4|1T|B|2K|B|3F|4|16|2|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|U|8|@$9|V|A|W|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|X|8|@$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]]|D|@$9|16|A|17|1|18]]|E|$]]|$1|J|3|-4|5|6|7|19|8|@]|D|@]|E|$]]]|K|$L|$5|M|N|O|E|$P|Q]]]]

Strictly speaking, it's an implementation detail. Python only specifies that a <code>dict</code> does remember key order, not how it does it.
Python 3.6 did not guarantee key order; that was an experimental re-implementation of the <code>dict</code> type in CPython. When (as expected) that experiment was deemed a success, Python itself required key-order preservation in Python 3.7.
In CPython, the C implementation of the <code>dict</code> type itself is modified. I'm not sure exactly how (you can look into the details <a href="https://github.com/python/cpython/blob/main/Objects/dictobject.c" rel="nofollow noreferrer">here</a>), but keeping an additional list in memory would likely be more efficient that doing the equivalent at the Python level, which is precisely what <code>OrderedDict</code> does. It's not even a Python <code>list</code> that holds the keys: it's a pure-Python linked list, so it's not surprising that the memory requirement is so large.

blocks|key|877456|text|我在来源上找到了一条评论|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|877457|保持插入顺序
这对组合桌来说很简单。由于dk_entries主要是附加的，所以只需迭代dk_entries就可以得到插入顺序。|blockquote|877458|和|877459|layout:

%2B---------------%2B
%7C+dk_refcnt+++++%7C
%7C+dk_log2_size++%7C
%7C+dk_kind+++++++%7C
%7C+dk_usable+++++%7C
%7C+dk_nentries+++%7C
%2B---------------%2B
%7C+dk_indices++++%7C
%7C+++++++++++++++%7C
%2B---------------%2B
%7C+dk_entries++++%7C
%7C+++++++++++++++%7C
%2B---------------%2B|code-block|syntax|javascript|877460|dk_entries是PyDictKeyEntry的数组。它的大小是USABLE_FRACTION(dk_size)。DK_ENTRIES(dk)可以用来获取指向条目的指针。|877461|因此，它似乎维护了一个数组。为了获得更多的信息，还需要做更多的挖掘工作，但这是一个起点。|877462|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/python/cpython/blob/ac75f6bdd4748b3378dd321f862d13aa1898f77a/Objects/dictobject.c#L89|1|https://github.com/python/cpython/blob/ac75f6bdd4748b3378dd321f862d13aa1898f77a/Objects/dictobject.c#L17^0|2|2|0|0|0|0|1|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@$A|12|B|13|1|14]]|C|$]]|$1|D|3|E|5|F|7|15|8|@]|9|@]|C|$]]|$1|G|3|H|5|6|7|16|8|@]|9|@$A|17|B|18|1|19]]|C|$]]|$1|I|3|J|5|K|7|1A|8|@]|9|@]|C|$L|M]]|$1|N|3|O|5|F|7|1B|8|@]|9|@]|C|$]]|$1|P|3|Q|5|6|7|1C|8|@]|9|@]|C|$]]|$1|R|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]]|S|$T|$5|U|V|W|C|$X|Y]]|Z|$5|U|V|W|C|$X|10]]]]

I found a comment in the <a href="https://github.com/python/cpython/blob/ac75f6bdd4748b3378dd321f862d13aa1898f77a/Objects/dictobject.c#L89" rel="nofollow noreferrer"><code>dict</code> source</a>:
<blockquote>
Preserving insertion order
It's simple for combined table. Since dk_entries is mostly append only, we can get insertion order by just iterating dk_entries.
</blockquote>
<a href="https://github.com/python/cpython/blob/ac75f6bdd4748b3378dd321f862d13aa1898f77a/Objects/dictobject.c#L17" rel="nofollow noreferrer">and</a>
<pre><code>layout:

+---------------+
| dk_refcnt |
| dk_log2_size |
| dk_kind |
| dk_usable |
| dk_nentries |
+---------------+
| dk_indices |
| |
+---------------+
| dk_entries |
| |
+---------------+
</code></pre>
<blockquote>
dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size).
DK_ENTRIES(dk) can be used to get pointer to entries.
</blockquote>
So, it appears to maintain an array. More digging would need to be done though to get more information, but that's a starting point.

Since Python 3.6 dictionaries keep insertion/key order.
I got into an argument with a colleague about HOW this is implemented. He says that this must have been achieved by using a list or some other collection to keep the key order. I suspect that there may be something more subtle at work.
I did the following comparisons:
<pre><code># Python 3.4.3

d = {1: 2, 2:3, 3:4}
od = OrderedDict(d)

print(sys.getsizeof(d)) # 288
print(sys.getsizeof(od)) # 1304
</code></pre>
<pre><code># Python 3.6.3

d = {1: 2, 2:3, 3:4}

print(sys.getsizeof(d)) # 240
</code></pre>
The size of <code>OderedDict</code> is enormous, I can absolutely see it using a list in the background for this task. However the size of regular dicts has not suffered any changes so I am skeptical about the fact that regular dicts also use lists to keep insertion order.
So HOW exactly do regular dicts in newer python versions keep key order?

How do Python dicts keep key order

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

因为Python3.6字典保持插入/键顺序。我和一位同事就如何实现这个问题进行了争论。他说，这一定是通过使用列表或其他集合来保持密钥顺序来实现的。我怀疑可能还有更微妙的事情在起作用。我做了以下比较：# Python 3.4.3d = {1: 2, 2:3, 3:4}od = OrderedDict(d)print(sy...

问Python如何保持键顺序？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Python如何保持键顺序？EN