algorithm - 关于散列 - 二次探测证明

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

如果限制是“大小”或其他任何内容，那么有什么证据可以证明我将在 map 中获得空单元格？

任何引用都将不胜感激。

Answer 1

无法保证您会探测数组中的每个元素。

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

平方 mod n 称为“二次余数”，and the number of quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).