0

我是 Hash Maps 的新手，明天有一个作业要交。我实现了一切，一切都很好，除了当我遇到碰撞时。我不太理解线性探测的想法，我确实尝试根据我的理解来实现它，但是由于某种原因，程序停止了表大小 < 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 个桶永远不会得到相同的哈希索引。但这没有用。

4

1 回答 1

1

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

  1. 从散列到位置开始线性搜索，以找到一个用于存储键+值的空槽。
  2. 如果遇到的槽是空的，存储你的key+value；你完成了。
  3. 否则，如果它们的键匹配，则替换值；你完成了。
  4. 否则，移动到下一个插槽，寻找任何空的或键匹配的插槽，此时 (2) 或 (3) 会发生。
  5. 为了防止溢出，执行所有这些操作的循环都以表格大小为模。
  6. 如果您一直运行回到原始哈希位置并且仍然没有空槽或匹配键覆盖，则您的表已完全填充（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;
}

请注意，在线性探测哈希算法中扩展表是乏味的。我怀疑这将在你的研究中出现。最终，您需要跟踪占用了多少槽，因此当表超过指定的负载因子（例如，80%）时，您扩展表，重新散列新p大小的所有条目，这将改变它们最终所在的位置。

无论如何，希望这是有道理的。

于 2019-12-15T13:03:08.240 回答