【Python旧时笔记 六】PyDictObject的哈希算法和搜索过程

zhufeng518

哈希函数如下：long
PyObject_Hash(PyObject*v)
{
PyTypeObject*tp=v->ob_type;
if(tp->tp_hash!=NULL)
return(*tp->tp_hash)(v);
/* To keep to the general practice that inheriting
* solely from object in C code should work without
* an explicit call to PyType_Ready, we implicitly call
* PyType_Ready here and then check the tp_hash slot again
*/
if(tp->tp_dict==NULL){
if(PyType_Ready(tp)< 0)
return-1;
if(tp->tp_hash!=NULL)
return(*tp->tp_hash)(v);
}
if(tp->tp_compare==NULL&&RICHCOMPARE(tp)==NULL) {
return_Py_HashPointer(v);/*Use address as hash value */
}
/* If there's a cmp but no hash defined, the object can't be hashed */
returnPyObject_HashNotImplemented(v);
}


搜索过程则是根据hash值确定表项位置，进行比较。
如果表项比较成功或者表现是Unused状态，返回。
如果表现是Dummy状态，则设置freeslot指向该位置，并向下一个位置进行比较。
for(perturb=hash;;perturb>>=PERTURB_SHIFT) {
i= (i<<2) +i+perturb+ 1;
ep= &ep0[i&mask];