1

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

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  ********
    }
}

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

任何帮助将不胜感激。

4

1 回答 1

3

首先，我们谈论的是开放寻址（或封闭散列）方法。如果前一个哈希码已被另一个哈希码使用，您需要处理计算新哈希码的冲突，这是因为哈希映射的每个桶最多可以包含 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)，不同的是所涉及的散列函数，它将赋予步长不同的权重。

于 2010-04-10T12:46:32.187 回答