（点击
上方蓝字
，快速关注我们）
来源：伯乐在线 - 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.
缓存对象进去
,
旧有的值没有变化
,
取出来用的时候初始化时才改变
本系列
看完本文有收获？请转
发分享给更多人
关注「P
ython开发者」，提升Python技能
