c++ - 我需要一些指导来编写哈希函数来对 ~160,000 个字符串进行排序

Question

我的导师把这个丢给了我们，并告诉我们我们只需要用谷歌搜索如何编写哈希函数。我对此很迷茫。我们为类(class)编写了一个基本的哈希表模板，但我有一个项目需要将大约 160,000 个字符串分类到一个至少有 500 个桶的表中(我想做更多以提高速度)。

我只是不知道去哪里寻找关于此的简明、易于理解的信息。

如有任何帮助，我们将不胜感激。

Answer 1

我建议 universal hash function .这种功能保证了预期中的少量碰撞，即使数据是由对手选择的。有很多通用哈希函数。

如果是字符串，可以采用下面的哈希函数。

对于字符c，我们定义#(c) c 的算术值即(ASCII)。对于字符串 x=c1c1...cn我们定义

如果 HSize 是一个整数并且 k 是一个大质数(您定义它)​​，对于范围 0<a,b<k*HSize让哈希函数为:

此函数提供 [0, HSize-1] 之间的输出

输出值是根据霍纳规则计算的，找到k*HSize的模数每次操作后除法。

因此，创建一个函数 HashFunction 并将要散列的字符串作为参数传递。 这是代码:

#define k 7919 
#define Hsize 1009   
#define a 321
#define b 43112

long long HashFunction(string text)
{
  int i;
  long long  res = 0;
  long long M = (Hsize * k);
  cout<<"M = "<<M<<endl;
  cout<<"Hsize = "<<Hsize<<endl;
  cout<<"k = "<<k<<endl;
  int s=text.size();
  for(i = s-1; i >= 0; i--)
  {
    res = a * (res * 256 + (int)text[i]);
    //cout<<"res before modulo = "<<res<<endl;
    res=res % M;
    //cout<<"res after modulo = "<<res<<endl;
  }
    long long res1 = (res + b) / k;
    return res1;
}