Python字典实现源码解读

python dict 源码解读

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

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

如图所示

当我们输入 &＃39;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

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

那么什么是Hash Table呢？

散列表的基本思想就是，通过一个函数，将key映射称为一个索引，去访问某一片连续内存区域，而这个索引所在的内存就存放了value的地方。

所以说，散列表是普通数组的推广应用。核心就是：根据关键字计算出key在表中的地址。

看图：

因为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 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 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里