Python源码分析-PyDictObject_程序人生

Python源码分析-PyDictObject

admin

2023-07-31 00:47:28

0次

目前Cpython使用最多，下面分析下python中字典的源码实现

数据结构

1. PyDictObject

PyDictObject是python字典对应的C对象，本质上是一个hash表基本元素的组合，包含3个元素：

一个table（可以看成是一个数组）
hash函数
表格中的每一项：entry

123456789101112131415161718192021

typedef struct _dictobject PyDictObject;struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; /* # Active + # Dummy */ Py_ssize_t ma_used; /* # Active */ /* The table contains ma_mask + 1 slots, and that\’s a power of 2. * We store the mask instead of the size because the mask is more * frequently needed. */ Py_ssize_t ma_mask; /* ma_table points to ma_smalltable for small tables, else to * additional malloc\’ed memory. ma_table is never NULL! This rule * saves repeated runtime null–tests in the workhorse getitem and * setitem calls. */ PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE];};

PyDictObject包含了一个PyObject_HEAD, 任何python的对象都含他的指针。PyObject_HEAD包含一个双向链表, 一个引用计算器, 一个对象描述(typeobject)。这个对象其实主要的作用是垃圾回收。
ma_table 和ma_smalltable对应的是hash表中的table，但这里为啥有两个table呢？因为Python源码中使用了大量PyDictOject，但是dict中元素的数量一般比较少，为了方便，每次创建该对象时都会创建Pydict_MINISIZE个entry空间。当table中元素的个数超过一定数量时就会自动调整table的长度。所以，ma_table初始时等于ma_smalltable，当entry个数增加时，会调整 ma_table的长度。

Py_ssize_t ma_mask是用于计算hash值的，它的值等于table的长度减一。这个属性的理解非常重要，直接关系到是否能完全理Python的哈希函数以及hash值的计算。Python字典的哈希函数非常简单，如下：

12	ma_mask = len(table) – 1 # table的长度必须是2的N次方，所以ma_mask肯定是奇数index = key & ma_mask #等同于 index = key % len(table) ； index是表格中的位置，那么 key是怎么来的，这是关键，后续介绍

ma_lookup 函数用于根据 key查找 val。既然hash函数这么简单，那么为什么还需一个特殊的查找函数呢？因为table中的entry不是简单的一个数字或者字符串，而是一个对象PyDictEntry，这个对象有自己的生命周期，所以i在查找时稍微复杂一点。

ma_fill与ma_used：上面说过PyDictEntry有自己的生命周期，包括3个状态：unused，active, dummy。ma_fill表示table中已使用的个数（=active+dummy），active表示当前正在使用的个数，dummy表示插入以后删除的个数。

123	#code: pythond = {\’name\’: \’wxg\’, \’age\’: 23, \’sex\’: \’male\’} # unused=5(默认Pydict_MINISIZE=8)， active=3, dummy=0del d[\’sex\’] # unused=5, active=2, dummy=1

2. PyDictEntry

PyDictEntry是table中的具体元素项。

123456789

typedef struct { /* Cached hash code of me_key. Note that hash codes are C longs. * We have to use Py_ssize_t instead because dict_popitem() abuses * me_hash to hold a search finger. */ Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value;} PyDictEntry;

me_hash是hash值， me_key是储存的对象（可以是任意类型，因为python中一切皆对象，这些对象都是PyObject），me_value是存储的值。

hash函数分析

理解一个hash表的实现，最重要的是理解其中的hash函数的实现，以及发生碰撞时的解决方法。

1. hash函数的实现

上面介绍过hash函数的实现

1234	ma_mask = len(table) – 1 # table的长度必须是2的N次方，所以ma_mask肯定是奇数 index = key & ma_mask # key是怎么来的，这是关键，后续介绍 #设 d = {\’name\’: \’wxg\’} key = get_key(\’name\’) # 下面介绍 get_key 是怎么实现的。

PyDictObject本身的hash函数很简单，因为key是经过一次hash的值，即get_key函数就是获取一个对象（包括字符串，整数和更复杂对象）的hash值。Python源码中的原型如下：

上一篇：Python 二分查找与 bisect 模块

下一篇：5 个很好的 Python 面试题