python 字典实现的原理与探析

在计算机体系中，我们经常可以观察到一种一一对应关系的存在，比如硬件设备的ip地址和mac地址。这种关系在工程实现中被称为映射，正如光和影子之间的关系，表面上我们可以通过一个物体推测出在光照下可以看到什么样的影子，但由于光照的姿势不一样，影子的样子也不一样，这就衍生出多种多样的映射关系，但本质上就是在同一种角度的照射下我们看到一种影子，对吧~

映射关系.png

在python中，有一种容器，名为dict正是这么做的，其中的每个元素就是一个key:value键值对，通过指定的key可以找到value。这是一种性能的得到过高度优化的结构，通过这种时间复杂度达到O(1)的极致性能让我们在做查询的时候得到极大的便利，可问题在于，这玩意这么方便这么快，就可以滥用吗？字典里面的key是否有序？凭什么时间复杂度达到O(1)那空间复杂度又是多少呢？开发者们是怎么对这个结构进行优化的呢？对于同样是开发者的我们又有什么借鉴意义呢？问题很多，而且也几乎是面试的时候会遇到的问题，基于此，理应秉承为自己负责的态度，提升自己的内功水平:)

解决问题之前

我们在推演答案之前不妨先想一下，如果我们自己构造一个dict会长成什么样？

这里我们可以借助leetcode上面的两道题来开胃:

1. 705. 设计哈希集合，这道题的目的在于完成key的唯一性设计
2. 706. 设计哈希映射，这道题的目的在于完成映射关系的构建

通过解决这两个基本问题之后我们对于窥探dict的底层原理才有一点基本的认知。即在python的字典中其内部使用的数据结构是哈希表

所谓哈希

哈希其实是音译的，其实就是hash，也是散列的意思，简单来说就是，通过这个散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。构建散列函数的方法有很多，比如直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留取余等。

这个话题其实也是一个大工程才能说明白，后续有机会再继续展开。

观察dict

我们先观察一个有趣的现象

dict观察.png

在这个案例中，作为字典的key值，要求选用不可变的容器如tuple，但如果选用可变的容器则是会弹出TypeError: unhashable type: 'list'这个异常。这个地方我们可以尝试着揣摩设计者们的一个思想，即通过某个函数将需要搜索的键值映射为一个索引，然后通过索引去访问连续的内存区域，对于可变的容器想要开辟出一个固定的长度的内存区间显然不可能。

源码分析

Dictionary object implementation using a hash table ，通过描述可知，python 的字典就是实现了一个 hash 表。对于这个结构的任何一个key或value，开发者们在底层会把它称之为一个entry，至于为什么？我们且一步步推敲。源文件：Objects/dict-common.h

字典结构关系图.png

窥探entry

任何一个key、value都是一个entry这个是基本思想，我们先来看看这个entry的实现方式。它的大小可以用USABLE_FRACTION这个宏来获取

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

其中，me_hash就是哈希生成的值，避免每次查询的时候都要重新建立，me_key就是对应的键，不过这个字段只对combined table有意义，me_value就是对应的值。 在 python 中，每一个PyDictObject对象的变化，entry的状态会在不同的状态间转换。基本上在如下四种状态中转换：Unused、Active、Dummy 和Pending。

• Unused:没有插入任何一个获取的key与value，并且在此之前也没有存储任何的key、value，每一个entry在初始化的时候都会处于这种状态。当有key插入，Unused会在里面切换到Active态。
• Active:当 index>=0 时，me_key不为空且me_value不为空时，保存了一个键值对。当一个键被删除的时候，且me_value不为空的时候Active可以转变为Dummy或者Pending状态。
• Dummy:先前保存了一个Active的键值对，但是这个键值对被删除了并且另一个Active的键值对还没有填入该位置，Dummy可以转变为Active。
• Pending:索引>=0，键!=空，值=空（仅拆分），尚未插入到拆分表中。

窥探keys

typedef struct _dictkeysobject PyDictKeysObject;

struct _dictkeysobject {
    //引用计数
    Py_ssize_t dk_refcnt;

    /* Size of the hash table (dk_indices). It must be a power of 2. */
    /* 哈希表的大小，必须是2的倍数 */
    Py_ssize_t dk_size;

    /* 与哈希表有关的函数 */
    dict_lookup_func dk_lookup;

    /* Number of usable entries in dk_entries. */
    /* dk_entries中可用的entries数量 */
    Py_ssize_t dk_usable;

    /* Number of used entries in dk_entries. */
    /* dk_entries中已经使用的entries数量 */
    Py_ssize_t dk_nentries;

    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).

       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).

       The size in bytes of an indice depends on dk_size:


       Dynamically sized, SIZEOF_VOID_P is minimum. */
    //最终的哈希表，它存储了dk_entries的索引
    //里面的类型是会随着dk_size的大小而变化的
    /*
       - 1 byte if dk_size <= 0xff (char*)
       - 2 bytes if dk_size <= 0xffff (int16_t*)
       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
       - 8 bytes otherwise (int64_t*)
    */
    char dk_indices[];  /* char is required to avoid strict aliasing. */

    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
       see the DK_ENTRIES() macro */
};

源码中有个dk_entries也就是上一个小节中提到的PyDictKeyEntry，这也是我们把某个键值对称之为一个entry的原因。

窥探Object

/* The ma_values pointer is NULL for a combined table
 * or points to an array of PyObject* for a split table
 对于一张combined table，ma_values指针为NULL
 对于一张split table，则指向一个数组，数组里面都是PyObject *
 */
typedef struct {
    //注意这是PyObject_HEAD,不是PyObject_VAR_HEAD
    //PyObject_HEAD只有引用计数和类型，没有ob_size
    PyObject_HEAD

    //字典里面元素的个数，active
    Py_ssize_t ma_used;

    /* Dictionary version: globally unique, value change each time
       the dictionary is modified 
       字典版本：全局唯一，每一次value的变动，都会导致其改变
    */
    uint64_t ma_version_tag;
	
    /*
    如果ma_values为NULL，这是一张combined table，所有的key和value都存在ma_keys里面
    */
    PyDictKeysObject *ma_keys;

    /* 
	   如果ma_values不为NULL，这是一张split table，那么key都存在ma_keys里
	   所有的values都存在ma_values这个数组里
	*/
    PyObject **ma_values;
} PyDictObject;

注意到源码中，不管在什么地方，我们看到存储的时候都是PyObject *，其实就是个指针引用，这个说明了字典的值是什么都可以装的(不可变类型)

两种字典类型

在字里行间的介绍中，会发现字典存在两种类型：分离字典（split-table dictionaries)与联合字典(combined-table dictonaries)。详细的信息可查看有关 dict 的描述pep-0412。

split-table dictionaries

当被创建的字典是用来保存object的__dict__属性时，该字典才会创建为一个split-table，它们的键表都被缓存在类型属性中，并且允许所有该类型的实例都可以共享该 keys。当出现一个事件将字典的属性值进行改变的时候，个别字典将慢慢的转化成组合表的形式。这就保证了在大部分的应用场景下很高的内存利用效率，并保证了在各个场景下的正确性。当split-dict重新改变大小，它会立马改变为一个combined-table，如果重置大小作为保存实例属性的结果，并且只有一个该object的实例，字典会立马再变为一个split-table。如果从split-table中删除一个key-value，它不会删除keys tables中对应的该值，而只是从values表 中移除了该value。

combined-table dictionaries

直接通过dict內建函数与{}生成的字典，模块和大部分其他字典都会创建为combined-table字典，一个combined-table不会改变为一个split-table字典，该字典的行为方式与最初的字典的行为方式大致相同。

总结

可以看到字典的定义还是蛮复杂的，但是仔细分析还是可以看懂的。PyDictObject里面有一个ma_values，如果是combined table，那么这个值是为NULL，key和value是放在PyDictKeyEntry里面的，由me_key和me_value存储，这当然也是一个PyObject *指针类型。如果是split table，那么ma_values则是一个数组，存储所有value，当然这里的value也是指针，PyDictKeyEntry则只存储key，而哈希表还要对应一个索引，这个索引都是放在PyDictKeysObject里面的。

感悟

看似简单的字典对象, 实际上底层实现起来包括了不少的计算机体系的知识, 看似复杂, 但其实大部分都是我们熟悉的算法和数据结构。我们主要是感悟其中的面向对象的设计思想，将可变因素通过指针引用的方式放置在内存堆栈。

参考资料

1. https://www.cnblogs.com/traditional/p/11772868.html
2. https://flaggo.github.io/python3-source-code-analysis/objects/dict-object/
3. https://juejin.cn/post/6844903693834256392