python3.7的字典是有序的
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
记于：2019/07/23
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录