Python字典实现--源码解读

python dict 源码解读

python dict的基本介绍

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

key value
name 张三
age 18
sex

当我们输入 '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在表中的地址。
看图:
Python字典实现--源码解读

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源码

上一篇:判断访问终端并实现跳转不同路径


下一篇:图论训练之十