Python3.6之后的字典有序了！

之前面试时候面试官问python几大数据类型是否有序。我说了python从3.6之后字典从无序变成有序了，因为我记得我看过。但是面试官就反复说让我再下去看看，因为对原理没有了解的特别透彻，就也没有说服人家。于是下来了解了一下原理，记录一下。

python3.6后字典的变化

Python3.5（含）以前，字典是不能保证顺序的，键值对A先插入字典，键值对B后插入字典，但是当打印字典的Keys列表时，就会发现B可能在A的前面。

但是从Python3.6开始，字典变成有序的了。键值对A先插入字典，键值对B后插入字典，当打印字典的Keys列表时，就会发现B在A的后面。

不仅如此，从Python3.6开始，下面三种遍历操作，效率要高于Python3.5之前：

for key in dict
for value in dict.values()
for key, value in dict.items()

且从Python3.6开始，字典占有内存空间的大小，视字典里面键值对的个数，只有原来的30%～95%。

Python3.5（含）之前，字典的底层原理

字典的插入

当我们初始化一个空字典的时候，CPython的底层会初始化一个二维数组，这个数组有8行，3列，如下：

my_dict = {}

'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---]]
'''

现在，我们往字典里面添加一个数据：

my_dict['name'] = 'kingname'

'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指针, 指向kingname的指针],
[---, ---, ---],
[---, ---, ---]]
'''

那为什么添加一个键值对以后，内存变成这个样子呢？ 首先我们调用Python的hash函数，计算name这个字符串在当前运行时(Python自带的这个hash函数计算出来的值，只能保证在每一次运行的时候不变，但是当你关闭Python再重新打开，那么它的值就可能会改变)的hash值：

>>> hash('name')
1278649844881305901

假设在某一次运行时里面，hash('name')的值为1278649844881305901。现在我们要把这个数对8取余数，余数为5。那么就把它放在刚刚初始化的二维数组中，下标为5的这一行，由于name和kingname是两个字符串，所以底层C 语言会使用两个字符串变量存放这两个值，然后得到他们对应的指针。于是，我们这个二维数组下标为5的这一行，第一个值为name的hash值，第二个值为name这个字符串所在的内存的地址（指针就是内存地址），第三个值为kingname这个字符串所在的内存的地址。

每一行有三列，每一列占用8byte的内存空间，所以每一行会占有24byte的内存空间。

字典的读取

读取指定键对应的值

my_dict['age'] = 26
my_dict['salary'] = 99999

'''
此时的内存示意图
[[-4234469173262486640, 指向salary的指针, 指向999999的指针],
[1545085610920597121, 执行age的指针, 指向26的指针],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指针, 指向kingname的指针],
[---, ---, ---],
[---, ---, ---]]

假设我们要读取age对应的值。那么，Python会先计算在当前运行下，age对应的Hash值，然后对hash值取余数。余数为1，那么二维数组里面，下标为1的这一行就是需要的键值对。直接返回这一行第三个指针对应的内存中的值，即26。

遍历字典的Key

Python底层会遍历这个二维数组，如果当前行有数组，那么就返回Key指针对应的内存里的值。如果没有，则跳过。所以总是会遍历整个二位数组的每一行。

由于hash值取余数以后，余数可大可小，所以字典的Key并不是按照插入的顺序存放的。

Python3.6后，字典的底层原理

字典的插入

在Python3.6以后，字典的底层数据结构发生了变化，现在当你初始化一个空的字典后，它在底层是这样的：

my_dict = {}

'''
此时的内存示意图
indices = [None, None, None, None, None, None, None, None]
entries = []
'''

Python单独生成了一个长度为8的一维数组。然后又生成了一个空的二维数组。 现在，我们往字典里面添加一个键值对：

my_dict['name'] = 'kingname'

'''
此时的内存示意图
indices = [None, 0, None, None, None, None, None, None]
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针]]
'''

那为什么内存会变成这个样子呢？

首先，我们获取了‘name’当前运行时的hash值为-5954193068542476671，此值取余为1。所以，我们把indices这个一维数组里，下标为1的位置修改为0。这个0代表的是二维数组entries的索引。

老的方式，当二维数组有8行的时候，即使有效数据只有3行，但它占用的内存空间还是8*24=192bytes。但使用新的方式，如果只有三行有效数据，那么entries也只有3行，占用的空间为3*24=72bytes，而indices由于只是一个一维的数组，只占有8bytes，所以一共占有80bytes。内存占有只有原来的41%。

字典的读取

读取指定键对应的值

my_dict['address'] = 'xxx'
my_dict['salary'] = 999999

'''
此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针],
          [9043074951938101872, 指向address的指针，指向xxx的指针],
          [7324055671294268046, 指向salary的指针, 指向999999的指针]
         ]
'''

假设我要读取salary的值，那么首先计算salary的hash值，以及hash值对8的余数，余数为6。然后我就去读indices下标为6的值，这个值为2。然后再去读entries里，下标为2的这一行数据，即salary对应的数据。

遍历字典

新的方式，当我要插入新的数据的时候，始终只是往entries的后面添加数据，这样就能保证插入的顺序。当我们要遍历字典的Keys和Values时，直接遍历entries即可。里面每一行都是有用的数据，不存在跳过的情况，减少了遍历的个数。

总结

在3.5以前

3.6以后