• 简介
• PyDictObject
• 对象类型
• 创建dict
• 缓存池

本文基于Python3.10.4。

简介

元素与元素之间通常可能会存在某种联系，这个联系将两个元素关联在一起。为了刻画这种关联关系，编程语言中都会提供关联容器，其中保存着一对一对的元素对，通常其中一个被称为键（key），另一个被称为值（value）。

C++ STL中的map就是一种关联容器，其低层的实现基于RB-tree红黑树，可以提供良好的搜索效率，其搜索的时间复杂度为log₂N。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缓存池的管理机制。