哈希表和Java中的二次探测帮助

Question

我真的需要帮助插入哈希表。我现在不完全明白。有人可以用外行的话来解释二次和线性探测吗？

public void insert(String key) 
{ 
    int homeLocation = 0; 
    int location = 0; 
    int count = 0; 

    if (find(key).getLocation() == -1) // make sure key is not already in the table 
    { 
     //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING ******** 
    } 
} 

这是我正在处理的代码。我不是要求任何人这样做，我真的需要帮助学习整个概念

任何帮助将不胜感激。

Answer 1

首先我们说的是开放地址（或封闭散列）的方法。如果前一个已被另一个使用，则需要处理计算新哈希码的冲突，这是因为hashamap的每个桶最多可以包含1个元素。

所以，你有两个参数的散列函数：

• v，用于计算哈希码的对象的值。
• t，这是i*f其中i，称为步长，就是你如果碰撞发生，f是迄今达成的碰撞次数增加，每次有什么对你的哈希函数。

以此为出发点，你有两种可能的功能：

H(v, t) = (H(v) + t) % n 
H(v, t) = (H(v) + c*t + d*t*t) % n 

第一个是线性函数，而第二个是二次一个（这里谈到这个tecnique的名称）。在哪里你应该知道什么% n是，c和d被选为常量来具有更好的散列函数。

实事求是地讲为线性探测：

• 你caculate H(x, 0)
• • 如果电池是自由的地方元素有
• • 如果电池被占用计算H(x, i)
• • • 如果电池是自由的地方，在新的地址元素
• • • 如果电池占据然后计算H(x, i+i)
• • • • 继续下去，直到你找到一个空单元格

为二次探测你做的是一样的，你从开始H(x,0)，然后H(x,i)然后H(x,i+i)，所涉及的散列函数有所不同，这将给步长赋予不同的权重。