使用hash_map时,在stl字符串上使用的最佳散列算法是什么？

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

1> George V. Re..：

---

我与微软研究院的Paul Larson合作进行了一些散列表实现.他研究了各种数据集上的一些字符串散列函数,发现简单地乘以101和add循环工作得非常好.

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

---

Soumajyoti,溢出无所谓.大多数哈希函数溢出.关键是你可以在低位32位中得到合适的位组合.

2> Dark Shikari..：

---

从我的一些旧代码:

/* 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;
}

它很快.真的吓坏了.

---

它可能很快,但它可能是有史以来发明的最糟糕的散列函数之一.

---

@Matthieu:为什么？很多重复？你有什么参考资料我可以在这里阅读更多信息吗？

3> David Pierre..：

---

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

4> Nils Pipenbr..：

---

这总取决于您的数据集.

我通过使用字符串的CRC32获得了令人惊讶的好结果.适用于各种不同的输入集,效果非常好.

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

编辑:几乎忘了:这个页面有一个很好的哈希函数枪战,包括性能数据和测试数据:

http://smallcode.weblogs.us/ < - 在页面下方.

5> SquareCog..：

---

我使用Jenkins哈希来编写Bloom过滤器库,它具有很好的性能.

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

这就是Perl用于散列操作的原因,fwiw.

6> bk1e..：

---

如果要散列一组固定的单词,最好的散列函数通常是一个完美的散列函数.但是,它们通常要求在编译时知道您尝试散列的单词集.检测词法分析器中的关键词(以及将关键词转换为标记)是使用诸如gperf之类的工具生成的完美哈希函数的常见用法.一个完美的哈希也可以让你替换hash_map一个简单的数组或vector.

如果你没有散列一组固定的单词,那么显然这不适用.