关于双重散列（double hashing）和Brent 改进算法(Brent’s improvement)的一道例题

关于双重散列（double hashing）和Brent 改进算法(Brent’s improvement)的一道例题

当我们用两个哈希函数的时候，探测的效率得到了提升，并且在一定程度上避免了聚集。

给出两个哈希函数 h1，h2 满足 h1，h2：K——> {0,1，...，m-1}

Double hashing：设定h(k,i) = (h1(k) + ih2(k)) mod m    其中（i = 0,1,2，...，m-1）；m为表长

h2(k)的选择：每个值k的探测顺序必须达到所有位置0, . . . ，m。这意味着h2(k)不等于0，并且它不能整除m，h2应该独立于h1来选择。

例题：m=7 , h1(k) = k mod 7, h2(k) = 1 + (k mod5)  对数据 10 19 31 22 14 16 进行双重散列

解：

k           10        19        31        22       14       16

h1(k)      3         5          3           1         0         2

h2(k)      1         5          2           3         3         5

对于10，19 没有冲突直接放入表中

h1(10) mod 7 = 3

h1(19) mod 7 = 5

对于31，