python dict怎么实现的

发布时间:2022-05-15 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了python dict怎么实现的脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Python中dict对象是表明了其是一个原始的Python数据类型,按照键值对的方式存储,其中文名字翻译为字典,顾名思义其通过键名查找对应的值会有很高的效率,@R_477_1304@在常数级别O(1).

dict底层实现(推荐学习:Python视频教程)

python2中,dict的底层是依靠哈希表(Hash Table)进行实现的,使用开放地址法解决冲突.

所以其查找的时间复杂度会是O(1).

Dict的操作实现原理(包括插入、删除、以及缓冲池等)

首先介绍:PyDictObject对象的元素搜索策略:

有两种搜索策略,分别是lookdict和lookdict_string,lookdict_string就是lookdict在对于PyStringObject进行搜索时的特殊形式,那么通用的搜索策略lookdict的主要逻辑是:

(1)对第一个entry的查找:

a)根据hash值获得entry的索引

b)若entry处于unused态,则搜索结束;若entry所指向的key与搜索的key相同,则搜索成功

c)若当前entry处于dummy态,则设置freeslot(这里的freeslot是可以返回作为下一个立即可用的地址来存储entry)

d)检查Active态的entry,若其key所指向的值与搜索的值相同,则搜索成功

(2)对剩余的探测链中的元素的遍历查找:

a)根据所采用的探测函数,获得探测链上的下一个待检查的entry

b)检查到一个unused态的entry,表明搜索失败:

如果freeslot不为空,则返回freeslot;否则返回unused态的entry

c)检查entry的key与所搜索的key的引用是否相同,相同则搜索成功,返回entry

d)检查entry的key与所搜索的key的值是否相同,相同则搜索成功,返回entry

e)遍历过程中,发现dummy态的entry,且freeslot未设置,则设置freeslot

接下来是:PyDictObject对象的元素插入与删除的策略:

需要首先用到搜索策略,搜索成功,则直接将值进行替换,搜索失败,返回unused态或dummy态的entry,设置key、value和hash值,并且根据目前插入的元素情况进行ma_table的大小的调整(调整的依据就是装载率,根据是否大于2/3来进行调整);删除也是类似,先计算hash值,然后搜索相应的entry,搜索成功,删除entry中维护的元素,将entry从Active态修改为dummy态

在PyDictObject的实现过程中,会用到缓冲池,在PyDictObject对象被销毁的时候,才开始接纳被缓冲的PyDictObject对象,定义的缓冲池可接纳的对象数量是80个,创建新PyDictObject对象的时候,如果缓冲池中有,则可以直接从缓冲池中取出使用

更多Python相关技文章,请访问Python教程栏目进行学习!

以上就是python dict怎么实现的的详细内容,更多请关注脚本宝典其它相关文章!

脚本宝典总结

以上是脚本宝典为你收集整理的python dict怎么实现的全部内容,希望文章能够帮你解决python dict怎么实现的所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: