python字典的冲突处理

[yongcong wang]

CPyton的实现，伪码如下：

/* Starting slot */
slot = hash;

/* Initial perturbation value */
perturb = hash;
while (<slot is full> && <item in slot doesn't equal the key>) {
slot = (5*slot) + 1 + perturb;
perturb >>= 5;
// 补充下：5*slot通过(slot<<2)+slot实现，当然最后还要slot&mask
}

右移5位是通过统计得出的结果，比4位或6位产生更少的冲突

备忘，引擎的hash table可以参考下