python2源码PyDictObject——lookdict_

PyDictObject包含两种不同搜索策略：lookdict和lookdict_string。两者使用相同的算法，但后者是针对PyStringObject的特化形式，其假设PyDictObject对象中每个entry的key都是PyStringObject*。

static PyDictEntry *
lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i; // size_t 是一个unsigned int
    register size_t perturb;
    register PyDictEntry *freeslot; // 指向探测序列第一个dummy态的entry
    register size_t mask = (size_t)mp->ma_mask; // ma_mask记录PyDictObject对象的entry个数
    PyDictEntry *ep0 = mp->ma_table; // ma_table记录PyDictObject每个槽位的对象
    register PyDictEntry *ep;

    /* Make sure this function doesn't have to handle non-string keys,
       including subclasses of str; e.g., one reason to subclass
       strings is to override __eq__, and for speed we don't cater to
       that here. */
    //lookdict_string只能用于string类型的查找，若判断非string，则转为lookdict
    if (!PyString_CheckExact(key)) { 
#ifdef SHOW_CONVERSION_COUNTS
        ++converted;
#endif
        mp->ma_lookup = lookdict;
        return lookdict(mp, key, hash);
    }
    // 将hash值与mask做与运算，找到对应的slot，防止下标溢出（hash值可能很大，超过mask）
    i = hash & mask;
    // 取该hash对应的对象
    ep = &ep0[i];
    // 若该对象为ununsed或key值相等，则直接返回
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;
    // 若该对象为dummy，记录freeslot
    if (ep->me_key == dummy)
        freeslot = ep;
    else {
        // 对于active对象，如果hash值相等，且string判断也相等，则同样返回
        //此处string为简单的_PyString_Eq，而lookdict为PyObject_RichCompareBool
        //因此对于纯string查找，速度更快
        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) {
        // 冲突的情况，在此找到下一个slot，并循环判断直至返回
        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;
}