哈希 table quadrtc。试探

Question

需要一个例子

我需要给出 table 的大小和我尝试插入的元素，在 table 超过一半后由于碰撞我无法插入。

我在 table 大小上尝试了一些不同的输入，其功能是： h of i (x) = (hash(x) + f(i)) mod table 大小

f(i)= i^2

如有任何帮助，我将不胜感激。

Answer 1

对于尺寸为 7 的 table 假设位置 0、1、2、4 已占用，3、5、6 是空闲的。现在尝试插入一个 x，其中 hash(x) = 0.

示例：我们取 hash(x) = x % 7.

Insert 0: hash(0) = 0, this slot is free so insert 0 into slot 0
Insert 1: hash(1) = 1, this slot is free so insert 1 into slot 1
Insert 2: hash(2) = 2, this slot is free so insert 2 into slot 2
Insert 4: hash(4) = 4, this slot is free so insert 4 into slot 4
Insert 7: hash(7) = 0, slot 0 is already taken; start quadratic probing:
(0+1*1)%7 = 1 also taken
(0+2*2)%7 = 4 also taken
(0+3*3)%7 = 2 also taken
(0+4*4)%7 = 2 also taken
(0+5*5)%7 = 4 also taken
(0+6*6)%7 = 1 also taken
...

哈希 table quadrtc。试探

Hash table quadrtc. probing

algorithm

hashtable

quadratic-probing