java - 帮助处理 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

首先，我们讨论的是开放寻址(或封闭散列)方法。如果前一个哈希码已被另一个哈希码使用，您需要处理计算新哈希码的冲突，这是因为 HashMap 的每个桶最多只能包含 1 个元素。

所以你有一个带有两个参数的哈希函数:

• v，用于计算哈希码的对象的值。
• t，它是 i*f，其中 i，称为 stepsize，是您每次添加的内容哈希函数，如果发生碰撞，f 是到目前为止达到的碰撞次数。

从这里开始你有两个可能的功能:

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

第一个是线性函数，第二个是二次函数(这里是该技术的名称)..你应该知道什么 % n 是，c 和 d 被选择为具有更好哈希函数的常量..

实际上对于线性探测而言:

• 你计算H(x, 0)
• • 如果单元格空闲，则将元素放在那里
• • 如果单元格被占用计算H(x, i)
• • • 如果单元格空闲，则将元素放入新地址
• • • 如果单元格被占用则计算H(x, i+i)
• • • • 继续，直到找到一个空单元格

对于二次探测，您所做的是相同的，您从H(x,0) 开始，然后是H(x,i) 然后是 H(x,i+i)，不同之处在于所涉及的散列函数会给步长赋予不同的权重。