当使用hash_map时，在stlstring上使用什么最好的散列algorithm？
我发现VS2005上的标准哈希函数在尝试实现高性能查找时非常缓慢。 快速有效的散列algorithm有哪些好的例子可以消除大多数的冲突？
我和微软研究院的保罗·拉森 （ Paul Larson ）一起研究了一些散列表实现。 他调查了各种数据集上的一些string散列函数，发现一个简单的乘以101和加法循环的工作效果非常好。
unsigned int hash( const char* s, unsigned int seed = 0) { unsigned int hash = seed; while (*s) { hash = hash * 101 + *s++; } return 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; }
它很快。 真的吓坏了
Boost有一个boost :: hash库，可以为大多数常见的types提供一些基本的散列函数。
这总是取决于你的数据集。
我一个人使用string的CRC32有惊人的好结果。 适用于各种不同的input设置。
在网上很容易find很多好的CRC32实现。
编辑：几乎忘了：这个页面有一个很好的散列函数枪战与性能数字和testing数据：
http://smallcode.weblogs.us/ < – 进一步在页面下方。
我使用Jenkins哈希来编写一个Bloom滤镜库，它有很好的性能。
详细信息和代码可在这里find： http : //burtleburtle.net/bob/c/lookup3.c
这就是Perl用于哈希操作的原因。
如果你正在散列一组固定的单词，最好的散列函数通常是一个完美的散列函数 。 但是，他们通常要求在编译时已经知道你想要散列的一组字。 在词法分析器中检测关键字（以及将关键字转换为令牌）是使用gperf等工具生成的完美哈希函数的常见用法。 一个完美的哈希也可以让你用一个简单的数组或vectorreplacehash_map 。
如果你没有散列一组固定的单词，那么显然这不适用。
对string散列的一个经典build议是逐个将字母/统一码值加到累加器中，每次将累加器乘以一个素数。 （允许在散列值上溢出）
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;
没有丢出数据就很难做到这一点。 如果你知道你的string可以通过几个字符来区分，而不是整个内容，你可以做得更快。
如果值过于频繁计算，您可以尝试创build一个basic_string的新子类来更好地caching散列值。 虽然hash_map应该在内部做。
我做了一些search和有趣的事情，Paul Larson的小algorithm在这里出现在http://www.strchr.com/hash_functions中，因为在许多条件下所有testing的碰撞最less，而且它的速度非常快展开或桌子驱动。;
拉尔森是简单的乘以101和上面的循环。
Python 3.4包含一个基于SipHash的新的哈希algorithm。 PEP 456是非常丰富的。
如果你的string的平均长度比单个caching行长，但是它们的长度+前缀是合理唯一的，那么可以考虑长度+前8/16个字符。 （长度包含在std :: string对象本身中，因此便于阅读）
从哈希函数一路下来 ：
至less在游戏开发者圈子中， MurmurHash作为一个“一般散列函数”非常stream行。
这是一个很好的select，但是如果我们总体上可以做得更好，我们再来看看。 另一个很好的select，特别是如果你知道更多有关你的数据而不是“未知的字节数”的话，就是自己推出（例如参见Won Chun的回复，或者Rune修改过的专门用于4字节密钥的xxHash / Murmur等等。）。 如果你知道你的数据，总是试着看看这些知识是否可以用于良好的效果！
没有更多的信息，我会推荐MurmurHash作为通用的非密码散列函数 。 对于小string（在程序中的平均标识符的大小）非常简单和着名的djb2和FNV是非常好的。
在这里（数据大小<10字节），我们可以看到，其他algorithm的ILP智能性并没有得到显示，而FNV或djb2的超简单性在性能上也是胜利的。
djb2
unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; }
FNV-1
hash = FNV_offset_basis for each byte_of_data to be hashed hash = hash × FNV_prime hash = hash XOR byte_of_data return hash
FNV-1A
hash = FNV_offset_basis for each byte_of_data to be hashed hash = hash XOR byte_of_data hash = hash × FNV_prime return hash
关于安全性和可用性的说明
哈希函数可能使您的代码容易受到拒绝服务攻击。 如果攻击者能够强制你的服务器处理太多的冲突，你的服务器可能无法应付请求。
像MurmurHash这样的哈希函数接受一个种子，你可以提供这个种子来大幅降低攻击者预测你的服务器软件产生的哈希值的能力。 记住这一点。
