源码位置 Include/dictobject.h | Objects/dictobject.c
PyDictObject的存储策略
|
1 2 3 4 5 6 7 8 9 |
1. 使用散列表进行存储 2. 使用开放定址法处理冲突 2.1 插入, 发生冲突, 通过二次探测算法, 寻找下一个位置, 直到找到可用位置, 放入(形成一条冲突探测链) 2.2 查找, 需要遍历冲突探测链 2.3 删除, 如果对象在探测链上, 不能直接删除, 否则会破坏整个结构(所以不是真的删) |
关于 hash表的 wiki
基本键值PyDictEntry
|
1 2 3 4 5 |
typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry; |
说明
|
1 2 3 4 |
1. PyDictEntry 用于存储键值对信息 2. Py_ssize_t me_hash 存储了me_key计算得到的hash值, 不重复计算 |
结构
PyDictEntry的三个状态(图片引自-Python源码剖析)
PyDictObject定义
定义
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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]; }; |
说明
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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数量 |
结构
结论
|
1 2 3 |
1. PyDictObject在生命周期内, 需要维护ma_fill/ma_used/ma_mask 三个计数值 2. 初始化创建是ma_smalltable, 超过大小后, 会使用外部分配的空间 |
构造过程
定义
