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

2021-12-27 00:00:00 windows performance hash c++ stl

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

I've found the standard hashing function on VS2005 is painfully slow when trying to achieve high performance look ups. What are some good examples of fast and efficient hashing algorithms that should void most collisions?

推荐答案

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

I worked with Paul Larson of Microsoft Research on some hashtable implementations. He investigated a number of string hashing functions on a variety of datasets and found that a simple multiply by 101 and add loop worked surprisingly well.

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

相关文章