首页 / PYTHON / Python字典实现--源码解读

Python字典实现--源码解读

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python字典实现--源码解读，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5371字，纯文字阅读大概需要8分钟。

内容图文

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

内容总结

以上是互联网集市为您收集整理的Python字典实现--源码解读全部内容，希望文章能够帮你解决Python字典实现--源码解读所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/681464.html

来源：【匿名】