python3.7的字典是有序的

iamyoung001 发布于2019-07-31 11:30 / 3190人阅读

摘要：表容量更新的前后，它的键之间的相对顺序是会变化的，因此字典的元素是无序的。而且字典扩容和缩容时要按照的顺序来保持字典始终有序。旧的字典总会预留大于的容量的位置，防止碰撞过多影响效率。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45229.html

Python 有序字典简介

摘要：有序字典简介示例有序字典和通常字典类似，只是它可以记录元素插入其中的顺序，而一般字典是会以任意的顺序迭代的。有序字典-OrderedDict简介示例有序字典和通常字典类似，只是它可以记录元素插入其中的顺序，而一般字典是会以任意的顺序迭代的。参见下面的例子: import collections print Regular dictionary: d = {} d[a] = ...

DrizzleX 2019-07-31 10:54 评论0 收藏0
Python中的字典到底是有序的吗

摘要：并且中会显示，的版本在中已经不再支持了。接下来再看下以上版本的效果以版本为例从上图可以看出，在新的版本中，针对的存储已经变为有序，在遍历和打印的时候，会按照存储的顺序进行取值。再补充一点之前介绍到，在字典中，是唯一的。之前写了文章介绍python中的列表和字典，在文章中描述到了python...

aervon 2021-09-28 09:36 评论0 收藏0
跟着大彬读源码 - Redis 6 - 对象和数据类型（下）

摘要：哈希对象哈希对象的可选编码分别是和。编码的哈希对象编码的哈希对象使用压缩列表作为底层实现。关于哈希编码转换的函数，可以参考，源码如下是原始对象，是目标编码。对应源码如下对象元素数量为，或者总结哈希对象有和编码。继续撸我们的对象和数据类型。上节我们一起认识了字符串和列表，接下来还有哈希、集合和有序集合。 1 哈希对象哈希对象的可选编码分别是：ziplist 和 hashtable。...

YFan 2019-08-06 13:45 评论0 收藏0
Python字典小结

摘要：我们用函数，来简单快捷地创建这个字典输出结果与原先代码一致。示例代码如下版本为无序字典有序字典输出的结果为无序字典有序字典默认字典是内建类的一个子类，第一个参数为属性提供初始值，默认为。字典（dict）结构是Python中常用的数据结构，笔者结合自己的实际使用经验，对字典方面的相关知识做个小结，希望能对读者一些启发~ 创建字典常见的字典创建方法就是先建立一个空字典，然后逐一...

BoYang 2019-07-31 11:13 评论0 收藏0