二度哈希（rehashing / double hashing）

1、二度哈希的工作原理如下：

有一个包含多个哈希函数（H1……Hn）的集合。当我们要从哈希表中添加或获取元素时，首先使用哈希函数H1。如果导致冲突，则尝试使用H2，一直到Hn。各个哈希函数极其相似，不同的是它们选用的乘法因子。通常，哈希函数Hk的定义如下：
Hk(key) = [GetHash(key) + k * (1 + (( (GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

2、双重散列法(Double Hashing)
该方法是开放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key) )％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列为：
d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。

定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

若 m 为素数，则 h1(key) 取 1 到 m-1 之间的任何数均与 m 互素，因此，我们可以简单地将它定义为：
h1(key)=key ％ (m-2)+1

巴特西

double hashing 双重哈希

二度哈希（rehashing / double hashing）

最新文章

热门文章