Dict 最重要的是 Key 的搜索，上一节已经大致搞清楚了搜索过程。Python 的搜索函数指针被保存在 ma_keys->dk_lookup 中，而 dk_lookup 可能的取值有：

• lookdict
• lookdict_unicode
• lookdict_unicode_nodummy

后面两种是 lookdict 针对 key 为 string 的优化版本搜索函数，实际上大体逻辑差异不大。

// Objects/dictobject.c:751

static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
         Py_hash_t hash, PyObject **value_addr)
{
    // 省略一些代码

top:
    dk = mp->ma_keys;

    // Key 实际在这里
    ep0 = DK_ENTRIES(dk);
    // 哈希表的长度 - 1，用来计算 Key 的哈希值对哈希表长度的余数
    mask = DK_MASK(dk);
    // perturb 的高位会被逐渐添加到哈希表探测中，避免大量 Key 碰撞。
    perturb = hash;
    // 第一次计算余数
    i = (size_t)hash & mask;

    for (;;) {
        // 第一次探测，获得哈希表[i] 记录
        Py_ssize_t ix = dictkeys_get_index(dk, i);
        // 此处为空记录
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return ix;
        }
        // 该探测点有有效 Key
        if (ix >= 0) {
            PyDictKeyEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            // 该探测点的 Key 与目标 Key 相同，找到目标
            if (ep->me_key == key) {
                // 返回对应 Value 和 Value 在 Entries 中的索引 ix
                *value_addr = ep->me_value;
                return ix;
            }
            // 省略一些碰撞处理
        }

        // 没有找到目标，计算哈希表中下一探测点位置
        // 将 Key 的哈希值高位移动，加入探测点计算，以获得更好的散列效果。
        perturb >>= PERTURB_SHIFT;
        // 计算哈希表下一探测点索引
        i = (i*5 + perturb + 1) & mask;
    }
    Py_UNREACHABLE();
}

与之前探讨的流程差异，主要是加入了哈希值高位的权重，避免频繁碰撞。这一系列查找函数会在需要对搜索字典 Key 的时候调用。

修改已有 K-V

对于 Dict，修改已有 Key 的值与在 Dict 中新增 Key 差异很小，区别在于操作前会先搜索字典的 Key，如果搜索到 Key，就地修改该 Key 的 value，否则就在哈希表中第一个找到的 Empty 位置，插入该 Key-Value。修改 Key 的关键函数是：

// Objects/dictobject.c:1521

int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)

该函数最终调用的是下面的函数：

// Objects/dictobject.c:1027

static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    // 省略一些代码

    Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);

    // ··· ···


    // 处理 splited 模式下的 Dict 新增元素
    if (/* 一系列条件 */) {
        // 该函数会整理 Dict，删除无用元素，并将 Dict 转换为 combined 模式
        if (insertion_resize(mp) < 0)
            goto Fail;
        ix = DKIX_EMPTY;
    }

    // 插入新 Key
    if (ix == DKIX_EMPTY) {
        // ··· ··· 忽略
        return 0;
    }

    // 关键代码！ 如果 Value 发生变化
    if (old_value != value) {

        // splited 模式下，修改 mp->ma_values[ix]
        if (_PyDict_HasSplitTable(mp)) {
            mp->ma_values[ix] = value;
            if (old_value == NULL) {
                /* pending state */
                assert(ix == mp->ma_used);
                mp->ma_used++;
            }
        }
        else {
            // combined 模式，修改 DK_ENTRIES(mp->ma_keys)[ix].me_value
            assert(old_value != NULL);
            DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
        }
        // ··· ···
    }

    // ··· ···
}

显然，修改已有 Key 的 Value 步骤是：

1. 在 Dict 的哈希表中检索该 Key；
2. 找到哈希表中的 dk_entries 或者 ma_values 索引记录；
3. 修改对应的 value。

需要特别注意一点，向 Dict 中增删元素，Dict 必须处于 combined 模式，即 key-value 都储存在 dk_entries 数组中，借助 insertion_resize 函数可以实现这样的功能，顺便会清理 Dict 中那些已经被 “删除” 的元素，稍后会涉及更多 insertion_resize 相关主题。