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

Question

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

Answer 1

我与微软研究院的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;
}

Answer 2

从我的一些旧代码:

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

它很快.真的吓坏了.

Answer 3

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

Answer 4

这总取决于您的数据集.

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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