E0de327ecde7cc9c634a701570362780
Python字典对象的搜索过程及优化

Python字典对象的搜索过程及优化

上周我们探讨了《Python字典对象的实现》,但是还剩下一个比较重要的环节就是Python字典对象搜索的具体过程未能涉及,今天我们就一起来看看搜索过程及其优化的手段。

两种搜索算法

默认情况下,ma_lookup会使用lookdict_string进行搜索,也就是把需要查询的key当成是字符串。当然,如果key本身不是字符串的话,则会切换到lookdict这种通用模块,比如查询PyIntObject

为了减少本文的篇幅,我们直接探讨lookdict_string的实现模式,原理都是相同的:

static PyDictEntry *
lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i;
    register size_t perturb;
    register PyDictEntry *freeslot;
    register size_t mask = (size_t)mp->ma_mask;
    PyDictEntry *ep0 = mp->ma_table;
    register PyDictEntry *ep;

     // 第一部分
    i = hash & mask;
    ep = &ep0[i];
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;
    if (ep->me_key == dummy)
        freeslot = ep;
    else {
        if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
            return ep;
        freeslot = NULL;
    }

    // 第二部分
    /* In the loop, me_key == dummy is by far (factor of 100s) the
       least likely outcome, so test for that last. */
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
        if (ep->me_key == NULL)
            return freeslot == NULL ? ep : freeslot;
        if (ep->me_key == key
            || (ep->me_hash == hash
            && ep->me_key != dummy
            && _PyString_Eq(ep->me_key, key)))
            return ep;
        if (ep->me_key == dummy && freeslot == NULL)
            freeslot = ep;
    }
    assert(0);          /* NOT REACHED */
    return 0;
top Created with Sketch.