目录
本文基于Python3.10.4。
简介
元素与元素之间通常可能会存在某种联系，这个联系将两个元素关联在一起。为了刻画这种关联关系，编程语言中都会提供关联容器，其中保存着一对一对的元素对，通常其中一个被称为键（key），另一个被称为值（value）。
C++ STL中的map就是一种关联容器，其低层的实现基于RB-tree红黑树，可以提供良好的搜索效率，其搜索的时间复杂度为log2N。python中的dict是python实现的一种关联容器，其底层使用了散列表，来进一步提高搜索的效率。
PyDictObject
PyDictObject是python中dict的底层实现，先看一下它的具体定义。
[Include/cpython/dictobject.h]
typedef struct {
PyObject_HEAD
/* Number of items in the dictionary */
Py_ssize_t ma_used;
/* Dictionary version: globally unique, value change each time
the dictionary is modified */
uint64_t ma_version_tag;
PyDictKeysObject *ma_keys;
/* If ma_values is NULL, the table is "combined": keys and values
are stored in ma_keys.
If ma_values is not NULL, the table is split:
keys are stored in ma_keys and values are stored in ma_values */
PyObject **ma_values;
} PyDictObject;
- PyObject_HEAD：python定长对象的共有部分
- ma_used：dict中的元素对 数目
- ma_version_tag：dict的版本号，每一次元素的修改就会更新dict的版本
- ma_keys：dict中key对象的定义
- ma_values：dict中value对象的定义，类型是PyObject，所以python中dict的值可以是任意类型的对象
这里从注释可以看到两种存储方式，如果ma_values为空，这个dict对象就是combined合并类型，keys和values都保存在ma_keys中。如果不为空的话，values保存在ma_values中，keys保存在ma_keys中。
PyObject是python中所有类型对象的基础，这里不多做介绍，重点跟一下PyDictKeysObject的定义。
[Objects/dict-common.h]
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
/* Size of the hash table (dk_indices). It must be a power of 2. */
Py_ssize_t dk_size;
/* Function to lookup in the hash table (dk_indices):
- lookdict(): general-purpose, and may return DKIX_ERROR if (and
only if) a comparison raises an exception.
- lookdict_unicode(): specialized to Unicode string keys, comparison of
which can never raise an exception; that function can never return
DKIX_ERROR.
- lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
specialized for Unicode string keys that cannot be the <dummy> value.
- lookdict_split(): Version of lookdict() for split tables. */
dict_lookup_func dk_lookup;
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable;
/* Number of used entries in dk_entries. */
Py_ssize_t dk_nentries;
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
The size in bytes of an indice depends on dk_size:
- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)
Dynamically sized, SIZEOF_VOID_P is minimum. */
char dk_indices[]; /* char is required to avoid strict aliasing. */
/* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
see the DK_ENTRIES() macro */
};
- dk_refcnt：引用计数器数目
- dk_size：散列表的大小，其大小必须是2的n次方
- dk_lookup：查找元素的函数
- dk_usable：dk_entries中可用的数目
- dk_nentries：dk_entries中使用中的数目
- dk_indices：保存的数据
对象类型
python中每一种类型的行为，都由相应的类型对象决定。要了解PyDictObject对象具有哪些操作，就需要通过它的类型对象来了解。
[Objects/dictobject.c]
PyTypeObject PyDict_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"dict",
sizeof(PyDictObject),
0,
(destructor)dict_dealloc, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
(reprfunc)dict_repr, /* tp_repr */
&dict_as_number, /* tp_as_number */
&dict_as_sequence, /* tp_as_sequence */
&dict_as_mapping, /* tp_as_mapping */
PyObject_HashNotImplemented, /* tp_hash */
0, /* tp_call */
0, /* tp_str */
PyObject_GenericGetAttr, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS |
_Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_MAPPING, /* tp_flags */
dictionary_doc, /* tp_doc */
dict_traverse, /* tp_traverse */
dict_tp_clear, /* tp_clear */
dict_richcompare, /* tp_richcompare */
0, /* tp_weaklistoffset */
(getiterfunc)dict_iter, /* tp_iter */
0, /* tp_iternext */
mapp_methods, /* tp_methods */
0, /* tp_members */
0, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
dict_init, /* tp_init */
PyType_GenericAlloc, /* tp_alloc */
dict_new, /* tp_new */
PyObject_GC_Del, /* tp_free */
.tp_vectorcall = dict_vectorcall,
};
dict作为一种标准的map类型，重点查看一下dict_as_mapping的定义，其中实现了dict的重要操作。
[Objects/dictobject.c]
static PyMappingMethods dict_as_mapping = {
(lenfunc)dict_length, /*mp_length*/
(binaryfunc)dict_subscript, /*mp_subscript*/
(objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
};
- dict_length：获取dict的长度
- dict_subscript：通过下标获取数据
- dict_ass_sub：修改dict中的key对应的值
这里选取dict_length和dict_ass_sub的具体实现进行介绍，关于dict的其它功能实现，有兴趣的可以通过源码进一步了解。
获取dict长度：
static Py_ssize_t
dict_length(PyDictObject *mp)
{
return mp->ma_used;
}
static int
dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
{
if (w == NULL)
return PyDict_DelItem((PyObject *)mp, v);
else
return PyDict_SetItem((PyObject *)mp, v, w);
}
前面介绍到ma_used中保存了dict对象中元素对的数目，所以获取其长度的时候，可以直接返回这个参数的值。dict_ass_sub中则是显示了元素的新增、更新与删除。
创建dict
python中仅提供了一种方式来创建dict对象，创建的函数不需要参数。下面是创建函数的声明：
[Include/dictobject.h]
PyAPI_FUNC(PyObject *) PyDict_New(void);
跟一下这个函数的具体实现：
[Objects/dictobject.c]
PyObject *
PyDict_New(void)
{
dictkeys_incref(Py_EMPTY_KEYS);
return new_dict(Py_EMPTY_KEYS, empty_values);
}
/* Consumes a reference to the keys object */
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
// new_dict() must not be called after _PyDict_Fini()
assert(state->numfree != -1);
#endif
if (state->numfree) {
mp = state->free_list[--state->numfree];
assert (mp != NULL);
assert (Py_IS_TYPE(mp, &PyDict_Type));
_Py_NewReference((PyObject *)mp);
}
else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL) {
dictkeys_decref(keys);
if (values != empty_values) {
free_values(values);
}
return NULL;
}
}
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
ASSERT_CONSISTENT(mp);
return (PyObject *)mp;
}
dictkeys_incref只是简单的累加引用数，这里不做进一步介绍，有兴趣的可以阅读源码熟悉，PyDict_New的具体实现逻辑全在new_dict中。
这里先重点熟悉下面这部分，缓存池相关部门后面再单独介绍：
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
ASSERT_CONSISTENT(mp);
return (PyObject *)mp;
new_dict创建一个新的dict对象，在无缓存的情况下，PyObject_GC_New创建一个新的PyObject对象，初始化对象中的参数值。
缓存池
前面了解创建dict对象时的逻辑，就有一部分是关于缓存池的处理。
struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
// new_dict() must not be called after _PyDict_Fini()
assert(state->numfree != -1);
#endif
if (state->numfree) {
mp = state->free_list[--state->numfree];
assert (mp != NULL);
assert (Py_IS_TYPE(mp, &PyDict_Type));
_Py_NewReference((PyObject *)mp);
}
在每次创建dict对象是，会通过get_dict_state函数去获取缓存池的数据。如果缓存池中有数据可以用，会直接返回缓存池中的dict对象，减少频繁创建dict对象的资源消耗。python中对于dict的缓存池机制与list的缓存池机制是一样的，有兴趣的可以了解一下list的源码。
这里介绍了缓存池中数据的使用，那么缓存池中的数据是怎么写进去的呢？是像python的小整数缓存池一样吗？
答案是不一样的，dict的缓存池是在删除dict对象的时候写入的。
删除dict：
static void
dict_dealloc(PyDictObject *mp)
{
PyObject **values = mp->ma_values;
PyDictKeysObject *keys = mp->ma_keys;
Py_ssize_t i, n;
/* bpo-31095: UnTrack is needed before calling any callbacks */
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_BEGIN(mp, dict_dealloc)
if (values != NULL) {
if (values != empty_values) {
for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
Py_XDECREF(values[i]);
}
free_values(values);
}
dictkeys_decref(keys);
}
else if (keys != NULL) {
assert(keys->dk_refcnt == 1);
dictkeys_decref(keys);
}
struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
// new_dict() must not be called after _PyDict_Fini()
assert(state->numfree != -1);
#endif
if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
state->free_list[state->numfree++] = mp;
}
else {
Py_TYPE(mp)->tp_free((PyObject *)mp);
}
Py_TRASHCAN_END
}
这里我们可以看到，在调用删除dict对象的时候，会先将dict的中key和value都删除。之后再判断缓存池中是否还有空间，可以将这个dict对象保存起来。有空间的话，将其写入缓存池，不然的话就释放dict对象的空间，删除dict对象。
那么dict的缓存池有多大呢？我们可以跟一下state的定义：
#ifndef PyDict_MAXFREELIST
# define PyDict_MAXFREELIST 80
#endif
struct _Py_dict_state {
/* Dictionary reuse scheme to save calls to malloc and free */
PyDictObject *free_list[PyDict_MAXFREELIST];
int numfree;
PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
int keys_numfree;
};
和python中其它缓存池一样，缓存池的大小都是硬编码的，需要更改的时候，得修改源码重编码。同时这里可以看到除了dict对象的缓存池之外，针对PyDictKeysObject对象也设置了一个缓存池。它使用的逻辑与前者差不多，有兴趣的可以去进一步熟悉dict中元素对的创建和删除，了解PyDictKeysObject缓存池的管理机制。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/287883.html