在散列冲突中，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 散列 table 中的每个索引都与包含三个字段的结构相关联：散列值、键指针和值指针：

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

哈希冲突的工作原理

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

在索引 12 处查找 key5 时，Python 验证键匹配，然后 return 关联 value5.

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

结论

你问的是如何 "CPython know which value is stored at index HASHVALUE and which value is stored at RESOLUTIONINDEX"。答案是值与关联的键一起存储，从而可以知道哪个值与哪个键关联。

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

In hash collision, how does CPython know which value is stored at index HASHVALUE and which value is stored at RESOLUTIONINDEX

python

hash

dictionary

collision

键与其关联值一起存储

哈希冲突的工作原理

结论