Cpython 2.7 分支中，dict 对象的源代码 lookdict 搜索算法

 

1 static PyDictEntry * 2 lookdict(PyDictObject *mp, PyObject *key, register long hash) 3 { 4     register size_t i; 5     register size_t perturb; 6     register PyDictEntry *freeslot; 7     register size_t mask = (size_t)mp->ma_mask; 8     PyDictEntry *ep0 = mp->ma_table; 9     register PyDictEntry *ep;10     register int cmp;11     PyObject *startkey;12 13     i = (size_t)hash & mask;14     ep = &ep0[i];15     if (ep->me_key == NULL || ep->me_key == key) //【1】16         return ep;17 18     if (ep->me_key == dummy)19         freeslot = ep;20     else {21 //进到这里说明 ep->me-key !=NULL && ep->me_key!=key && ep->me_key==Active22         if (ep->me_hash == hash) {23             startkey = ep->me_key;24             Py_INCREF(startkey);25             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); //[2]这里为啥要再比较一次？26             Py_DECREF(startkey);27             if (cmp < 0)28                 return NULL;29             if (ep0 == mp->ma_table && ep->me_key == startkey) {
   //[3]这里明显是相等的，为啥要再判断一次？30                 if (cmp > 0)31                     return ep;32             }33             else {34                 /* The compare did major nasty stuff to the35                  * dict:  start over.36                  * XXX A clever adversary could prevent this37                  * XXX from terminating.38                  */39                 return lookdict(mp, key, hash);40             }41         }42         freeslot = NULL;43     }

 

　　

两个问题无法理解：

　　1.1 dict 对象搜索算法中，进入【2】处已经说明了 ep->me_key!=key 这个条件成立，但是 【2】那里为啥要再次比较一次 me_key 和 key 呢？

百思不得其解！！！

      原因： 【1】处为两个指针做 == 比较，说明指针的内容相同，即指向的是同一对象

                  进入到流程【2】则说明两个对象指向不同的内存，但是在满足两个条件后也认为他们“相等”，从而返回对应的项目，条件如下：

                  一是 两个对象哈希值相等

                  二是 两个对象的值相等（比较算法由对象提供，通常是 __eq__方法）

     举例：dict[10000]=10,此时需要搜索 d[10000]对象的 entry 对象，搜索时 指向 10000 的Pyobject* 明显和之前 存入 dict[10000] 值时对应的

               Pyobject 指针不一致，此时 p(p->int(10000) me_key) != q(q->int(10000) key),因此不会进入流程 【1】

               但是 p,q同时满足规定的两个条件，即hash值和 ob_val 都一致，因此返回 p 处的 （key,value）entry

   

     1.2 [3]处 判断的条件明显是成立的（参见蓝色高亮部分），不理解为啥要重复判断一次，暂时想不通~