深入理解Python虚拟机：字典（dict）的实现原理及源码分析in这篇文章，我们主要介绍版本字典在python3.0早期的实现。目前的词典已经进行了部分优化，我们会在后面的文章中介绍。字典数据结构分析/*ma_values指针对于合并表为NULL*或指向PyObject*的数组对于拆分表*/typedefstruct{PyObject_HEADPy_ssize_tma_used;PyDictKeysObject*ma_keys;PyObject**ma_values;}PyDictObject;struct_dictkeysobject{Py_ssize_tdk_refcnt;Py_ssize_tdk_size;dict_lookup_funcdk_lookup；Py_ssize_tdk_usable；PyDictKeyEntrydk_entries[1];};typedefstruct{/*me_key的缓存哈希码。*/Py_hash_tme_hash;PyObject*me_key;PyObject*me_value;/*该字段只对组合表有意义*/}PyDictKeyEntry;上面各个字段的含义是：ob_refcnt，对象的引用计数。ob_type，对象的数据类型。ma_used，当前哈希表中的数据条数。ma_keys，指向键值对数组。ma_values，这个数组指向values，但是在cpython的具体实现中不一定要用到这个value，因为_dictkeysobject中的PyDictKeyEntry数组中的对象也可以存值，只有当所有的key都是strings时才会有这个value使用。在本文中，PyDictKeyEntry中的值主要用于讨论字典的实现，因此您可以忽略该变量。dk_refcnt，这个也是用来表示引用计数的，跟字典的视图有关，原理和引用计数类似，这里先忽略。dk_size，也就是哈希表的大小，必须是$2^n$，这样才能把模运算变成位与运算。dk_lookup，代表哈希表的查找函数，是一个函数指针。dk_usable，表示当前数组中有多少个键值对可用。dk_entries，哈希表，实际存放键值对的地方。整个哈希表的布局大致如下图所示：新建字典对象的功能比较简单。首先申请内存空间，然后进行一些初始化操作申请哈希表来存储键值对。staticPyObject*dict_new(PyTypeObject*type,PyObject*args,PyObject*kwds){PyObject*self;PyDictObject*d;断言（类型！=NULL&&类型->tp_alloc！=NULL）；//申请内存空间self=type->tp_alloc(type,0);如果（自我==NULL）返回NULL；d=(PyDictObject*)self;/*对象已被tp_alloc隐式跟踪*/if(type==&PyDict_Type)_PyObject_GC_UNTRACK(d);//因为还没有添加数据，哈希表中ma_used=0d->ma_used=0;//申请保存键值对的数组PyDict_MINSIZE_COMBINED为宏定义值8，表示哈希表数组的最小长度d->ma_keys=new_keys_object(PyDict_MINSIZE_COMBINED);//如果应用程序失败则返回NULLif(d->ma_keys==NULL){Py_DECREF(self);返回空值；}returnself;}//new_keys_object函数如下staticPyDictKeysObject*new_keys_object(Py_ssize_tsize){PyDictKeysObject*dk;Py_ssize_t我；PyDictKeyEntry*ep0;断言（大小>=PyDict_MINSIZE_SPLIT）；断言（IS_POWER_OF_2（大小））；//这是应用程序内存的位置。实际申请内存空间的大小是PyDictKeysObject的大小加上size-1PyDictKeyEntry的大小//这里你可能会有疑问为什么不是sizePyDictKeyEntry的大小，因为在结构体PyDictKeysObject中已经申请了一个PyDictKeyEntry对象dk=PyMem_MALLOC(sizeof(PyDictKeysObject)+sizeof(PyDictKeyEntry)*(size-1));如果(dk==NULL){PyErr_NoMemory();返回空值；}//下面是一些初始化操作dk_refcnt设置为1因为目前只有一个字典对象使用这个PyDictKeysObject对象DK_DEBUG_INCREFdk->dk_refcnt=1;dk->dk_size=尺寸；//哈希表的大小//下面这行代码主要表示哈希表中当前的状态，可以存储多少个键值对？在cpython实现中，允许2/3的数组空间存储数据。如果超过这个数，则需要扩容dk->dk_usable=USABLE_FRACTION(size);//#defineUSABLE_FRACTION(n)((((n)<<1)+1)/3)ep0=&dk->dk_entries[0];/*slot0的hash值被popitem使用，所以必须初始化*/ep0->me_hash=0;//将所有键值对初始化为NULLfor(i=0;idk_lookup=lookdict_unicode_nodummy;returndk;}哈希表扩容机制首先，我们了解下字典实现中哈希表的扩容机制。当我们继续向字典中添加新的数据时，字典中的数据很快就会达到数组长度的$\frac{2}{3}$，此时需要扩充。扩容后数组大小的计算方法如下：#defineGROWTH_RATE(d)(((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))新数组等于原键值对的个数乘以2加上原数组长度的一半。尺寸。创建新数组。将原哈希表中的数据添加到新数组中（即rehashing的过程）。具体实现代码如下：PyDictKeysObject*oldkeys;PyObject**旧值；Py_ssize_ti，旧尺寸；//下面代码的主要作用是计算2的最小整数次方可以大于等于minused/*找到最小的tablesize>minused。*/for(newsize=PyDict_MINSIZE_COMBINED;newsize<=minused&&newsize>0;newsize<<=1);如果(newsize<=0){PyErr_NoMemory();返回-1；}oldkeys=mp->ma_keys;oldvalues=mp->ma_values;/*分配一个新表。*///创建一个新数组mp->ma_keys=new_keys_object(newsize);如果（mp->ma_keys==NULL）{mp->ma_keys=oldkeys;返回-1；}if(oldkeys->dk_lookup==lookdict)mp->ma_keys->dk_lookup=lookdict;oldsize=DK_SIZE(oldkeys);mp->ma_values=NUL升;/*如果为空则没有可复制的东西，所以只返回*/if(oldsize==1){assert(oldkeys==Py_EMPTY_KEYS);DK_DECREF(旧键);返回0；}/*下面的主循环假设我们可以将refcount转移到新键*并且该值存储在me_value中。*在此处增加引用计数和复制值以补偿*这种（调整拆分表的大小）应该相对少见*/if(oldvalues!=NULL){for(i=0;idk_entries[i].me_key);oldkeys->dk_entries[i].me_value=oldvalues[i];}}}/*Mainloop*///将原始数字组当中的元素加入到新的数字组当中for(i=0;idk_entries[i];如果(ep->me_value!=NULL){assert(ep->me_key!=dummy);insertdict_clean(mp,ep->me_key,ep->me_hash,ep->我的价值）；}}//更新当前哈希表可以插入多少数据mp->ma_keys->dk_usable-=mp->ma_used;if(oldvalues!=NULL){/*NULLoldkeys中的me_value槽，以防它被共享*/for(i=0;idk_entries[i].me_value=NULL;断言（旧值！=空值）；free_values（旧值）；DK_DECREF(旧键);}else{assert(oldkeys->dk_lookup!=lookdict_split);if(oldkeys->dk_lookup!=lookdict_unicode_nodummy){PyDictKeyEntry*ep0=&oldkeys->dk_entries[0];对于(i=0;idk_refcnt==1);DK_DEBUG_DECREFPyMem_FREE（旧密钥）；}return0;}字典插入数据我们不断地往字典中添加数据，在插入数据的时候，很有可能会遇到哈希冲突。字典中哈希冲突的处理方法与集合中哈希冲突的处理方法基本相同。都使用开发地址方式，但这种开放地址方式相对实现。比较复杂，具体过程如下：staticvoidinsertdict_clean(PyDictObject*mp,PyObject*key,Py_hash_thash,PyObject*value){size_ti;size_t扰动；PyDictKeysObject*k=mp->ma_keys;//首先获取mask的值size_tmask=(size_t)DK_SIZE(k)-1;PyDictKeyEntry*ep0=&k->dk_entries[0];PyDictKeyEntry*ep;i=散列和掩码；ep=&ep0[i];for(perturb=hash;ep->me_key!=NULL;perturb>>=PERTURB_SHIFT){//这里是处理哈希冲突的方法i=(i<<2)+i+perturb+1;ep=&ep0[i&面具];}assert(ep->me_value==NULL);ep->me_key=密钥；ep->me_hash=散列；ep->me_value=value;}总结在本文中，我将简单介绍一下cpython中内部字典的实现机制。整个字典的实现机制相当复杂。本文只讲整个字典的一小部分实现。主要设计了字典和相关数据结构的内存布局。最重要的是字典的创建、扩展和插入。对理解哈希表的结构还是很有帮助的！！！本文是深入理解python虚拟机系列文章之一。文章地址为：https://github.com/Chang-LeHung/dive-into-cpython更多精彩内容合集可访问：https://github.com/Chang-LeHung/CSCore关注公众号：一个废物研究僧，现在深入了解计算机（Java、Python、计算机系统基础、算法和数据结构）
