PyDictObject的存储策略

123456789

1. 使用散列表进行存储 2. 使用开放定址法处理冲突 2.1 插入, 发生冲突, 通过二次探测算法, 寻找下一个位置, 直到找到可用位置, 放入(形成一条冲突探测链) 2.2 查找, 需要遍历冲突探测链 2.3 删除, 如果对象在探测链上, 不能直接删除, 否则会破坏整个结构(所以不是真的删)

关于 hash表的 wiki

基本键值PyDictEntry

12345

typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value;} PyDictEntry;

说明

1234	1. PyDictEntry 用于存储键值对信息 2. Py_ssize_t me_hash存储了me_key计算得到的hash值, 不重复计算

结构

PyDictEntry

PyDictEntry的三个状态(图片引自-Python源码剖析)

PyDictEntryState

PyDictObject定义

定义

123456789101112

typedef struct _dictobject PyDictObject;struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; Py_ssize_t ma_used; Py_ssize_t ma_mask; PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE];};

说明

12345678910111213141516

1. PyObject_HEAD反而声明为定长对象, 因为ob_size在这里用不上, 使用ma_fill和ma_used计数 2. Py_ssize_t ma_fill; Py_ssize_t ma_used; ma_fill = # Active + # Dummy ma_used = # Active 3. Py_ssize_t ma_mask;散列表entry容量 = ma_mask + 1, 初始值ma_mask = PyDict_MINSIZE – 1 = 7 ma_mask + 1 = # Unused + # Active + # Dummy 4. PyDictEntry *ma_table;指向散列表内存, 如果是小的dict(entry数量

结构

PyDictObject

结论

123	1. PyDictObject在生命周期内, 需要维护ma_fill/ma_used/ma_mask 三个计数值 2. 初始化创建是ma_smalltable, 超过大小后, 会使用外部分配的空间

构造过程

定义

上一篇：利用 scrapy爬知乎用户关系网以及下载头像

下一篇：Python中如何使用*args和**kwargs

Python 源码阅读——dict

PyDictObject的存储策略

基本键值PyDictEntry

PyDictObject定义

构造过程

相关内容

热门资讯