当使用hash_map时，在stl字符串上使用的最好的散列算法是什么？ [英] What's the best hashing algorithm to use on a stl string when using hash_map?

问题描述

我发现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研究部分hashtable实现。他调查了各种数据集上的一些字符串哈希函数，发现一个简单的乘以101和add循环的工作出奇的好。

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

这篇关于当使用hash_map时，在stl字符串上使用的最好的散列算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！