c++ - C++ 中带 vector 的简单 HashMap

Question

我在第一学期的学习中，作为我的一部分。科学作业 我必须使用 vector 实现一个简单的 HashMap ，但我在理解这个概念时遇到了一些问题。

首先我必须实现一个散列函数。为了避免冲突，我认为最好使用双重散列，如下所示:

do {
    h = (k % m + j*(1+(k % (m-2)));
    j++;
} while ( j % m != 0 );

其中 h 是要返回的哈希，k 是键，m 是 hash_map 的大小(和一个质数；它们都是 int 类型)。

这很简单，但是我需要能够在映射中插入或删除一对键和相应的值。

这两个函数的签名应该是 bool，所以我必须返回 true 或 flase，我猜我应该在 vector 中位置 h 没有元素时返回 true。 (但我不知道为什么 remove 也应该是 bool)。

我的问题是当插入函数返回 false 时该怎么办(即当位置 h 上已经保存了一个键值对时 - 我将其实现为名为 find 的函数)。我显然可以通过简单地增加 j 将它移动到下一个空闲位置，但是我的哈希函数计算的哈希不会再告诉我们某个 key 保存在哪个位置，导致删除函数的错误行为。

网上有没有很好的例子，不使用预定义的 STD 方法？ (我的谷歌在过去几天表现得很奇怪，只用本地语言给我返回无用的点击)

Answer 1

我被告知要将我的评论移至答案，所以就在这里。我假设您的 get 方法采用您正在寻找参数的值。

所以我们要做的是一个称为线性探测的过程。

当我们插入值时，我们会像往常一样对其进行哈希处理，假设我们的哈希值为 4

[x,x,x,,,x,x]

如我们所见，我们可以简单地将它插入:

[x,x,x,x,,x,x]

然而，如果在插入时 4 被占用，我们将简单地移动到下一个空槽

[x,x,x,**x**,x,,x,x]

在线性探测中，如果我们到达终点，我们将循环回到起点，直到找到一个插槽。你不应该用完空间，因为你正在使用一个 vector ，它可以在它开始接近满容量时分配额外的空间

这会在您搜索时引起问题，因为 4 处的值可能不再是 4(在本例中为 5)。为了解决这个问题，我们做了一些修改。请注意，只要负载平衡低于 1，插入和检索的运行时间复杂度仍然为 O(1)。

在我们的 get 方法中，我们不是返回数组中 4 处的值，而是开始寻找 4 处的值，如果它在那里我们可以返回它。如果不是，我们查看 5 处的值，依此类推，直到找到该值。

在伪代码中新的东西看起来像这样

bool insert(value){
   h = hash(value);
   while(node[h] != null){
      h++;

      if( h = node.length){
          h = 0;
       }
   }
   node[h] = value;

  return true;
}

得到

get(value){
    h = hash(value);
    roundTrip = 0; //used to see if we keep going round the hashmap

   while(true){

      if(node[h] == value)
          return node[h];

      h++;

      if( h = node.length){
          h = 0;
          roundTrip++;
       }

       if(roundTrip > 1){ //we can't find it after going round list once
          return -1;
       }
   }
}