Hi~今天给大家说说为什么python3.6之后字典是有序的，效率更高？在Python3.5（含）之前，无法保证字典的顺序。先将键值对A插入字典，再将键值对B插入字典。但是当你打印字典的Keys列表时，你会发现B可能在A的Front。但是从Python3.6开始，字典是有序的。你先插入键值对A，再插入键值对B，那么当你打印Keys列表的时候，你会发现B在A的后面。不仅如此，从Python3.6开始，下面的三个遍历操作比Python3.5之前更高效：python">forkeyindictionaryforvalueindictionary.values()forkey,valueindictionary.items()从Python3.6开始，字典占用的内存空间大小，取决于字典中键值对的个数，只有原来的30%~95%。Python3.6是如何优化字典的？为了解释这个问题，我们需要讲一讲，Python3.5之前（含），词典的基本原理。当我们初始化一个空字典时，CPython底层会初始化一个二维数组，它有8行3列，如下图所示：my_dict={}'''此时的内存图[[---,---,---],[---,---,---],[---,---,---],[---,---,---],[---,---,---],[---,---,---],[---,---,---],[---,---,---]]'''现在，我们向字典中添加一条数据：my_dict['name']='kingname''''此时的内存图[[---,---,---],[---,---,---],[---,---,---],[---,---,---],[---,---,---],[1278649844881305901,指向名称的指针,指向kingname的指针],[---,---,---],[---,---,---]]'''这里解释一下为什么添加了键值对后，内存变成了这样：首先我们调用Python的hash函数计算字符串name在当前运行时的hash值：>>>hash('name')1278649844881305901特别注意，我这里强调“当前运行时”，因为Python自带的hash函数和Hash不同我们传统上认为的功能。Python自带的hash函数计算出来的值只能保证每次运行时不变，但是当你关闭Python再重新打开时，它的值可能会发生变化，如下图所示：在某个运行时，该值hash('name')的结果是1278649844881305901，现在我们要把这个数取余8：>>>1278649844881305901%85余数是5，然后放到刚刚初始化的二维数组中，有下标5.由于name和kingname是两个字符串，所以C语言底层会用两个字符串变量来存储这两个值，然后得到它们对应的指针。因此，对于我们的二维数组中下标为5的那一行，第一个值为name的哈希值，第二个值为字符串name所在内存的地址（指针为内存地址），而第三个值是字符串kingname所在内存的地址。现在，我们插入两个键值对：my_dict['age']=26my_dict['salary']=999999'''此时的内存图[[-4234469173262486640，薪水指针，指向999999]，[1545085610920597121,指向执行年龄的指针,指向26],[---,---,---],[---,---,---],[---,---,---],[1278649844881305901,指向name的指针,指向kingname的指针],[---,---,---],[---,---,---]]'''那么如何字典读取数据？首先假设我们要读取年龄对应的值。此时Python先计算出当前运行时age对应的Hash值：>>>hash('age')1545085610920597121现在将这个hash值取余8：>>>1545085610920597121%81余数为1，那么在二维数组中，下标为1的行就是需要的键值对。直接返回这一行第三个指针对应的内存中的值，也就是age对应的值26。当你要遍历字典的键时，Python底层会遍历二维数组。如果当前行有数据，则返回Key指针对应的内存中的值。如果当前行没有数据，则跳过它。所以总是遍历整个二进制数组的每一行。每行三列，每列占用8bytes内存空间，所以每行会占用24bytes内存空间。由于Hash值的余数可大可小，所以字典的key并不是按照插入的顺序存储的。注意这里我省略了两点和本文关系不大：1.开放寻址，当两个不同的Key散列，然后取8的余数，余数可能相同。这时，为了不覆盖已有的值，Python会使用开放寻址技术，寻找新的位置来存放新的键值对。2.当字典中键值对的个数超过当前数组长度的2/3时，数组就会扩容，8行变成16行，16行变成32行。长度改变后，原来的余数位置也会改变。此时需要移动原位置的数据，导致插入效率低下。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的指针，指向executekingname的指针]]'''为什么内存会变成这样？我们一步步来看：在当前运行时，字符串name的hash值为-5954193068542476671，这个值与8的余数为1：>>>hash('name')-5954193068542476671>>>hash('name')%81因此，我们将索引一维数组中下标1的位置改为0。这里的0是什么意思？0是二进制数组条目的索引。现在entries中只有一行，就是我们刚刚添加的键值对的三个数据：name的hash值，name的指针和kinganme的指针。所以indices中填入的数字0就是我们刚刚插入到二位数组中的键值对数据的行索引。好了，现在我们再插入两条数据：my_dict['address']='xxx'my_dict['salary']=999999'''此时的内存图indices=[1,0,None,None,None,None,2,None]entries=[[-5954193068542476671,指向name的指针,指向executekingname的指针],[9043074951938101872,指向地址的指针,指向xxx的指针],[7324055671294268046,指向salary的指针,指向999999的指针]]'''现在如果我想读取数据怎么办？如果我要读取salary的值，那么先计算salary的hash值，并将这个值取8余数：>>>hash('salary')7324055671294268046>>>hash('salary')%86then我会去读取索引为6的值。这个值是2。然后读取entries中下标为2的那一行的数据，也就是salary对应的数据。在这种新的方式中，当我要插入新数据时，我总是只在条目的后面添加数据，这样插入的顺序就可以得到保证。当我们要遍历字典的Keys和Values时，直接遍历entry即可。里面的每一行都是有用的数据，没有跳过，减少了遍历的次数。老办法，当二维数组有8行时，即使有效数据只有3行，它占用的内存空间还是824=192字节。但是使用新方法，如果只有三行有效数据，那么entry就只有3行，占用324=72字节的空间，而且由于索引只是一个一维数组，所以只占用8个字节，所以一共占用80个字节。字节。内存占用只有原来的41%。
