Python 源码阅读：dict
（点击上方蓝字，快速关注我们）
来源：伯乐在线 - wklken
源码位置 Include/dictobject.h | Objects/dictobject.c
PyDictObject的存储策略
1. 使用散列表进行存储
2. 使用开放定址法处理冲突
2.1 插入, 发生冲突, 通过二次探测算法, 寻找下一个位置, 直到找到可用位置, 放入(形成一条冲突探测链)
2.2 查找, 需要遍历冲突探测链
2.3 删除, 如果对象在探测链上, 不能直接删除, 否则会破坏整个结构(所以不是真的删)
关于 hash表的 wiki
基本键值PyDictEntry
typedef struct {
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
说明
1. PyDictEntry 用于存储键值对信息
2. Py_ssize_t me_hash
存储了me_key计算得到的hash值, 不重复计算
结构
PyDictEntry的三个状态(图片引自-Python源码剖析)
PyDictObject定义
定义
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. 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. PyDictObject在生命周期内, 需要维护ma_fill/ma_used/ma_mask 三个计数值
2. 初始化创建是ma_smalltable, 超过大小后, 会使用外部分配的空间
构造过程
定义
PyObject *
PyDict_New(void)
{
register PyDictObject *mp;
// 初始化dummy
if (dummy == NULL) {
dummy = PyString_FromString("");
if (dummy == NULL)
return NULL;
// 暂时忽略
#ifdef SHOW_CONVERSION_COUNTS
Py_AtExit(show_counts);
#endif
#ifdef SHOW_ALLOC_COUNT
Py_AtExit(show_alloc);
#endif
#ifdef SHOW_TRACK_COUNT
Py_AtExit(show_track);
#endif
}
// 如果PyDictObject缓冲池可用
if (numfree) {
// 取缓冲池最后一个可用对象
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
// 初始化
if (mp->ma_fill) {
// 1. 清空 ma_smalltable
// 2. ma_used = ma_fill = 0
// 3. ma_table -> ma_smalltable
// 4. ma_mask = PyDict_MINSIZE - 1 = 7
EMPTY_TO_MINSIZE(mp);
} else {
// 1. ma_table -> ma_smalltable
// 2. ma_mask = PyDict_MINSIZE - 1 = 7
INIT_NONZERO_DICT_SLOTS(mp);
}
assert (mp->ma_used == 0);
assert (mp->ma_table == mp->ma_smalltable);
assert (mp->ma_mask == PyDict_MINSIZE - 1);
#ifdef SHOW_ALLOC_COUNT
count_reuse++;
#endif
} else {
// 创建一个
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL)
return NULL;
// 初始化 1/2/3/4
EMPTY_TO_MINSIZE(mp);
#ifdef SHOW_ALLOC_COUNT
count_alloc++;
#endif
}
// 搜索方法, 关注这个
mp->ma_lookup = lookdict_string;
#ifdef SHOW_TRACK_COUNT
count_untracked++;
#endif
#ifdef SHOW_CONVERSION_COUNTS
++created;
#endif
// 返回
return (PyObject *)mp;
}
简化步骤
1. 如果PyDictObject对象缓冲池有, 从里面直接取, 初始化
2. 否则, 创建一个, 初始化
3. 关联搜索方法lookdict_string
4. 返回
结论
1. 关注对象缓冲池
2. 关注lookdict_string
销毁过程
方法定义
static void
dict_dealloc(register PyDictObject *mp)
{
register PyDictEntry *ep;
Py_ssize_t fill = mp->ma_fill;
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_SAFE_BEGIN(mp)
// 遍历销毁ma_table中元素 (ma_table可能指向small_table 或 外部)
for (ep = mp->ma_table; fill > 0; ep++) {
if (ep->me_key) {
--fill;
Py_DECREF(ep->me_key);
Py_XDECREF(ep->me_value);
}
}
// 如果指向外部, 销毁整个(上面一步只销毁内部元素)
if (mp->ma_table != mp->ma_smalltable)
PyMem_DEL(mp->ma_table);
// 如果对象缓冲池未满且是PyDict_Type, 放入
if (numfree tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}
PyDictObject对象缓冲池
定义
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
对象缓冲池的结构(跟PyListObject对象缓冲池结构基本一样)
结论
1. 最多会缓存80个对象
2. 只缓存 PyDictObject 本身, 其PyDictEntry全部会被回收
3. 缓存对象进去, 旧有的值没有变化, 取出来用的时候初始化时才改变
本系列
看完本文有收获？请转发分享给更多人
关注「Python开发者」，提升Python技能