箱猫日和

哈希表二次探测

最近重新看哈希表的东西，发现自己大致能看懂了。以下是自己从书中了解的几个重点。
二次探测是一个根据哈希函数散列到同一个位置即碰撞时重新查找的方式，具体来说，假如i是哈希函数得到的位置，如果i有值了，那么尝试查找i + 1×1，i + 2×2，i + 3×3…i + NxN。
其次和二次探测相关的是在哈希表的大小为一个质数，并且使用量在一半以下时出现碰撞或者聚类的机率很小。
下面写一下实现哈希表二次探测个人认为主要的两个点，剩下的就是一些具体实现的细节问题了。

查找下一个质数

在容量超过一半时重新散列。需要找到比当前表大小大一些的质数。个人实现如下（Java）：

public static int findNextPrime(int current) {
  int nextPrime = current;
  if(nextPrime % 2 == 0) nextPrime++;
  while(!isPrime(nextPrime)) {
    nextPrime += 2;
  }
  return nextPrime;
}

private static boolean isPrime(int number) {
  for (int i = 3; i <= Math.sqrt(number); i += 2) {
    if (number % i == 0) return false;
  }
  return true;
}

二次探测

二次散列每次增加的偏移都是平方数，实际计算时可以不用乘法，而是根据两个偏移的差。比如i + NxN和i + (N + 1)x(N + 1)，差为2N + 1，这样计算就方便多了。示例程序如下（Ruby）：

#!/usr/bin/env ruby

def find_pos(table, element)
  index = element % table.size
  offset, n = 1, 1
  while table[index]
    index += offset
    index %= table.size
    offset += n * 2 + 1 
    n += 1
  end 
  index
end

table = Array.new(10)
table[3] = 33
table[8] = 18
table[9] = 49
puts find_pos(table, 58) 
puts find_pos(table, 69)

xnnyygn