C++如何在使用哈希函数时计算冲突次数？

Question

我被分配到这个实验室，我需要在其中创建一个哈希函数，并计算在对包含最多 30000 个元素的文件进行哈希处理时发生的冲突次数。到目前为止，这是我的代码

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

long hashcode(string s){
  long seed = 31; 
  long hash = 0;
  for(int i = 0; i < s.length(); i++){
    hash = (hash * seed) + s[i];
  }
  return hash % 10007;
};

int main(int argc, char* argv[]){
  int count = 0;
  int collisions = 0;
  fstream input(argv[1]);
  string x;
  int array[30000];

  //File stream
  while(!input.eof()){
    input>>x;
    array[count] = hashcode(x);
    count++;
    for(int i = 0; i<count; i++){
        if(array[i]==hashcode(x)){
            collisions++;
        }
    }
  }
  cout<<"Total Input is " <<count-1<<endl;
  cout<<"Collision # is "<<collisions<<endl;
}

我只是不确定如何计算碰撞次数。我尝试将每个散列值存储到一个数组，然后搜索该数组，但当只有 10000 个元素时，它导致了 12000 次冲突。任何关于如何计算冲突的建议，或者即使我的哈希函数可以使用改进，都将不胜感激。谢谢。

Answer 1

问题是你在重新计算碰撞(假设你的列表中有 4 个相同的元素，没有其他元素，然后通过你的算法看看你会计算多少次碰撞)

相反，创建一组哈希码，每次计算哈希码时，检查它是否在集合中。如果它在集合中，则增加碰撞总数。如果它不在集合中，则将其添加到集合中。

编辑:

为了快速修补您的算法，我已经完成了以下操作:在循环后递增计数，并在发现冲突后跳出 for 循环。这仍然不是非常高效，因为我们正在遍历所有结果(使用集合数据结构会更快)，但这至少应该是正确的。

还对其进行了调整，因此我们不会一遍又一遍地计算 hashcode(x):

int main(int argc, char* argv[]){
  int count = 0;
  int collisions = 0;
  fstream input(argv[1]);
  string x;
  int array[30000];

  //File stream
  while(!input.eof()){
    input>>x;
    array[count] = hashcode(x);
    for(int i = 0; i<count; i++){
        if(array[i]==array[count]){
            collisions++;
            // Once we've found one collision, we don't want to count all of them.
            break;
        }
    }
    // We don't want to check our hashcode against the value we just added
    // so we should only increment count here.
    count++;
  }
  cout<<"Total Input is " <<count-1<<endl;
  cout<<"Collision # is "<<collisions<<endl;
}