python dict怎么实现的

Python中dict对象是表明了其是一个原始的Python数据类型，按照键值对的方式存储，其中文名字翻译为字典，顾名思义其通过键名查找对应的值会有很高的效率，时间复杂度在常数级别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教程栏目进行学习！

Atas ialah kandungan terperinci python dict怎么实现的. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!