关于散列——二次探测证明

Question

我正在研究散列的冲突解决方法，尤其是在开放寻址中（例如线性探测、二次探测）。线性探测很容易理解，因为它指的是

index = hash(value)
for i, 0 -> SIZE
   seek_index = (index + i) % SIZE
   if map[seek_index] is EMPTY
      //proceed insertion

但是对于二次探测，我不知道什么时候需要搜索空槽？

index = hash(value)
for i, 0 -> SIZE    // Is it should be up to SIZE ?
   seek_index = (index + i*i) % SIZE
   if map[seek_index] is EMPTY
      //proceed insertion

如果限制是 SIZE 或其他任何东西，如果在地图中存在，我将得到 EMPTY 单元格的证据是什么？

任何参考将不胜感激。

Answer 1

不能保证您会探测到数组中的每个元素。

例如，考虑 SIZE=5。然后你将在索引 0、1²、2²、3²、4² 处探测（相对于 index），其中 (modulo 5) 是 0、1、4、4、1。所以如果空格位于索引 2 或 3（相对于 index），那么您将找不到它们。

正方形 mod n 称为 "quadratic residues"、and the number of quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).

关于散列——二次探测证明

Regarding Hashing - Quadratic Probing Proof

algorithm

hash

hashtable

hashmap

data-structures