个人网站建设简历,网络营销论文范文,中文域名值得注册吗,北京有实力的软件开发公司以下内容是针对#xff1a;python源码剖析中的第五章——python中Dict对象 的读书笔记(针对书中讲到的内容进行了自己的整理#xff0c;并且针对部分内容根据自己的需求进行了扩展)一、Dict的用法Dict的对象在使用到了所谓的关联关系的时候#xff0c;就是通过key-value的形…以下内容是针对python源码剖析中的第五章——python中Dict对象 的读书笔记(针对书中讲到的内容进行了自己的整理并且针对部分内容根据自己的需求进行了扩展)一、Dict的用法Dict的对象在使用到了所谓的关联关系的时候就是通过key-value的形式能够通过key值快速定位到某个value值Dict的相关操作如下class mydict(object):def __init__(self):self.d {}def fuzhi(self):self.d {2:23, 3:34}def fuzhi2(self):self.d[1] 1self.d[str] 123self.d[may] 234self.d[may] 789def delkey(self):del(self.d[1]) #删除key时key值必须存在于dict中否则会报出 KeyErrorself.d.pop(str)def bianli(self):for (k,v) in self.d.items():print k, vdef getkeysandv(self):print self.d.keys() #获取当前dict中的所有key值#获取某个元素值print self.d.get(345) #若key不存在则返回默认返回值Noneprint self.d.get(123, -1) #若key不存在则返回自定义的返回值-1print self.d.get(may) #若key值存在则返回对应的valuedef setkeyexcept(self):self.d[[1,2,3]] 123 #可变对象不能作为key会提示TypeError: unhashable type: list 的类似错误二、Dict的存储实现原理python中的dict对象也即PyDictObject对象因为对搜索的效率要求很高所以选择了散列表(hash table)因为在最优情况下散列表能够提供O(1)的搜索效率因此这里就能想到在leetcode上面刷的题目中很多通过list形式可以实现的为了降低时间复杂度可以用hash的方式选择dict对象存储(当然具体问题要具体分析)散列表的基本思想是通过一定的函数将需要搜索的键值映射为一个整数根据这个整数作为索引去访问某片连续的内存区域。用于映射的函数称为映射函数映射所产生的值称为散列值(hash value)。散列函数对搜索效率有直接的决定性作用。在使用散列函数将不同的值可能映射到相同的散列值这个时候就需要冲突解决(装载率大于2/3时冲突的概率就会大大增加)冲突解决在python中使用的是开放定址法就是通过一个二次探测函数f计算下一个位置一直到找到下一个可用的位置为止在这个过程中会到达多个位置这些位置就形成了一个“冲突探测链”这个冲突探测链在查找某个元素的时候起到重要作用所以在删除某个位置上的元素不能直接将这个位置的内容删除如果删除的话则导致后续依赖于这个位置的其他值就都无法寻找到了所以只能进行“伪删除”(通过给元素设置状态dummy态表示没有存储具体的值但是还会用到的废弃态)具体的PyDictObject对象中会存在每一个元素元素的定义是typedef struct{Py_ssize_t me_hash;PyObject *me_key;PyObject *me_value;}PyDictEntry;每一个元素有三种状态分别是unused、active、dummy状态具体含义unusedme_keyNull,me_valueNullactiveme_key!Null,me_value!Nulldummyme_keydummy,me_valueNullPyDictObject对象的定义#define PyDict_MINSIZE 8typedef struct _dictobject PyDictObject;struct _dictobject{PyObject_HEADPy_ssize_t ma_fill; //元素个数: activedummyPy_ssize_t ma_used; //元素个数: ActivePy_ssize_t ma_mask;PyDictEntry *ma_table;PyDictEntry *(*ma_lookup) (PyDictEntry *mp, PyObject *key, long hash);PyDictEntry ma_smalltable[PyDict_MINSIZE];}其中各个字段的含义如下ma_fill域中维护着从PyDictObject对象创建开始直到现在为止所有曾经及正在处于active态的entry个数ma_used域中维护着当前正处于Active态的entry个数ma_smalltable的PyDictEntry的数组表示的是当创建一个PyDictObject对象的时候至少创建PyDict_MINISIZE个entry被创建(这个数量在程序中定义是8个这个数量是经过长期的经验所得来的值)ma_table是指向一块区域的如果entry的数量不超过8个那么这个指针就指向了ma_smalltable的地址如果超过了8个就需要申请一块大的内存并且ma_table指向这块大的内存三、Dict的操作实现原理(包括插入、删除、以及缓冲池等)首先介绍PyDictObject对象的元素搜索策略有两种搜索策略分别是lookdict和lookdict_stringlookdict_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)根据所采用的探测函数获得探测链上的下一个待检查的entryb)检查到一个unused态的entry表明搜索失败如果freeslot不为空则返回freeslot否则返回unused态的entryc)检查entry的key与所搜索的key的引用是否相同相同则搜索成功返回entryd)检查entry的key与所搜索的key的值是否相同相同则搜索成功返回entrye)遍历过程中发现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对象的时候如果缓冲池中有则可以直接从缓冲池中取出使用
