python - 在散列冲突中，CPython 如何知道哪个值存储在索引 HASHVALUE 以及哪个值存储在 RESOLUTIONINDEX

Question

如果我有一个字典，例如 { key1 : value1, key2 : value2,..., key17:value17 }，并且 2 个键给出相同的散列，比如 key13 和 key5散列时给出 12，据我所知，python 实现了一种冲突解决方法(如果我没记错的话，开放寻址)来解决这个问题。因此，假设 value5 将存储在索引 12 中，而 value13 将存储在另一个由冲突解决方法确定的开放索引中。

这是让我感到困惑的棘手部分:为了检索值(例如从 key5 中)，CPython 解释器是否对键进行哈希处理并从索引 HASHVALUE 中检索值？这不可能是对的，因为解释器如何知道 value13 是否属于 key5，或者它是否由于冲突位于不同的索引中？

我试着查看 https://github.com/python/cpython/blob/master/Objects/dictobject.c#L1041 中的 C 代码

功能好像是

PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{
    Py_hash_t hash;
    PyDictObject *mp = (PyDictObject *)op;
    PyDictKeyEntry *ep;
    PyThreadState *tstate;
    PyObject **value_addr;

    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: try
       #running "python -Wi" for an example related to string interning.
       #Let's just hope that no exception occurs then...  This must be
       #_PyThreadState_Current and not PyThreadState_GET() because in debug
       #mode, the latter complains if tstate is NULL. */
    tstate = (PyThreadState*)_Py_atomic_load_relaxed(
        &_PyThreadState_Current);
    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);
        ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr);
       # /* ignore errors */
        PyErr_Restore(err_type, err_value, err_tb);
        if (ep == NULL)
            return NULL;
    }
    else {
        ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr);
        if (ep == NULL) {
            PyErr_Clear();
            return NULL;
        }
    }
    return *value_addr;
}

但是我的 C 知识非常缺乏，坦率地说，我不明白其中一半说的是什么。

Answer 1

键与其关联的值一起存储

CPython 哈希表中的每个索引都与一个结构相关联，该结构包括三个字段:哈希值、键指针和值指针:

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

它如何处理哈希冲突

在您的场景中，{hash5, key5, value5} 存储在索引 12 处，{hash13, key13, value13} 是存储在由开放寻址冲突解决方案选择的备用索引中。

在索引 12 处查找 key5 时，Python 会验证该键是否匹配，然后返回关联的 value5。

相反，当第一次在索引 12 处查找 key13 时，Python 注意到 key13 != key5 并且不会返回 value5 。相反，它跳转到 key13 匹配的备用索引，然后返回关联的 value13。

结论

您问“CPython 如何知道哪个值存储在索引 HASHVALUE 以及哪个值存储在 RESOLUTIONINDEX”。答案是值与关联的键一起存储，从而可以知道哪个值与哪个键相关联。