Python进阶编程：编写更高效、优雅的Python代码
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

3.2.1　字典对象解析

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

Python3.6以后，字典变化较大，最大的变化就是dict变得有序了，并且效率提高了20%～30%，特别是内存利用率更高了。

下面看看C层面的关于字典实现的3个结构体。

第一个核心结构体为PyDictKeyEntry，也称entry或slot。

entry定义的源码位置为Objects/dict-common.h。

// 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的结构体。dict中的每一对key-value对应一个PyDictKeyEntry类型的对象。

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态。在Active态下，me_key和me_value都不能为NULL。更进一步地说，me_key不能为dummy对象。

·Dummy：当entry中存储的（key，value）对被删除后，entry的状态不能直接从Active态转为Unused态，否则会导致冲突探测链的中断。相反，entry中的me_key将指向dummy对象，entry进入Dummy态，这就是伪删除技术。当Python沿着某条冲突链搜索时，如果发现entry处于Dummy态，说明目前该entry虽然是无效的，但是其后的entry可能是有效的，是应该被搜索的。这样，就保证了冲突探测链的连续性。

·Pending态：索引≥0，键！=空，值=空（仅拆分），尚未插入拆分表中。

第二个核心结构体为PyDictKeysObject。

PyDictKeysObject源码位置为Objects/dict-common.h。

// Objects/dict-common.h
typedef struct _dictkeysobject PyDictKeysObject;
/* See dictobject.c for actual layout of DictKeysObject */
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    。。。。
};

对于该对象，需要关注对象中的对象映射数，即df_refcnt对象。

第三个核心结构体为PyDictObject。

PyDictObjec源码位置为Include/cpython/dictobject.h。

// Objects/cpython/dictobject.h 
typedef struct _dictkeysobject PyDictKeysObject;

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;

PyDictObjec对象的解读如下。

·PyObject_HEAD：是所有Python对象共有的，包含两个成员：一个是引用计数，另一个是指向对象所属类型的指针。

·ma_used：当使用内置函数len()去获取字典的长度时，底层直接返回ma_used这个成员的值。

·ma_version_tag：字典版本号，全局唯一，每次字典更改，版本号也要改变。

·ma_keys：是一个指针，指向另一个核心结构体PyDictKeysObject，是实现字典的关键所在。

·ma_values：是一个指向指针的指针，当它为NULL时，散列表是组合的，key和value存储在ma_keys里；当它不为NULL时，散列表是分离的，key存储在ma_keys里，而value存储在ma_values里。

上一章目录下一章