Python字典的顺序
Python字典的顺序
从Python 3.6开始，字典是有序的。它被描述为CPython的一个实现细节，而不是语言特性。文档中指出：
dict()现在使用了一种“紧凑”表示，这是由PyPy开创的。与Python 3.5相比，新的dict()的内存使用量减小了20%至25%。这也实现了PEP 468（保留函数中**kwargs的顺序）的要求。这种新实现的有序性被认为是一种实现细节，不能依赖它（这可能会在将来发生变化，但是在改变语言规范以要求所有当前和未来的Python实现都遵守有序语义之前，希望将这种新的dict实现保留在语言中几个版本；这也有助于与仍然使用随机迭代顺序的旧版本的语言保持向后兼容，例如Python 3.5）。（由INADA Naoki在问题27350中提供。这个想法最初是由Raymond Hettinger提出的。）
新的字典实现如何在保留元素顺序的同时提供更好的性能？
2017年12月更新：对于Python 3.7，字典保留插入顺序是被保证的。
Python 3.6+引入了有序字典（OrderedDict）的概念，它会记住插入的顺序。然而，这一特性在Python 3.6中被认为是实现细节，所以如果要在其他Python实现中（以及其他有序行为）保证插入顺序，就需要使用OrderedDict。
在Python 3.7中，有序字典成为了一个确保的语言特性，而不仅仅是实现细节。这意味着其他Python实现也必须提供一个有序字典，如果他们希望成为Python 3.7的符合实现。
Python 3.6中的字典实现相比之前的版本在性能上有所提升，并且能够保持元素的顺序。这是通过维护两个数组实现的。
第一个数组是dk_entries，它按插入的顺序保存字典的条目。这是一个仅追加的数组，新项目始终在末尾插入，从而实现了保持顺序的功能。
第二个数组是dk_indices，它保存了dk_entries数组的索引，用于查找对应的条目。这个数组充当了哈希表的作用。当键被哈希时，它会导致dk_indices中的一个索引，并通过索引dk_entries获取对应的条目。由于只保存索引，因此这个数组的类型取决于字典的整体大小。
与以前的实现相比，这种新的实现方式更加紧凑，因为它只存储了必要的条目（即已插入的条目），并且保持了一个只占用2/3 * dk_size空间的稀疏数组。这种变化使得字典的内存需求大大降低。
当删除一个条目时，对应的索引会被替换为一个特殊的值DKIX_DUMMY（值为-2），并且条目数组中的条目会被替换为NULL。当进行插入操作时，新的值会被追加到条目数组中。当索引填满超过2/3阈值时，会执行调整数组大小的操作。
在Python 3.7中，创建字典时的顺序是有保证的。例如，创建一个字典a = {'one': 1, 'two': 2}，在迭代时，'one'将始终在'two'之前。
总体而言，Python的字典性能在实际应用中得到了提升，特别是由于紧凑的实现方式引入的内存效率提升。
对于以前的版本的Python，可以使用collections模块中的OrderedDict来实现有序字典的功能。可以根据Python的版本来导入不同的模块，例如：
import sys
if sys.version_info < (3, 6):
from collections import OrderedDict as dict
else:
dict = dict
总之，Python 3.6+引入了有序字典的概念，并通过维护两个数组的方式实现了有序字典的插入顺序。这一改进提高了字典的性能和内存效率，在Python 3.7中，有序字典成为了一个确保的语言特性。