我发现在尝试实现高性能查找时，VS2005上的标准哈希函数非常缓慢。有哪些快速有效的哈希算法可以使大多数冲突无效的良好示例？

解决方案

这始终取决于数据集。

通过使用字符串的CRC32，我有一个令人惊讶的好结果。适用于各种不同的输入集。

在网上很容易找到很多好的CRC32实现。

编辑：几乎忘了：该页面具有很好的哈希函数枪战与性能数字和测试数据：

http://smallcode.weblogs.us/ <-进一步浏览该页面。

Boost有一个boost :: hash库，它可以为大多数常见类型提供一些基本的哈希函数。

根据我的一些旧代码：

/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}

它很快。真的快吓死了。

关于字符串哈希的一种经典建议是，将字母的ascii / unicode值逐个添加到累加器中，每次将累加器乘以质数就可以逐步完成字母。 (允许哈希值溢出)

template <> struct myhash{};

  template <> struct myhash<string>
    {
    size_t operator()(string &to_hash) const
      {
      const char * in = to_hash.c_str();
      size_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash_map<string, int, myhash<string> > my_hash_map;

如果不浪费数据，很难获得比这更快的速度。如果我们知道字符串只能由几个字符而不是全部内容来区分，那么我们可以做得更快。

我们可以尝试通过创建一个新的basic_string子类来更好地缓存哈希值，该子类会记住哈希值，如果该值过于频繁地计算。 hash_map应该在内部进行。

我使用Jenkins哈希编写了Bloom过滤器库，它具有出色的性能。

详细信息和代码可在此处获得：http://burtleburtle.net/bob/c/lookup3.c

这就是Perl用于其哈希操作fwiw的方式。

如果我们要对一组固定的单词进行哈希处理，则最佳哈希函数通常是理想的哈希函数。但是，它们通常要求在编译时知道要散列的一组单词。在词法分析器中检测关键字(并将关键字翻译为标记)是使用诸如gperf之类的工具生成的完美哈希函数的常见用法。完美的哈希还可以让我们用简单的数组或者"向量"替换" hash_map"。

如果我们不对一组固定的单词进行散列，那么显然这并不适用。

如果字符串平均比单个缓存行长，但是它们的长度+前缀是相当唯一的，请考虑仅使用长度+前8/16个字符。 (长度包含在std :: string对象本身中，因此读取起来很便宜)

我与Microsoft Research的Paul Larson合作处理了一些哈希表实现。他研究了各种数据集上的许多字符串哈希函数，发现简单的乘以101和加循环的效果出奇地好。

unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned int hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}