从源码上分析Python底层是如何实现dictionarieskey]语法的这些特性来快速访问dict中的元素的。Python3.6之后的版本将保持元素添加到字典中的顺序。那么，Python底层是如何支持这些特性的呢？效率如何？今天就来简单探讨一下dict中的dict。Python底层实现，并尝试用CPython源码回答上述问题。【基本原理】首先我们来思考如何从一批数据中快速找到一个元素。在计算机中，对数据的访问是基于数据的存储方式，不同存储方式的访问效率差别很大。我们熟悉的列表是基于底层数组实现的。数组的优点是可以通过索引实现随机访问，速度非常快，时间复杂度为O(1)。但是前提是你需要知道被访问元素的位置。至于key-value等关联数据，我们并不关注它在应用中的存储位置。如果我们只是简单的用数组来存储key-value，我们需要比较数组中的每一个元素，才能找到目标key。当数据量很大时，这种查找是非常低效的。有没有一种数据结构可以实现高效比较？是的！学过C++的同学应该都知道，C++标准库提供了一个关联容器：map。它可以高效地访问键值对，其底层是基于红黑树实现的。红黑树是一种搜索效率高的自平衡二叉搜索树。那么，Python中的dict是基于红黑树实现的吗？答案是不。为了达到更快的访问速度，Python采用了另一种存储结构：哈希表。哈希表基于数组的随机访问特性，利用哈希算法快速计算key的哈希值，从而定位元素在底层数组中的位置，实现对元素的快速访问。这种结构的访问效率与数组相同，但也有一定的缺点：哈希算法不能保证对每个键的求值结果的唯一性，因此不同的键可能得到相同的存储位置。这会导致冲突。哈希表需要某些策略来避免键冲突。当然，冲突key的访问效率也会降低。我们来看看CPython是如何通过哈希表来实现dict的。【字典相关数据结构】1、字典对象PyDictObjecttypedefstruct{PyObject_HEAD/*字典元素个数*/Py_ssize_tma_used;/*全局唯一版本号，dict修改时会改变*/uint64_tma_version_tag;/*存储元素或Element键，负责哈希表的具体实现*/PyDictKeysObject*ma_keys;/*当哈希表为combined模式时，该值存储在ma_keys的每个PyDictKeyEntry对象中，该值为NULL。用于在哈希表处于拆分模式时存储元素的值。*/PyObject**ma_values;}PyDictObject;每个字典都是一个PyDictObject对象。在这个结构体中，最重要的成员变量是ma_keys，它是实现哈希表的key。2、哈希表PyDictKeysObjectstruct_dictkeysobject{Py_ssize_tdk_refcnt;/*哈希表(dk_indices)的大小，其值为2的幂.*/Py_ssize_tdk_size;/*在哈希表(dk_indices)中进行查找的函数*/dict_lookup_funcdk_lookup;/*dk_entries中可用条目数*/Py_ssize_tdk_usable;/*dk_entries中已使用条目数*/Py_ssize_tdk_nentries;/*哈希表。可以动态调整大小。64位系统上最小大小为8，32位系统上最小大小为4.*/chardk_indices[];/*"PyDictKeyEntrydk_entries[dk_usable];"*/};typedefstruct_dictkeysobjectPyDictKeysObject;从名字上看，PyDictKeysObject是用来存储字典元素的key。实际上，在复合模式下，它存储的是键值对。所以，不管是哪种模式，至少key是保存在这个对象中的。这个对象是我们研究的重点。PyDictKeysObject的内存布局如下：我们在上面的代码中简单的标注了PyDictObject的各个成员变量的含义。现在关注dk_indices。dk_indices是一个char类型的数组，从定义上看，这是一块rawmemory。它正是哈希表使用的存储空间。dk_indices数组前面部分存放的是字典元素（键值对）在dk_entries中的索引值。我们可以称这部分为：哈希表索引内存块。根据数组的大小，对每个索引值的类型进行不同的解释。索引类型数组大小dk_sizeint8dk_size<=128int16256<=dk_size<=2**15int322**16<=dk_size<=2**31int64dk_size>=2**32可以看出越大数组，每个值代表一个更大的索引范围。每个索引值的取值范围为[0,dk_size*2/3]，或者：-1（内存未被使用），-2（内存已被使用）。dk_indices数组的后半部分用于存储字典中的元素。这个空间被解释为：PyDictKeyEntrydk_entries[dk_usable]。我们可以称这部分为：哈希表键值对内存块。dk_entries中的元素数量是dk_size的2/3。该值不仅可以有效减少键冲突，还可以提高内存空间的利用率。3.字典元素typedefstruct{Py_hash_tme_hash;/*为me_key哈希值缓存*/PyObject*me_key;PyObject*me_value;/*只有当哈希表为组合模式时才有意义*/}PyDictKeyEntry;哈希表是组合模式，这里存储的是我们的键值对。当哈希表处于拆分模式时，只有me_key将元素存储为键。【哈希表】从上面数据结构的定义，我们已经知道dict会将key-value对存储在一个连续的内存空间dk_indices中。dk_indices正是dict使用的哈希表。那么，如何理解dk_indices的哈希表呢？通常，哈希表有两种实现方式：冲突链和开放寻址。这两种方法对应两种解决键冲突的方法。冲突链：将哈希值相同的键组织成一个链表。哈希表只存储指向元素链表的指针，哈希值相同的元素依次追加到每个链表的末尾。开放寻址：从哈希表中的冲突位置找到下一个可用位置。元素存储在哈希表中。如果发现冲突，则从冲突的位置（如kv1的位置）开始，通过一定的策略寻找下一个可用的位置（如kv3）。CPython使用开放寻址并使用优化的存储结构。dk_indices数组的第一部分用来存放键值对的位置索引，第二部分用来存放键值对。这是一种高效紧凑的存储结构。我们从dictobject.c的insert_dict()函数中取出一段代码来验证这个结构。insertdict(PyDictObject*mp,PyObject*key,Py_hash_thash,PyObject*value)函数用于向字典mp中插入一个哈希值为hash的key-value键值对。此片段开头的if(ix==DKIX_EMPTY)表示可以将此键值对插入哈希表的未使用位置（称为槽）。代码接下来检查哈希表中的剩余空间是否可用，如果不足则调整大小。接下来调用find_empty_slot()获取slot在哈希表索引内存块中的位置索引hashpos。该函数实现碰撞算法。通过DK_ENTRIES宏获取ma_keys中下一个可用内存ep。由于哈希表键值对内存块是连续的，所以下一个可用内存可以通过将当前存储的键值对数量dk_nentries加上dk_indices移位计算前部分的偏移量得到。#defineDK_ENTRIES(dk)\((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk)*DK_IXSIZE(dk)]))通过DK_ENTRIES的宏定义我们可以清楚的看到直到它正在访问dk_indices的键值对内存块。现在，我们知道了元素在哈希表索引内存块中的位置hashpos和键值对内存块中的“相对位置”dk_nentries，调用dictkeys_set_index()设置两者在哈希表中的关系：指数[hashpos]=dk_nentries。下面的代码更新ep指向的内存数据并累加dk_nentries。你可以详细体验这个过程。这种存储结构也保证了使用key访问元素的效率。可以将key的哈希值快速映射到元素在哈希表索引内存块中的位置hashpos，然后通过键值对内存的偏移“index”直接访问对应的键值对块保存在hashpos中。【哈希算法与冲突算法】哈希表的实现有三个重要的要素：数据结构、哈希算法和冲突算法。我们已经了解了数据结构。那么，CPython使用什么哈希算法呢？如果不手动实现__hash__方法，它会使用内置的hash()函数来计算键的哈希值。CPython使用开放寻址来解决冲突。冲突算法如下：先初始化哈希表的位置索引i，然后获取存放在i处的键值对内存块的索引ix。在循环中不断更新i，检查ix的值，直到ix<0，即此时哈希表索引内存块的i代表一个从未使用过的槽。更新i的算法不好理解，就不深究了。【如何保持元素的插入顺序】dict的一个有趣的特性是在插入元素时保持元素的位置顺序：>>>d={}>>>d[3]="Three">>>d[1]="一">>>d[2]="二">>>d[0]="零">>>d{3:'三',1:'一',2:'Two',0:'Zero'}>>>>>>list(d.keys())[3,1,2,0]从上面对哈希表的分析，我们很容易理解其中的原因：元素是追加到键值对内存块的末尾。当我们打印字典，或者调用它的keys()方法时，字典直接访问键值对的内存块。因此，元素按照插入的顺序返回。[resize]由于dict使用连续的内存块来实现哈希表，当插入的元素较多时，可能内存空间不足，需要扩充内存。另一方面，如果之前已经分配了很大的内存空间，然后进行大量删除元素的操作，此时也需要减少内存，避免浪费。staticintinsertion_resize(PyDictObject*mp){returndictsize(mp,GROWTH_RATE(mp));}insertion_resize()调用dictresize()来调整字典的大小。dictresize()的第二个参数是调整后的大小，这里是一个宏。在CPython3.9.2中定义为：#defineGROWTH_RATE(d)((d)->ma_used*3)可以看出dict的大小会调整为原来used的大小（包括valid键值对）内存3倍。这个调整幅度还是蛮大的，好处是可以避免频繁的resize。【结论】本文简要介绍了Python字典的底层数据结构和实现算法。通过使用内存优化的哈希表，dict支持快速查找和有序插入等特性。这种数据结构的设计方法非常值得我们在开发中借鉴。本文转载自微信公众号《Python学习与思考》，可通过以下二维码关注。转载本文请联系python学习思考公众号。
