Python字典实现--源码解读

参考链接： Python字典| values

python dict 源码解读

 python dict的基本介绍Hash Table 概念dict实现的三个核心结构体解读dict的底层几个C API源码

python dict的基本介绍 

一般在编程语言里，需要一种数据结构，来映射一些关系，比如人的名字、年龄、性别等等 如图所示 

keyvaluename张三age18sex男……

当我们输入 'name’时，希望能得到 ‘张三’ 在Python里dict字典就是实现这个功能的一个内置数据类型 上表中的每一对key-value都可以称为一个条目(Entry)，根据key就能找到value，是不是类似一个字典。 

python中的dict语法如下 

>>>student = dict(name="张三", age=18, sex="男")

>>>student

{"name":"张三", "age":18, "sex":"男"}

>>>student["name"]

张三

>>>

dict[key]–>value 

Hash Table 概念 

Python的字典是采用了散列表，或者叫哈希表，因为理论上，在最优的情况下，散列表能提供O(1)的复杂度的搜索效率。python的实现中本身大量使用了字典，比如在正常情况下，每个对象都有一个__dict__属性，再比如函数的关键字参数**kwargs等等，都依赖于python的字典，所以搜索效率是python实现字典的第一首要目标。 

那么什么是Hash Table呢？ 散列表的基本思想就是，通过一个函数，将key映射称为一个索引，去访问某一片连续内存区域，而这个索引所在的内存就存放了value的地方。 所以说，散列表是普通数组的推广应用。核心就是：根据关键字计算出key在表中的地址。 看图：  

dict实现的三个核心结构体 

因为python3.6以后，字典变化较大，最大的变化就是dict变得有序了，并且效率提高了20%~30%，特别内存利用率更高了。 接下来，让我们看看C层面的关于字典实现的三个结构体 第一个核心结构体PyDictKeyEntry 位置:cpython/Objects/dict-common.h 

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;

从名字可以看出来，这是dict存储每一对key-value的结构体，也就是之前所说的Entry条目。 dict中的每一对key-value对应一个PyDictKeyEntry类型的对象。 

1.me_hash：存储了key的哈希值，专门用一个成员记录key的散列值，可以避免每次查询时都要去重新计算下。 2.me_value：可以看到，在PyDictKeyEntry中value是一个PyObject *，这也是Python中的dict什么都能装的下的原因，因为在Python里，无论什么东西归根结点都是一个PyObject对象。 3.me_key：在一个PyDictObject对象变化的过程中，其中的entry会在不同的状态中转换。 PyDictObject中的entry可以在4种状态中转换：Unused(态)、Active(态)、Dummy(态)和Pending(态) 

 Unused：当一个entry处于Unused态时，entry的me_key和me_value都为NULL，这种情况下，表示这个entry并没有存储一个(key，value)，并且之前也没有存储过它们，每一个entry在初始化的时候都会处于这种状态。而且只有在Unused态下，一个entry的me_key才会为NULL。 Active：当一个entry存储了一个(key，value)时，entry便转换到了Active态，在这种状态下，me_key和me_value都不能为NULL，更准确的讲me_key不能为dummy对象 

第二个核心结构体PyDictKeysObject 位置:cpython/Objects/dict-common.h 

typedef struct _dictkeysobject PyDictKeysObject;

/* See dictobject.c for actual layout of DictKeysObject */

struct _dictkeysobject {

    Py_ssize_t dk_refcnt;

    /* Size of the hash table (dk_indices). It must be a power of 2. */

    Py_ssize_t dk_size;

    /* Function to lookup in the hash table (dk_indices):

       - lookdict(): general-purpose, and may return DKIX_ERROR if (and

         only if) a comparison raises an exception.

       - lookdict_unicode(): specialized to Unicode string keys, comparison of

         which can never raise an exception; that function can never return

         DKIX_ERROR.

       - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further

         specialized for Unicode string keys that cannot be the <dummy> value.

       - lookdict_split(): Version of lookdict() for split tables. */

    dict_lookup_func dk_lookup;

    /* Number of usable entries in dk_entries. */

    Py_ssize_t dk_usable;

    /* Number of used entries in dk_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:

       - 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*)

       Dynamically sized, SIZEOF_VOID_P is minimum. */

    char dk_indices[];  /* char is required to avoid strict aliasing. */

    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:

       see the DK_ENTRIES() macro */

};

第三个核心结构体PyDictObject 位置:cpython/Include/cpython/dictobject.h 

typedef struct _dictkeysobject PyDictKeysObject;

/* The ma_values pointer is NULL for a combined table

 * or points to an array of PyObject* for a split table

 */

typedef struct {

    PyObject_HEAD

    /* Number of items in the dictionary */

    Py_ssize_t ma_used;

    /* Dictionary version: globally unique, value change each time

       the dictionary is modified */

    uint64_t ma_version_tag;

    PyDictKeysObject *ma_keys;

    /* If ma_values is NULL, the table is "combined": keys and values

       are stored in ma_keys.

       If ma_values is not NULL, the table is splitted:

       keys are stored in ma_keys and values are stored in ma_values */

    PyObject **ma_values;

} PyDictObject;

1.PyObject_HEAD：就不用多说了，这是所有Python对象共有的，包含了两个成员，一个是引用计数，一个是指向对象所属的类型的指针。 2.ma_used：表示字典中条目个数，当我们使用内置函数len()去获取字典的长度时，底层直接返回就是这个成员的值 3.ma_version_tag：字典版本号，全局唯一，每次字典更改了，这个值也要改变 4.ma_keys：是一个指针，指向另一个核心结构体PyDictKeysObject，它是实现字典的关键所在。 5.ma_values：是一个指向指针的指针，当它为NULL时，散列表是组合的(combined)，key和value存储在ma_keys里；当它不为NULL时，散列表是分离的(splited)，key存储在ma_keys里，而value存储在ma_values里 

解读dict的底层几个C API源码