我发现在尝试实现高性能查找时，VS2005上的标准哈希函数非常缓慢。 有哪些快速有效的哈希算法可以使大多数冲突无效的良好示例？
我与Microsoft Research的Paul Larson合作处理了一些哈希表实现。他研究了各种数据集上的许多字符串哈希函数，发现简单的乘以101和加循环的效果非常好。
1
2
3
4
5
6
7
8
9
10
11
12
| unsigned int
hash(
const char* s,
unsigned int seed = 0)
{
unsigned int hash = seed;
while (*s)
{
hash = hash * 101 + *s++;
}
return hash;
} |
根据我的一些旧代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| /* 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库，它可以为大多数常见类型提供一些基本的哈希函数。
这始终取决于您的数据集。
通过使用字符串的CRC32，我获得了令人惊讶的好结果。适用于各种不同的输入集。
在网上很容易找到很多好的CRC32实现。
编辑：几乎忘了：此页面具有性能数字和测试数据的不错的散列函数枪战：
http://smallcode.weblogs.us/ <-在页面下方。
如果您要对一组固定的单词进行哈希处理，则最佳哈希函数通常是理想的哈希函数。但是，它们通常要求在编译时知道您要哈希的一组单词。在词法分析器中检测关键字(以及将关键字转换为标记)是使用诸如gperf之类的工具生成的完美哈希函数的常见用法。完美的哈希还可以让您将hash_map替换为简单数组或vector。
如果您不对一组固定的单词进行散列，那么显然这并不适用。
我使用Jenkins哈希编写了一个Bloom过滤器库，它具有出色的性能。
详细信息和代码可在此处获得：http://burtleburtle.net/bob/c/lookup3.c
这就是Perl用于其哈希操作fwiw的方式。
Python 3.4包含了一个基于SipHash的新哈希算法。 PEP 456非常有用。
我做了一些搜索，有趣的是，Paul Larson的小算法出现在这里
http://www.strchr.com/hash_functions
因为在多种条件下测试的碰撞次数最少，因此对于展开或表驱动的碰撞速度非常快。
Larson是上面的101和乘法。
关于字符串哈希的一种经典建议是，将字母的ascii / unicode值逐个添加到累加器中，每次将累加器与质数相乘，从而逐步处理字母。 (允许哈希值溢出)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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; |
如果不浪费数据，很难获得比这更快的速度。如果您知道字符串只能由几个字符而不是全部内容来区分，那么您可以做得更快。
您可能会尝试通过创建一个新的basic_string子类来更好地缓存哈希值，该子类会记住哈希值，如果该值计算得太频繁的话。 hash_map应该在内部进行。
从哈希函数一直向下：
MurmurHash got quite popular, at least in game developer circles, as a"general hash function".
It’s a fine choice, but let’s see later if we can generally do better. Another fine choice, especially if you know more about your data than"it’s gonna be an unknown number of bytes", is to roll your own (e.g. see Won Chun’s replies, or Rune’s modified xxHash/Murmur that are specialized for 4-byte keys etc.). If you know your data, always try to see whether that knowledge can be used for good effect!
如果没有更多信息，我会推荐MurmurHash作为通用的非加密哈希函数。对于小字符串(程序中平均标识符的大小)，非常简单且著名的djb2和FNV很好。
Here (data sizes < 10 bytes) we can see that the ILP smartness of other algorithms does not get to show itself, and the super-simplicity of FNV or djb2 win in performance.
djb2
1
2
3
4
5
6
7
8
9
10
11
| 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
1
2
3
4
5
| 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
1
2
3
4
5
| 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之类的哈希函数会接受您可以提供的种子，以大大降低攻击者预测服务器软件正在生成的哈希的能力。记住这一点。
如果您的字符串平均比单个缓存行长，但是它们的长度+前缀是相当唯一的，请考虑仅使用长度+前8/16个字符。 (长度包含在std :: string对象本身中，因此读取起来很便宜)
