网站导航
> 文章列表 > 【通过Cpython3.9源码看看字典到底是咋回事】

【通过Cpython3.9源码看看字典到底是咋回事】

网友: 文章列表 2024-03-21 22:49:36

【通过Cpython3.9源码看看字典到底是咋回事】

在这里插入图片描述

字典结构

/* The ma_values pointer is NULL for a combined table* or points to an array of PyObject* for a split table*/
typedef struct {PyObject_HEAD/* Number of items in the dictionary */Py_ssize_t ma_used;/* Dictionary version: globally unique, value change each timethe dictionary is modified */uint64_t ma_version_tag;PyDictKeysObject *ma_keys;/* If ma_values is NULL, the table is "combined": keys and valuesare stored in ma_keys.If ma_values is not NULL, the table is splitted:keys are stored in ma_keys and values are stored in ma_values */PyObject **ma_values;
} PyDictObject;

上述代码定义了 CPython 中的 PyDictObject 结构体，表示 Python 字典对象。

PyDictObject 结构体包含以下几个成员变量：

  1. PyObject_HEAD：Python 对象头部，包括对象类型、引用计数等信息。
  2. ma_used：字典中当前存储的键值对数量。
  3. ma_version_tag：字典的版本标记，每次字典被修改都会改变。
  4. ma_keys：指向 PyDictKeysObject 结构体的指针，表示字典中的键。
  5. ma_values：指向 PyObject* 类型的指针，表示字典中的值。

如果 ma_values 为 NULL，表示该字典采用“combined”方式存储，即键和值都存储在 ma_keys 中；如果 ma_values 不为 NULL，则采用“splitted”方式存储，即键存储在 ma_keys 中，值存储在 ma_values 中。

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 (andonly if) a comparison raises an exception.- lookdict_unicode(): specialized to Unicode string keys, comparison ofwhich can never raise an exception; that function can never returnDKIX_ERROR.- lookdict_unicode_nodummy(): similar to lookdict_unicode() but furtherspecialized 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 */
};

上述代码定义了 CPython 中的 _dictkeysobject 结构体，表示 Python 字典对象中的键的数据结构。

_dictkeysobject 结构体包含以下几个成员变量：

  1. dk_refcnt：键对象的引用计数。
  2. dk_size：哈希表的大小，必须是 2 的幂次方。
  3. dk_lookup：指向查找哈希表中元素的函数指针。
  4. dk_usable：哈希表中可用的条目数。
  5. dk_nentries：哈希表中已经使用的条目数。
  6. dk_indices：哈希表，保存了索引，或者是 DKIX_EMPTY（-1），或者是 DKIX_DUMMY（-2）。索引值必须满足 0 <= indice < USABLE_FRACTION(dk_size)，其中 USABLE_FRACTION(dk_size) 是可用的索引数量，即 dk_usable。索引的大小取决于 dk_size 的大小，当 dk_size <= 0xff 时，索引为 char* 类型，当 dk_size <= 0xffff 时，索引为 int16_t* 类型，当 dk_size <= 0xffffffff 时，索引为 int32_t* 类型，否则为 int64_t* 类型。
  7. dk_entries：保存键对象的数组，dk_usable 和 dk_nentries 决定了数组的长度，具体的长度由 DK_ENTRIES() 宏计算得到。

总之，_dictkeysobject 结构体定义了 Python 字典对象中键的基本属性和结构。

字典元素查找

1280116143@qq.com
PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{Py_hash_t hash;Py_ssize_t ix;PyDictObject *mp = (PyDictObject *)op;PyThreadState *tstate;PyObject *value;if (!PyDict_Check(op))return NULL;if (!PyUnicode_CheckExact(key) ||(hash = ((PyASCIIObject *) key)->hash) == -1){hash = PyObject_Hash(key);if (hash == -1) {PyErr_Clear();return NULL;}}/* We can arrive here with a NULL tstate during initialization: tryrunning "python -Wi" for an example related to string interning.Let's just hope that no exception occurs then...  This must be_PyThreadState_GET() and not PyThreadState_Get() because the latterabort Python if tstate is NULL. */tstate = _PyThreadState_GET();if (tstate != NULL && tstate->curexc_type != NULL) {/* preserve the existing exception */PyObject *err_type, *err_value, *err_tb;PyErr_Fetch(&err_type, &err_value, &err_tb);ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);/* ignore errors */PyErr_Restore(err_type, err_value, err_tb);if (ix < 0)return NULL;}else {ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);if (ix < 0) {PyErr_Clear();return NULL;}}return value;
}

PyDict_GetItem函数是用于从字典中获取一个键对应的值的函数。其函数定义如下：

PyObject *PyDict_GetItem(PyObject *op, PyObject *key)
  • op: 要从中获取键值对的字典对象。
  • key: 要获取值的键对象。

该函数首先会检查 op 是否为字典对象，如果不是则返回 NULL。接着会检查 key 是否为 Unicode 字符串对象，如果不是则需要对其进行哈希运算。如果哈希运算失败则会清除错误并返回 NULL。

然后该函数调用字典对象的 dk_lookup 函数进行查找。如果查找失败则会根据情况清除错误并返回 NULL。如果查找成功则返回相应的值对象。dk_lookup 是 _dictkeysobject 结构体中的一个函数指针，它指向一个用于在哈希表中查找元素的函数。这个函数会接收三个参数：指向哈希表的 _dictkeysobject 指针，要查找的元素 key，和元素 key 的哈希值 hash。如果找到了元素，则把元素的值存储在指向 value 的指针中，并返回该元素在哈希表中的索引；如果没找到元素，则返回 -1。在不同的情况下，dk_lookup 可以指向不同的查找函数，例如 lookdict()、lookdict_unicode() 等。

需要注意的是，如果函数调用过程中发生了异常，该函数会尝试保留异常信息，查找完成后再恢复之前的异常。

字典新增元素

int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{PyDictObject *mp;Py_hash_t hash;if (!PyDict_Check(op)) {PyErr_BadInternalCall();return -1;}assert(key);assert(value);mp = (PyDictObject *)op;if (!PyUnicode_CheckExact(key) ||(hash = ((PyASCIIObject *) key)->hash) == -1){hash = PyObject_Hash(key);if (hash == -1)return -1;}if (mp->ma_keys == Py_EMPTY_KEYS) {return insert_to_emptydict(mp, key, hash, value);}/* insertdict() handles any resizing that might be necessary */return insertdict(mp, key, hash, value);
}

PyDict_SetItem是向字典中设置一个键值对的函数，其参数包括一个指向待操作字典的指针 op，一个键 key 和一个值 value。

首先，PyDict_SetItem检查 op 是否是一个字典，如果不是，则返回错误。

接着，key 被哈希并存储在变量 hash 中，如果 key 不是 Unicode 对象或者 hash 值为 -1，则调用 PyObject_Hash 对 key 进行哈希。如果 PyObject_Hash 失败，则返回错误。

然后，如果字典为空（即不存在键值对），则调用 insert_to_emptydict 将键值对添加到字典中。如果字典非空，则调用 insertdict 函数将键值对添加到字典中，并处理可能需要的重新哈希和重新分配内存等操作。最后，函数返回一个整数，表示操作是否成功。

// Same to insertdict but specialized for ma_keys = Py_EMPTY_KEYS.
static int
insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,PyObject *value)
{assert(mp->ma_keys == Py_EMPTY_KEYS);PyDictKeysObject *newkeys = new_keys_object(PyDict_MINSIZE);if (newkeys == NULL) {return -1;}if (!PyUnicode_CheckExact(key)) {newkeys->dk_lookup = lookdict;}dictkeys_decref(Py_EMPTY_KEYS);mp->ma_keys = newkeys;mp->ma_values = NULL;Py_INCREF(key);Py_INCREF(value);MAINTAIN_TRACKING(mp, key, value);size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys);dictkeys_set_index(mp->ma_keys, hashpos, 0);ep->me_key = key;ep->me_hash = hash;ep->me_value = value;mp->ma_used++;mp->ma_version_tag = DICT_NEXT_VERSION();mp->ma_keys->dk_usable--;mp->ma_keys->dk_nentries++;return 0;
}

insert_to_emptydict 函数是用于将一个键值对添加到一个空的字典中的函数。它会创建一个新的 PyDictKeysObject 对象，指向的数组大小为 PyDict_MINSIZE，并将指定的键值对存储在该数组中的第一个位置。函数返回0表示成功，返回-1表示失败。在添加键值对之前，函数会增加键和值的引用计数，并在字典中记录这些引用，以便可以在之后跟踪这些对象。如果函数成功，它会更新字典的计数器和版本标记。如果出现任何错误，它会清理之前增加的引用计数并返回 -1。

/*
Internal routine to insert a new item into the table.
Used both by the internal resize routine and by the public insert routine.
Returns -1 if an error occurred, or 0 on success.
*/
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{PyObject *old_value;PyDictKeyEntry *ep;Py_INCREF(key);Py_INCREF(value);if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {if (insertion_resize(mp) < 0)goto Fail;}Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);if (ix == DKIX_ERROR)goto Fail;assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);MAINTAIN_TRACKING(mp, key, value);/* When insertion order is different from shared key, we can't share* the key anymore.  Convert this instance to combine table.*/if (_PyDict_HasSplitTable(mp) &&((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||(ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {if (insertion_resize(mp) < 0)goto Fail;ix = DKIX_EMPTY;}if (ix == DKIX_EMPTY) {/* Insert into new slot. */assert(old_value == NULL);if (mp->ma_keys->dk_usable <= 0) {/* Need to resize. */if (insertion_resize(mp) < 0)goto Fail;}Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);ep->me_key = key;ep->me_hash = hash;if (mp->ma_values) {assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);mp->ma_values[mp->ma_keys->dk_nentries] = value;}else {ep->me_value = value;}mp->ma_used++;mp->ma_version_tag = DICT_NEXT_VERSION();mp->ma_keys->dk_usable--;mp->ma_keys->dk_nentries++;assert(mp->ma_keys->dk_usable >= 0);ASSERT_CONSISTENT(mp);return 0;}if (old_value != value) {if (_PyDict_HasSplitTable(mp)) {mp->ma_values[ix] = value;if (old_value == NULL) {/* pending state */assert(ix == mp->ma_used);mp->ma_used++;}}else {assert(old_value != NULL);DK_ENTRIES(mp->ma_keys)[ix].me_value = value;}mp->ma_version_tag = DICT_NEXT_VERSION();}Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */ASSERT_CONSISTENT(mp);Py_DECREF(key);return 0;Fail:Py_DECREF(value);Py_DECREF(key);return -1;
}

这是 Python 字典对象中用于插入新条目的内部函数 insertdict 的实现代码。它用于将新的键值对插入到字典中。该函数有三个参数：字典对象 mp，键 key 和值 value。

在插入之前，我们需要确保 key 和 value 的引用计数都增加了，以防止它们被误释放。如果字典对象拥有拆分表，且键不是 Unicode 字符串，就需要进行插入大小调整，调用 insertion_resize 函数。这是因为拆分表的索引只是包含字符集合的子集，所以添加元素时可能会出现哈希冲突，导致拆分表无法正确解决冲突。

接下来，调用字典键查找函数 mp->ma_keys->dk_lookup 来查找键在字典中的位置，如果找到，则将新值赋给原位置的值。如果键在字典中没有找到，就将新键值对插入到字典中。如果字典对象没有拆分表，则将新键值对放入 me_value 字段中。如果字典对象拥有拆分表，则将值放入 ma_values 中相应的索引中。

如果没有找到空闲位置，则需要进行扩容。我们需要为新条目找到一个空闲的哈希槽，并将该槽的索引插入到 dk_indices 数组中。新条目的指针存储在键入表中的相应索引处，存储新值。

最后，我们需要在引用计数计数中减少旧值的引用计数，以防止内存泄漏，将键的引用计数减少，以使字典对象正确工作，并返回成功或失败的结果。

网络标签：

相关问题