在哈希冲突中,CPython如何知道在索引HASHVALUE中存储哪个值以及哪个值存储在RESOLUTIONINDEX中

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在哈希冲突中,CPython如何知道在索引HASHVALUE中存储哪个值以及哪个值存储在RESOLUTIONINDEX中，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2511字，纯文字阅读大概需要4分钟。

内容图文

如果我有一个dict,例如{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知识非常缺乏,我坦率地不明白这一半的含义.

解决方法:

密钥与其关联值一起存储

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会验证密钥是否匹配,然后返回关联的值5.

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

结论

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

内容总结

以上是互联网集市为您收集整理的在哈希冲突中,CPython如何知道在索引HASHVALUE中存储哪个值以及哪个值存储在RESOLUTIONINDEX中全部内容，希望文章能够帮你解决在哈希冲突中,CPython如何知道在索引HASHVALUE中存储哪个值以及哪个值存储在RESOLUTIONINDEX中所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端