内容简介:根据但有的时候我们可能会对哈希表中 Key 的插入顺序感兴趣,这时有经验的 Python 工程师就会用
现象
根据 哈希表 的定义,以及之前简单实现过的一个字典数据结构,当 Key 被插入哈希表后,哈希表根据散列函数求出的值来安排这个 Key 所在的位置,所以当我们遍历哈希表的时候, Key 的顺序是不确定的,因此 码农 在使用哈希表这个数据结构的时候,是不应该依赖于 Key 的插入顺序来达到某些目的的。
但有的时候我们可能会对哈希表中 Key 的插入顺序感兴趣,这时有经验的 Python 工程师就会用 collections
中的 OrderedDict
来保持插入 Key 的顺序。
>>> d1 = {} >>> d1['a'] = 1 >>> d1['b'] = 2 >>> d1['c'] = 3 >>> d1['d'] = 4 >>> d1['e'] = 5 >>> d1 {'b': 2, 'd': 4, 'c': 3, 'a': 1, 'e': 5} >>> from collections import OrderedDict >>> d2 = OrderedDict() >>> d2['a'] = 1 >>> d2['b'] = 2 >>> d2['c'] = 3 >>> d2['d'] = 4 >>> d2['e'] = 5 >>> d2 OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]) >>>
d1
是一个普通的字典实例,我们按照 abcde 的顺序插入 Key 之后,打印 d1 显示的是乱序的,这符合我们对哈希表的理解, d2
是一个 OrderedDict
实例,同样按 abcde 的顺序插入,从输出结果我们能看到它记忆了插入的顺序。那么问题来了,它是如何做到的?
原理
还是去源码中一探究竟,找到 Python 3 的 OrderedDict 实现
,不难发现,在继承 了自身的 dict 之后,类中还声明了一个
循环双向链表 self.__root
作为自己的属性,用另一个
dict 结构 self.__map
来存储 Key 到链表节点的对应关系,这样在更新或删除一个已有 Key 的时候,能在常数时间内完成对双向链表的操作。这几个数据结构的关系如下所示,注意 self.__root
总是指向双向链表的头部。
这样在遍历 OrderedDict
的时候,直接过一遍循环双向链表即可。
但类变得复杂了,相应的操作也会复杂起来,但上述的两种数据结构的结合,仍然能够做到对字典示例常数级操作。查询( __getitem__
)操作比较直观,可以通过调用父类的函数来完成。下面重点记录插入和删除操作是如何进行的。
插入
插入操作调用魔术方法 __setitem__
,当 Key 存在时,直接调用父类函数,复杂的情况是当 Key 不存在的时候,不仅需要把键值对放到哈希表中,还要同步更新 self.__map
和 self.__root
。
self.__root.prev
删除
删除操作调用 __delitem__
self.__map
显然,关于有顺序的哈希表,核心是对循环双向链表的操作,而链表的插入删除都是常数级操作,又用了一个 dict
来保证查询的常数级操作,所以既能记录 Key 插入的顺序,又能保证操作的时间复杂度。
但是。。。
在 Python 3.7
的发布中,官宣了 Python 原生的 dict
就能保证 Key 的插入顺序。
The insertion-order preservation nature of dict objects is now an official part of the Python language spec.
这是否就意味着 OrderedDict
变得多余了呢? StackOverflow 上有个 讨论
列出了 Python 3.7 中原生 dict
与 OrderedDict
的区别,主要有两条。
-
OrderedDict 支持对 Key 的顺序有关的操作,比如说把某个 Key 挪到头部或者尾部,逆序给出 Key 的序列(这个特性在 Python 3.8 中加到了原生
dict
中)等 -
OrderedDict 比较的时候会把 Key 的插入顺序考虑进去,而 dict 不会,比如说
>>> from collections import OrderedDict >>> OrderedDict([(1,1), (2,2)]) == OrderedDict([(2,2), (1,1)]) False >>> dict([(1,1), (2,2)]) == dict([(2,2), (1,1)]) True
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- c# – 实体框架以错误的顺序插入子对象
- 灵机一动之优雅实现用例顺序插入
- OrderedDict 是如何保证 Key 的插入顺序的
- MySQL 死锁套路:唯一索引下批量插入顺序不一致
- HashMap为何从头插入改为尾插入
- ViewGroup 默认顺序绘制子 View,如何修改?什么场景需要修改绘制顺序?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。