c++ - 在哈希表中查找项目的位置

Question

如您所知，哈希表是一种数据结构。在学习这种数据结构时，我发现很难理解查找给定项目位置的算法。我将其称为 findPos 及其源代码，如下所示:

int findPos(const HashedObject &x) const
{
    int offset = 1;
    int CurrentPos = hashfunction(x);
    while(array[CurrentPos].info != Inactive && array[CurrentPos].element != x)
    {
        CurrentPos += offset;
        offset += 2;
        if(CurrentPos >= array.size())
        {
            CurrentPos -= array.size();
        }
    }
    return CurrentPos;
}

我将解释此源代码中已使用的一些功能。

hashfunction(int x):此函数用于查找关键x的初始位置。如果您知道哈希表，您将理解它。

array这是我用来查找位置的表格。对象array具有2个主要属性:info和element。 array.element包含数组中每个元素的数据。 array.info包含数组元素的状态: Activity (可用)，已删除和不 Activity (免费)(我将enum用于这些状态)

这里的问题是 offset。据我所知，当我想找到给定元素的位置时，我需要根据 x的值在表中进行扫描。但是我不知道为什么他们在这里使用 offset而不是再次使用哈希函数来查找下一个位置。而且，我发现偏移量在循环后增加了2，这让我感到非常困惑。

Answer 1

因此，让我向您解释上面的代码，首先在代码中，它们在“currentpos”中传递了值x，“currentpos”是我们在*中传递的索引。当您询问为什么它们使用offset时因此他们使用“偏移”来增加“当前位置，即偏移是将增加当前位置的值”。

如果上面的语句使您感到困惑，那么就暂时假设它们像在循环中使用了“i”一样，已经将“offset”用作迭代器。

他们在此代码中使用了Linear Probing，并且每次偏移值增加2。

==> 为什么选择“2”？

正如我所说的那样，使用线性探测，但是在线性探测中，偏移量的值在这种情况下根据代码的编写者增加了2，而不是1，因此您已与编写者进行了检查，或者从任何地方获得了此代码。

不过，如果您遇到任何问题，请随时提出。