简介：Python 3.6及以后版本的字典设计为有序，以及在某些情况下效率更高，主要归功于“Preservation of Insertion Order”技术的引入。这种技术利用了散列表的插入顺序信息，使得字典在实现中能够保留元素插入的顺序，并在某些遍历操作上具有更高的效率。本文将深入解释这一技术及其对Python字典的影响。
Python 3.6引入了一项重大改进，使得字典（dict）成为有序的，并在某些情况下效率更高。这一变化源于“Preservation of Insertion Order”技术的采用。该技术利用散列表（hash table）的插入顺序信息，使得字典能够保留元素插入的顺序。这一特性不仅使得字典的遍历操作更为高效，还为开发者提供了更为一致和可预测的字典行为。
在Python 3.5（含）以前，字典并不是按照插入顺序保留元素的。这意味着，如果你先插入键值对A，后插入键值对B，当你打印字典的Keys列表时，B可能在A的前面。这种不确定性给开发者带来了困扰，因为他们无法预测字典的行为。
然而，从Python 3.6开始，字典设计为有序。这意味着当你先插入键值对A，后插入键值对B时，当你打印Keys列表时，B会出现在A的后面，从而保持了插入顺序。此外，由于该技术的引入，从Python 3.6开始，以下三种遍历操作的效率要高于Python 3.5之前：
for key in dictionaryfor value in dictionary.values()for key, value in dictionary.items()那么，Python 3.6到底对字典做了什么优化呢？要理解这个问题，我们需要探讨在Python 3.5（含）之前字典的底层原理。
在早期版本的Python中，字典的实现基于哈希表（hash table）。哈希表是一种数据结构，用于存储键值对，并利用哈希函数将键映射到存储位置。然而，传统的哈希表并不保留元素的插入顺序。为了解决这个问题，Python 3.6引入了一种新的数据结构——有序字典。
有序字典在传统哈希表的基础上增加了一个双向链表。这个链表记录了元素的插入顺序。当新的键值对被插入时，它会被添加到链表的末尾。这样，无论是按照键还是值的顺序遍历字典，都可以通过遍历这个链表来获得正确的结果。
此外，由于链表的加入，字典的查找和删除操作并不会像传统的哈希表那样发生冲突。因此，有序字典在性能上要优于传统的哈希表。
值得注意的是，有序字典的实现并没有改变原有的哈希表实现。而是将其作为底层数据结构的一部分。这意味着有序字典仍然具有哈希表的特性，如O(1)的平均查找时间复杂度。
总之，Python 3.6及以后版本的字典之所以有序且效率更高，得益于“Preservation of Insertion Order”技术的引入。这一技术利用散列表的插入顺序信息，使得字典能够保留元素插入的顺序，并提高了某些遍历操作的效率。这种改进不仅使得字典的行为更加一致和可预测，还为开发者提供了更为高效的数据处理能力。