python3.7的字典是有序的

• 2020 年 1 月 2 日
• 筆記

python3.7的字典是有序的

旧结构

python3.7之前的字典结构，经典粗暴的hash表实现方式，这样的话每次hash表的扩容和缩容都可能导致hash值的改变。

hash表容量更新的前后，它的键之间的相对顺序是会变化的，因此字典的元素是无序的。旧结构类似下面

--+-------------------------------+    | 哈希值 (hash)  键 (key)  值 (value)  --+-------------------------------+  0 |    hash0      key0    value0  --+-------------------------------+  1 |    hash1      key1    value1  --+-------------------------------+  2 |    hash2      key2    value2  --+-------------------------------+  . |           ...  __+_______________________________+

新结构

Indices  ----------------------------------------------------  None | index0 | None | None | index2 | None | index1 ...  ----------------------------------------------------    Entries  --------------------  hash0   key0  value0  ---------------------  hash1   key1  value1  ---------------------  hash2   key2  value2  ---------------------          ...  ---------------------

新结构由 Indices(索引，数组实现) 和 Entries(实体，PyDictObject类型) 两种结构组成。

• 当插入一个数据时，先计算数据对应的hash值并映射成 Indices 数组的一个下标，没有冲突的话就将另一个值 Entries_index(暂时这么叫吧) 填入Indices数组中下标对应的位置。并在Entries后面追加一行记录，类似 hash值, key值, value值 。如果冲突的话可以用基本的解决冲突的办法，这里不赘述了。

这种方法，字典 增删改查的时间复杂度 会有以前的O(1) 变为O(2)，因为多了一步查找的过程。而且字典扩容和缩容时要按照Indices的顺序来保持字典始终有序。

但是至少有两个优化。

• 字典占用的内存变小了。旧的字典总会预留大于 1/3的容量的hash位置，防止hash碰撞过多影响效率。现在则不必预留。
• 字典有序了。

源码见： dictobject.h

dictobject.c

记于：2019/07/23