http://www.chilton-computing.org.uk/acl/literature/reports/p012.htm
作者：F R A Hopgood and J Davenport
最近因为一起疑似lucene BytesRefHash的bug (哈希表死循环),研究了下哈希表，发现好多之前自己没仔细思考过的东西，以上这篇1972年的论文解除了我很多困惑。
二次探测在哈希表长度为质数时可以做到搜索周期为M (我之前认为为M/2),在哈希表长度为2的幂时同样有办法做到，只要确定好两个参数，文中也给出了严格的证明。
以下为疑似lucene中BytesRefHash可能引起死循环的地方(未证实，怀疑):
public int get(BytesRef key, BytesRef scratch) {
int code = key.hashCode();
int pos = (code &
hashMask);
int e =
ords[pos];
while (e != -
1 && e <
count && !equals(e, key, scratch)) {
final int inc = ((code >>
8) + code) |
1;
code += inc;
pos = (code &
hashMask);
e =
ords[pos];
}
if (e >=
count) {
return -
1;
}
return e;
}
这里之所以用这么奇怪的再散列法，无非是怕二次聚集，但这种做法应该不是缓存友好的，并且我不知道search period是否足够大，如果不够大是可能死循环的。
