删除 Entry

删除字典中的 K-V 是更新字典最常用的操作，与设置已有 K-V 类似，在执行一切操作之前，需要先找到目标 dk_entries。我们知道字典的搜索函数是一个指针，以便在不同时期切换合适的搜索函数。通过搜索函数找到目标 entry 之后，再执行真正的 “删除” 操作，逻辑非常清晰：

查找 K-V；
删除 K-V。

这一波操作我们已经很熟悉了，主要功能在 delitem_common 中实现，让我们深入研究它。

删除 Entry

Entry 是 Dict 中真正的数据区，在具体的说 Dict->ma_keys->dk_entries[] 中。一对 K-V 通常被保存在 dk_entries 数组中，但 Dict 需要借助哈希表 dk_indices 快速定位 Key，并最终找到对应的 Value。释放 Entry 难度并不大，只要用 Py_DECREF 宏，将 Key 和 Value 的引用计数减 1 就可以了。

但是别忘记维护哈希表，让我们回顾之前的例子。对于一个字典

d = {
  9: “VALUE”,
  17: “APPLE”
  }

具体的创建过程可以参看 37 节。此时 d 的内部看起来这样：

对于 Key = 9 和 Key = 17，二者实际上发生了碰撞，都直接映射到哈希表中的位置 1，通过二次探测计数，将两个 Key 离散到整个哈希表中，探测链看起来如此：

当 Key 为 9 和 17 时，探测链都是从 dk_indices[1] 开始的。探测链在整个 dk_entries 数组中分散的跳跃，查看很费劲，我们将探测链按照顺序排列：

图中橙色部分标明了哈希表中对应的 dk_entries 索引。探测琏是如此重要，发生碰撞的 Key 会按照探测链的顺序占据哈希表的位置。搜索 Key 的时候会按照探测链逐一检查 ix 索引（橙色区域数字，表示当前位置对应 dk_entries 数组的索引号），负数表示无效，0 和正数表示有效的索引。如果我们先删除 d[9]，将探测链中对应位置设置为 DKIX_EMPTY 会发生什么呢？

#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)  /* Used internally */

为了清晰，我没有将删除掉的 d[9] 设置为灰色，而设置为红色！此时当我们尝试搜索 d[17] 会发现，依然会从 dk_indices[1] 开始检查，但是现在 dk_indices[1] 的值是 DKIX_EMPTY，即 Key 9 不存在！！看来真的删除元素是不可以的，有可能会截断其他发生碰撞 Key 的探测链，所以 Python 增加了额外的负值表示 “删除”： DKIX_DUMMY，也就是 -2。DKIX_DUMMY 用来表示在哈希表探测链中这一位置不再使用了，但与 DKIX_EMPTY 又不同，探测链中可能还有其他 Key 存在，应当继续探测下一位置。这是一个 “伪删除” 技术。当 d[9] 被删除，实际上 d 内部的样子：

Now，Show You the code!

// Objects/dictobject.c:1570

static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
               PyObject *old_value)
{
    // ··· ···

    // 找到哈希表中的位置
    Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);

    // ··· ···

    ep = &DK_ENTRIES(mp->ma_keys)[ix];

    // 设置哈希表中该位置为 DKIX_DUMMY， -2
    dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);

    // ··· ··· 

    // 减少 K、V 引用技术，“释放” 引用
    Py_DECREF(old_key);
    Py_DECREF(old_value);

    // ··· ···
}

删除 K-V 的操作可以总结为：

找到 Key 和它在哈希表中的位置；
设置哈希表此处为 -2；
“释放” Key 及对应的 Value 的引用。

可以在 lookdict 中确认搜索过程中，所有 DKIX_DUMMY 被 “跳过”：

// Objects/dictobject.c:766

    for (;;) {
        Py_ssize_t ix = dictkeys_get_index(dk, i);

        // ix 为 -1， DKIX_EMPTY
        if (ix == DKIX_EMPTY) {
            // ··· ···
            // return，退出 
        }

        // ix 为 0 和正数，有效索引
        if (ix >= 0) {
            // ··· ···
            // return，退出
        }

        // ix 为其他负数，实际上 3.8 版本只可能是 -2，DKIX_DUMMY
        // 跳过，继续计算探测链下一位置
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
    }

我们的分析是可靠的，确实如此！

Think In Python

40. Dict 是如何工作的（4）删除 K-V

删除 Entry