字典是通过键来索引的，所以字典也可以看成是两个相互关联的数组。下面我们尝试向字典中添加3个key/value（键/值）对：>>>d={'a':1,'b':2}>>>d['c']=3>>>d{'a':1,'b':2,'c':3}可以按如下方式访问这些值：>>>d['a']1>>>d['b']2>>>d['c']3>>>d['d']Traceback(mostrecentcalllast):File"",line1,inKeyError:'d'因为键'd'确实不存在，因此引发KeyError异常。哈希表（Hashtables）在Python中，字典是通过哈希表来实现的。也就是说字典是一个数组，数组的索引是key经过hash函数处理后得到的。散列函数的目的是将键均匀分布在数组中。由于不同的键可能具有相同的哈希值，因此可能会发生冲突，高级哈希函数可以最大限度地减少冲突的次数。Python不包含这种高级哈希函数，几个重要的哈希函数（用于处理字符串和整数）通常是常规类型：>>>map(hash,(0,1,2,3))[0,1,2,3]>>>map(hash,("namea","nameb","namec","named"))[-1658398457,-1658398460,-1658398459,-1658398462]在接下来的页面中，我们只考虑使用字符串作为键的情况。在Python中，用于处理字符串的哈希函数是这样定义的：arguments:stringobjectreturns:hashfunctionstring_hash:ifhashcached:returnitsetlentostring'slengthinitializevarppointingto1stcharofstringobjectsetxtovaluepointedbypleftshiftedby7bitswhilelen>=0:setvarxto(1000003*x)xorvaluepointedbypincrementpointerpsetxtoxxorlengthofstringobjectcachexasthehashsowedon'tneedtocalculateitagainreturnxasthehash如果在Python中运行hash('a')，后台会执行string_hash()函数，然后返回12416037344（这里假设是64位平台）。如果使用长度为x的数组来存储键/值对，那么我们需要计算数组中槽（存储键/值对的单元）的索引，掩码值为x-1。这可以使计算索引的过程非常快。调整字典结构长度的机制（下面会详细介绍）会使得找到空槽的概率很高，这意味着在大多数情况下只需要简单的计算。如果字典中使用的数组长度为8，则key'a'的索引为：hash('a')&7=0，同理'b'的索引为3，'c'的索引是2，而'Theindexofz'和'b'的索引相同，也是3，所以有冲突。可以看出，Python的hash函数在key之间连续的情况下表现比较理想，主要是考虑到通常处理的都是这种类型的数据。但是，一旦我们添加键'z'就会发生冲突，因为这个键值与其他键不相邻，而且相距很远。当然我们也可以使用索引为key的hash值的链表来存储key/value对，但是会增加查找元素的时间，时间复杂度不再是O(1)。下一节将介绍Python字典用于解决冲突的方法。开放寻址法（Openaddressing）开放寻址法是一种通过检测的方式处理冲突的方法。在上面键'z'的冲突示例中，索引3已经在数组中被占用，因此需要搜索当前未使用的索引。递增和搜索键/值对都需要O(1)时间。寻找空闲槽采用二次探测序列，其代码如下：j=(5*j)+1+perturb;perturb>>=PERTURB_SHIFT;usej%2**iasthenexttableindex;循环5*j+1for快速放大不影响初始索引的哈希值二进制文件中的微小差异。变量扰动可以使其他二进制位也不断变化。出于好奇，我们来看看数组长度为32时的检测顺序，j=3->11->19->29->5->6->16->31->28->13->2...更多关于检测序列可以参考dictobject.c的源码。文档的开头包含对检测机制的详细描述。让我们通过一个例子来看看Python内部代码。基于C语言的字典结构以下是基于C语言的数据结构，用于存储字典的key/value对（也称为entry），存储内容包括hash值、key和value。PyObject是Python对象的基类。typedefstruct{Py_ssize_tme_hash;PyObject*me_key;PyObject*me_value}PyDictEntry;下面是字典对应的数据结构。其中，ma_fill为activeslots和dummyslots的总数。当删除活动插槽中的键/值对时，该插槽被标记为虚拟插槽。ma_used是活动插槽的总数。ma_mask值为数组长度减1，用于计算slot的索引。ma_table是数组本身，ma_smalltable是长度为8的初始数组。typedefstruct_dictobjectPyDictObject;struct_dictobject{PyObject_HEADPy_ssize_tma_fill;Py_ssize_tma_used;Py_ssize_tma_mask;PyDictEntry*ma_table;PyDictEntry*(*ma_lookup)(PyDictObject*mp,PyObject*key,longhash);PyDictEntryma_smalltable[PyDict_MINSIZE];};字典初始化字典在初次创建时将调用PyDict_New(）功能。此处删除了源代码中的一些行，并将C语言代码转换为伪代码以突出几个关键概念。returnsnewdictionaryobjectfunctionPyDict_New:allocatenewdictionaryobjectcleardictionary'stablesetdictionary'snumberofusedslots+dummyslots(ma_fill)to0setdictionary'snumberofactiveslots(ma_used)to0setdictionary'smask(ma_value)todictionarysize-1=7setdictionary'slookupfunctiontolookdict_stringreturnallocateddictionaryobject添加项添加新的键/值对调用的是PyDict_SetItem()函数。Thefunction将采用指向字典对象和键/值对的指针。在这个过程中，它会先检查key是否为字符串，然后计算hash值。如果key的hash值之前已经计算过并缓存过，则直接使用缓存值。然后调用insertdict()函数添加新的键/值对。如果活动槽和空槽的总数超过数组长度的2/3，则需要调整数组长度。为什么是2/3？这主要是为了保证探测序列能够足够快地找到空闲槽。我们稍后会介绍调整长度的功能。arguments:dictionary,key,valuereturns:0ifOKor-1functionPyDict_SetItem:ifkey'shashcached:usehashelse:calculatehashcallinsertdictwithdictionaryobject,key,hashandvalueifkey/valuepairaddedsuccessfullyandcapacityover2/3:calldictresizetoresizedictionary'stableinserdict_find_freefunctionlstrictook(.)这与用于查找键的函数相同。lookdict_string()使用散列和掩码计算插槽的索引。如果使用“index=hashvalue&mask”方法没有找到key，将通过调用前面描述的循环方法来探测它，直到找到一个空闲slot。第一轮检测，如果没有找到匹配的key，检测过程中遇到dummyslot，则返回一个dummyslot。这优先考虑以前删除的插槽。现在我们要添加以下键/值对：{'a':1,'b':2','z':26,'y':25,'c':5,'x':24},那么会发生下面的过程：分配一个字典结构，内表的大小为8。这是我们目前得到的：8个槽中的6个已经被使用，并且使用量已经超过了2/3总容量，因此将调用dictresize()函数以分配更大的数组，同时将条目从旧表复制到新表。在我们的例子中，调用dictresize()函数后，调整后的数组长度不少于4倍的活跃槽数，即minused=24=4*ma_used。而当activeslot数量很大（大于50000）时，调整后的长度不应小于activeslot数量的两倍，即2*ma_used。为什么是4次？这主要是为了减少对调整大小函数的调用次数，同时显着提高稀疏性。新表的长度要大于24，在计算长度值时，会不断升级当前长度值，直到大于24，最终长度为32，比如当前长度为8，则计算过程如下：8->16->32。这就是长度调整的工作原理：分配一个长度为32的新表，然后将旧表中的条目插入新掩码为31的新表中。最终结果如下：DeleteItem删除项目时调用PyDict_DelItem()函数。删除时先计算key的hash值，然后调用search函数返回entry，***槽被标记为dummyslot。假设我们要从字典中删除key'c'，最终会得到如下结果：注意删除item后，即使最后的activeslots数量远小于总数，也不会触发调整数组大小的动作。但是，如果在删除后添加key/value对，则可能会减少数组的长度，因为调整长度的条件判断是基于activeslots和dummyslots的总数。
