字典的自定義方法是怎么實(shí)現(xiàn)的？
作者：古明地覺(jué)
由于 dk_nentries = 5，說(shuō)明鍵值對(duì)數(shù)組用了 5 個(gè) entry，而在之后，第 2 個(gè)和第 5 個(gè) entry 被刪除了。一旦刪除，那么它的 me_key 和 me_value 會(huì)被重置為 NULL，和初始 entry 是等價(jià)的。
楔子
上一篇文章我們介紹了字典的創(chuàng)建過(guò)程，和一些基本操作，這些操作都對(duì)應(yīng)一個(gè)魔法方法。但除了這些魔法方法之外，每個(gè)對(duì)象還可以單獨(dú)定義很多自己的方法，這些方法統(tǒng)一由類(lèi)型對(duì)象的 tp_methods 字段維護(hù)，當(dāng)然這些之前已經(jīng)說(shuō)過(guò)了。
圖片
里面有很多的自定義方法，比如 get、pop、setdefault 等等，我們來(lái)剖析一下。
字典的 get 方法
獲取指定 key 對(duì)應(yīng)的 value，如果 key 不存在，那么返回默認(rèn)值。
d = {"name": "陳詩(shī)萌"}
print(d.get("name"))
"""
陳詩(shī)萌
"""
# key 不存在，返回默認(rèn)值 None
print(d.get("desc"))
"""
None
"""
# 當(dāng)然也可以指定默認(rèn)值
print(d.get("desc", "都柏林美少女"))
"""
都柏林美少女
"""下面看一下源碼實(shí)現(xiàn)。
// Objects/clinc/dictobject.c.h
#define DICT_GET_METHODDEF \
{"get", _PyCFunction_CAST(dict_get), METH_FASTCALL, dict_get__doc__},
static PyObject *
dict_get(PyDictObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 返回值
PyObject *return_value = NULL;
// 指定的 key
PyObject *key;
// 默認(rèn)值，默認(rèn)為 None
PyObject *default_value = Py_None;
// get 方法接收 1 ~ 2 個(gè)參數(shù)
if (!_PyArg_CheckPositional("get", nargs, 1, 2)) {
goto exit;
}
// args[0] 便是指定的 key
key = args[0];
if (nargs < 2) {
goto skip_optional;
}
// args[1] 便是傳入的默認(rèn)值，如果有的話
default_value = args[1];
skip_optional:
return_value = dict_get_impl(self, key, default_value);
exit:
return return_value;
}
// Objects/dictobject.c
static PyObject *
dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
{
PyObject *val = NULL;
Py_hash_t hash; // 哈希值
Py_ssize_t ix; // 哈希槽存儲(chǔ)的鍵值對(duì)數(shù)組的索引
// 計(jì)算哈希值
if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return NULL;
}
// 獲取 key 對(duì)應(yīng)的哈希槽存儲(chǔ)的鍵值對(duì)數(shù)組的索引
ix = _Py_dict_lookup(self, key, hash, &val);
if (ix == DKIX_ERROR)
return NULL;
// key 不存在，那么將默認(rèn)值賦值給 val
if (ix == DKIX_EMPTY || val == NULL) {
val = default_value;
}
// 增加 val 的引用計(jì)數(shù)，然后返回
return Py_NewRef(val);
}以上就是字典的 get 方法，非常簡(jiǎn)單。
字典的 setdefault 方法
這是一個(gè)非常強(qiáng)大的方法，但是用的人不是很多。它和 get 方法類(lèi)似，都是傳入一個(gè) key 和一個(gè)默認(rèn)值，如果 key 存在，那么返回 key 對(duì)應(yīng)的 value，否則返回默認(rèn)值。
但它和 get 方法不同的是，setdefault 在 key 不存在時(shí)，會(huì)將 key 和默認(rèn)值添加到字典中。
d = {"name": "陳詩(shī)萌"}
# 當(dāng) key 存在時(shí)，兩個(gè)方法的效果是一樣的，都等價(jià)于 d[key]
print(d.get("name"))
print(d.setdefault("name"))
"""
陳詩(shī)萌
陳詩(shī)萌
"""
# 但當(dāng) key 不存在時(shí)，就有差別了
# "desc" 這個(gè) key 不存在，返回默認(rèn)值
print(d.get("desc", "都柏林美少女"))
"""
都柏林美少女
"""
# 并且原始的字典不受影響
print(d)
"""
{'name': '陳詩(shī)萌'}
"""
# 但對(duì)于 setdefault 來(lái)說(shuō)，key 不存在時(shí)
# 會(huì)將 key 和默認(rèn)值添加進(jìn)去，然后返回默認(rèn)值
print(d.setdefault("desc", "都柏林美少女"))
"""
都柏林美少女
"""
# 原始的字典會(huì)發(fā)生改變
print(d)
"""
{'name': '陳詩(shī)萌', 'desc': '都柏林美少女'}
"""所以當(dāng)獲取的 key 不存在時(shí)，v = d.setdefault(key, value) 等價(jià)于如下。
- d[key] = value
- v = d[key]
那么 setdefault 一般用在什么地方呢？舉個(gè)例子。
data = [
("陳詩(shī)萌", "2020", 5), ("陳詩(shī)萌", "2020", 2),
("陳詩(shī)萌", "2021", 1), ("陳詩(shī)萌", "2021", 4), ("陳詩(shī)萌", "2021", 3),
("高老師", "2022", 7), ("高老師", "2022", 3), ("高老師", "2022", 3),
("高老師", "2023", 4), ("高老師", "2023", 1)
]
# 對(duì)于上面這種數(shù)據(jù)，我們需要變成下面這個(gè)樣子
"""
{
'陳詩(shī)萌': {
'2020': [5, 2],
'2021': [1, 4, 3]
},
'高老師': {
'2022': [7, 3, 3],
'2023': [4, 1]
}
}
"""
# 如果使用 setdefault 方法，就非常好解決了
d = {}
for name, year, cnt in data:
d.setdefault(name, {}).setdefault(year, []).append(cnt)
print(d)下面來(lái)看一下源碼實(shí)現(xiàn)。
// Objects/clinc/dictobject.c.h
#define DICT_SETDEFAULT_METHODDEF \
{"setdefault", _PyCFunction_CAST(dict_setdefault), \
METH_FASTCALL, dict_setdefault__doc__},
static PyObject *
dict_setdefault(PyDictObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 這部分和 get 方法是類(lèi)似的
PyObject *return_value = NULL;
PyObject *key;
PyObject *default_value = Py_None;
if (!_PyArg_CheckPositional("setdefault", nargs, 1, 2)) {
goto exit;
}
key = args[0];
if (nargs < 2) {
goto skip_optional;
}
default_value = args[1];
skip_optional:
return_value = dict_setdefault_impl(self, key, default_value);
exit:
return return_value;
}
// Objects/dictobject.c
static PyObject *
dict_setdefault_impl(PyDictObject *self, PyObject *key,
PyObject *default_value)
{
PyObject *val;
val = PyDict_SetDefault((PyObject *)self, key, default_value);
return Py_XNewRef(val);
}所以核心在于 PyDict_SetDefault 函數(shù)，這個(gè)函數(shù)比較長(zhǎng)，但邏輯不難理解。
// Objects/dictobject.c
PyObject *
PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
{
PyDictObject *mp = (PyDictObject *)d;
PyObject *value;
Py_hash_t hash;
PyInterpreterState *interp = _PyInterpreterState_GET();
if (!PyDict_Check(d)) {
PyErr_BadInternalCall();
return NULL;
}
// 獲取哈希值
if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return NULL;
}
// 如果 mp->ma_keys 等于 Py_EMPTY_KEYS，證明字典是空的，那么 key 肯定不存在
// 將 key 和 defaultobj 添加進(jìn)字典中，并返回 defaultobj
if (mp->ma_keys == Py_EMPTY_KEYS) {
if (insert_to_emptydict(interp, mp, Py_NewRef(key), hash,
Py_NewRef(defaultobj)) < 0) {
return NULL;
}
return defaultobj;
}
// 如果 key 不是字符串，但當(dāng)前字典是 Unicode table
// 意味著字典的結(jié)構(gòu)要發(fā)生改變，調(diào)用 insertion_resize，該方法后續(xù)會(huì)聊
if (!PyUnicode_CheckExact(key) && DK_IS_UNICODE(mp->ma_keys)) {
if (insertion_resize(interp, mp, 0) < 0) {
return NULL;
}
}
// 獲取哈希槽存儲(chǔ)的鍵值對(duì)數(shù)組的索引
Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return NULL;
// 如果 ix == -1，說(shuō)明 key 不存在，那么要先添加鍵值對(duì)
if (ix == DKIX_EMPTY) {
uint64_t new_version = _PyDict_NotifyEvent(
interp, PyDict_EVENT_ADDED, mp, key, defaultobj);
// 當(dāng)字典的 key 集合發(fā)生改變時(shí)，dk_version 要重置為 0
mp->ma_keys->dk_version = 0;
// value 等于默認(rèn)值
value = defaultobj;
// 是否還有可用空間，如果沒(méi)有，調(diào)用 insertion_resize
if (mp->ma_keys->dk_usable <= 0) {
if (insertion_resize(interp, mp, 1) < 0) {
return NULL;
}
}
// 返回 key 映射之后的哈希槽的索引
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
// 新添加的 entry 在鍵值對(duì)數(shù)組中的索引為 mp->ma_keys->dk_nentries
// 將該索引賦值給 dk_indices[hashpose]
dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
// 如果字典的 key 全部是字符串
if (DK_IS_UNICODE(mp->ma_keys)) {
assert(PyUnicode_CheckExact(key));
// 那么 entry 由 PyDictUnicodeEntry 結(jié)構(gòu)體表示
PyDictUnicodeEntry *ep = \
&DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
ep->me_key = Py_NewRef(key); // 增加 key 的引用計(jì)數(shù)
// 如果字典是分離表
if (_PyDict_HasSplitTable(mp)) {
Py_ssize_t index = (int)mp->ma_keys->dk_nentries;
assert(index < SHARED_KEYS_MAX_SIZE);
assert(mp->ma_values->values[index] == NULL);
// 值由 mp->ma_values 存儲(chǔ)
mp->ma_values->values[index] = Py_NewRef(value);
_PyDictValues_AddToInsertionOrder(mp->ma_values, index);
}
// 如果字典是結(jié)合表，那么鍵和值均保存在 entry 中
else {
ep->me_value = Py_NewRef(value);
}
}
// 說(shuō)明字典的 key 不全是字符串，此時(shí) entry 由 PyDictKeyEntry 結(jié)構(gòu)體表示
// 并且此時(shí)字典一定是結(jié)合表
else {
// 設(shè)置 me_key、me_value、me_hash
PyDictKeyEntry *ep = \
&DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
ep->me_key = Py_NewRef(key);
ep->me_hash = hash;
ep->me_value = Py_NewRef(value);
}
MAINTAIN_TRACKING(mp, key, value);
mp->ma_used++; // 字典的長(zhǎng)度加 1
mp->ma_version_tag = new_version; // 版本號(hào)改變
mp->ma_keys->dk_usable--; // 鍵值對(duì)數(shù)組中可用元素的個(gè)數(shù)減 1
mp->ma_keys->dk_nentries++; // 鍵值對(duì)數(shù)組中已存儲(chǔ)的元素的個(gè)數(shù)加 1
assert(mp->ma_keys->dk_usable >= 0);
}
// ...
ASSERT_CONSISTENT(mp);
// 返回 value
return value;
}以上便是 setdefault 方法。
字典的 popitem 方法
字典的 pop 方法之前已經(jīng)說(shuō)過(guò)了，這里來(lái)看一下 popitem 方法。
d = {"x": 1, "y": 2, "z": 3}
# pop 方法可以彈出指定的 key，并返回對(duì)應(yīng)的 value
# 如果 key 不存在，并且沒(méi)有指定默認(rèn)值，會(huì)拋出 KeyError，否則返回默認(rèn)值
print(d.pop("x")) # 1
# 而 popitem 方法則是彈出字典的最后一個(gè)鍵值對(duì)
d = {"x": 1, "y": 2, "z": 3}
print(d.popitem()) # ('z', 3)
print(d) # {'x': 1, 'y': 2}下面看一下源碼實(shí)現(xiàn)。
// Objects/clinc/dictobject.c.h
#define DICT_POPITEM_METHODDEF \
{"popitem", (PyCFunction)dict_popitem, METH_NOARGS, dict_popitem__doc__},
static PyObject *
dict_popitem(PyDictObject *self, PyObject *Py_UNUSED(ignored))
{
return dict_popitem_impl(self);
}
// Objects/dictobject.c
static PyObject *
dict_popitem_impl(PyDictObject *self)
{
Py_ssize_t i, j;
PyObject *res;
uint64_t new_version;
PyInterpreterState *interp = _PyInterpreterState_GET();
// 返回值，一個(gè)二元組，負(fù)責(zé)存儲(chǔ) key 和 value
res = PyTuple_New(2);
if (res == NULL)
return NULL;
// 如果字典的長(zhǎng)度為 0，那么拋出 KeyError
if (self->ma_used == 0) {
Py_DECREF(res);
PyErr_SetString(PyExc_KeyError, "popitem(): dictionary is empty");
return NULL;
}
// 如果字典使用分離表，那么當(dāng) popitem 之后，要重構(gòu)為結(jié)合表
if (self->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
if (dictresize(interp, self, DK_LOG_SIZE(self->ma_keys), 1)) {
Py_DECREF(res);
return NULL;
}
}
// 字典的 key 集合發(fā)生改變時(shí)，dk_version 要重置為 0
self->ma_keys->dk_version = 0;
PyObject *key, *value;
Py_hash_t hash;
// 字典所有的 key 都是字符串
if (DK_IS_UNICODE(self->ma_keys)) {
PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(self->ma_keys);
// ma_keys->dk_nentries 表示鍵值對(duì)數(shù)組中已使用的元素個(gè)數(shù)
// 那么 entry 的最大索引就是 ma_keys->dk_nentries - 1
i = self->ma_keys->dk_nentries - 1;
// 從 i 開(kāi)始往前遍歷，找到第一個(gè) me_value != NULL 的 entry
// 因?yàn)楸粍h除的 entry 依舊會(huì)駐留在鍵值對(duì)數(shù)組中，但 me_key、me_value 被設(shè)置為 NULL
while (i >= 0 && ep0[i].me_value == NULL) {
i--;
}
assert(i >= 0);
// 獲取 key
key = ep0[i].me_key;
new_version = _PyDict_NotifyEvent(
interp, PyDict_EVENT_DELETED, self, key, NULL);
hash = unicode_get_hash(key);
// 獲取 value
value = ep0[i].me_value;
// 因?yàn)楸粡棾隽?，所?entry 的 me_key 和 me_value 要重置為 NULL
ep0[i].me_key = NULL;
ep0[i].me_value = NULL;
}
// 字典的 key 不全是字符串，代碼和上面是類(lèi)似的
else {
PyDictKeyEntry *ep0 = DK_ENTRIES(self->ma_keys);
i = self->ma_keys->dk_nentries - 1;
while (i >= 0 && ep0[i].me_value == NULL) {
i--;
}
assert(i >= 0);
key = ep0[i].me_key;
new_version = _PyDict_NotifyEvent(
interp, PyDict_EVENT_DELETED, self, key, NULL);
hash = ep0[i].me_hash;
value = ep0[i].me_value;
ep0[i].me_key = NULL;
ep0[i].me_hash = -1;
ep0[i].me_value = NULL;
}
// 基于哈希值和哈希槽存儲(chǔ)的索引，獲取哈希槽的索引
j = lookdict_index(self->ma_keys, hash, i);
assert(j >= 0);
assert(dictkeys_get_index(self->ma_keys, j) == i);
// 將索引為 j 的哈希槽存儲(chǔ)的值設(shè)置為 DKIX_DUMMY
dictkeys_set_index(self->ma_keys, j, DKIX_DUMMY);
// res = (key, value)
PyTuple_SET_ITEM(res, 0, key);
PyTuple_SET_ITEM(res, 1, value);
// 這一步一會(huì)兒解釋
self->ma_keys->dk_nentries = i;
// 鍵值對(duì)個(gè)數(shù)減 1
self->ma_used--;
self->ma_version_tag = new_version;
ASSERT_CONSISTENT(self);
return res;
}以上就是 popitem 方法，但是里面有一行 self->ma_keys->dk_nentries = i; 估計(jì)讓人有些費(fèi)解，我們解釋一下。
首先當(dāng)鍵值對(duì)數(shù)組的空間申請(qǐng)之后，entry 就已經(jīng)存在了，初始狀態(tài)下的 entry 的 me_key 和 me_value 均為 NULL。所以一個(gè)被偽刪除的 entry 和初始的 entry 是等價(jià)的，下面假設(shè)有這么一個(gè)鍵值對(duì)數(shù)組。
圖片
由于 dk_nentries = 5，說(shuō)明鍵值對(duì)數(shù)組用了 5 個(gè) entry，而在之后，第 2 個(gè)和第 5 個(gè) entry 被刪除了。一旦刪除，那么它的 me_key 和 me_value 會(huì)被重置為 NULL，和初始 entry 是等價(jià)的。
這時(shí)候如果執(zhí)行 popitem，那么會(huì)彈出最后一個(gè) me_value 不為 NULL 的 entry，即沒(méi)有被偽刪除的 entry，對(duì)于當(dāng)前來(lái)說(shuō)就是第 4 個(gè) entry。
所以源碼中的 i 初始等于 dk_nentries - 1，然后往前遍歷，最終會(huì)找到索引為 3 的 entry，所以循環(huán)之后 i = 3。然后將索引為 3 的 entry 的 me_key 和 me_value 設(shè)置為 NULL，因?yàn)樗粍h除了。
注意：這里關(guān)鍵來(lái)了，既然變量 i 保存的是最后一個(gè) me_value != NULL 的 entry 的索引，那么當(dāng)它被刪除之后，就意味著從索引 i 開(kāi)始，后面所有的 entry 都相當(dāng)于回歸到了初始狀態(tài)。
圖片
由于 dk_nentries 會(huì)被設(shè)置為 i，后續(xù)再添加鍵值對(duì)時(shí)，會(huì)添加到索引為 i 的位置。對(duì)于當(dāng)前來(lái)說(shuō)，添加鍵值對(duì)時(shí)，修改的是 dk_entries[3] 的 me_key 和 me_value，而不是 dk_entries[5] 的 me_key 和 me_value。
所以通過(guò) popitem 方法，被刪除的 entry 是有可能實(shí)現(xiàn)復(fù)用的。
責(zé)任編輯：武曉燕
來(lái)源：
古明地覺(jué)的編程教室
