如何在 C++ 中实现线性探测？

Question

我是 Hash Maps 的新手，明天要交作业。我实施了一切，一切都很好，除了我发生碰撞的时候。我不太理解线性探测的想法，我确实尝试根据我的理解来实现它，但是由于某种原因，程序在 table 大小 < 157 时停止工作。

void hashEntry(string key, string value, entry HashTable[], int p) 
    {
        key_de = key;
        val_en = value;
       for (int i = 0; i < sizeof(HashTable); i++)
        {
        HashTable[Hash(key, p) + i].key_de = value;
        }
    }

我认为通过每次向哈希函数添加一个数字，2 个桶将永远不会获得相同的哈希索引。但这没有用。

Answer 1

具有线性探测的哈希 table 需要您

从散列到的位置开始进行线性搜索，寻找用于存储您的键+值的空槽。
如果遇到的slot是空的，存储你的key+value；你完成了。
否则，如果它们的键匹配，则替换值；你完成了。
否则，移动到下一个插槽，寻找任何空的或键匹配的插槽，此时 (2) 或 (3) 出现。
为了防止超过运行，执行所有这些操作的循环以 table 大小为模进行换行。
如果您运行一直回到原始散列位置并且仍然没有空槽或匹配键覆盖，则您的 table 已完全填充（100% 负载）并且您不能插入更多键值对。

就是这样。实际上它看起来像这样：

bool hashEntry(string key, string value, entry HashTable[], int p)
{
    bool inserted = false;
    int hval = Hash(key, p);

    for (int i = 0; !inserted && i < p; i++)
    {
        if (HashTable[(hval + i) % p].key_de.empty())
        {
            HashTable[(hval + i) % p].key_de = key;
        }

        if (HashTable[(hval + i) % p].key_de == key)
        {
            HashTable[(hval + i) % p].val_en = value;
            inserted = true;
        }
    }

    return inserted;
}

请注意，在线性探测哈希算法中扩展 table 是乏味的。我怀疑这将在您的学习中出现。最终你需要跟踪有多少插槽被占用，所以当 table 超过指定的负载因子（比如 80%）时，你扩展 table，重新散列新 p 上的所有条目大小，这将改变他们最终居住的地方。

无论如何，希望它有意义。

如何在 C++ 中实现线性探测？

How do I implement linear probing in C++?

c++

collision

probing