我发现VS2005上的标准哈希函数在尝试实现高性能查找时非常慢。有哪些快速高效的哈希算法可以避免大部分冲突？
使用hash_map时，对于stl字符串，最好使用哪种哈希算法？
49
- PiNoYBoY82
2
24下面提供了一组通用哈希函数，建议您尝试将其应用于数据集中，由于碰撞的原因，某些函数可能比其他函数表现更好。网址为：http://www.partow.net/programming/hashfunctions/index.html。 - Matthieu N.
1可能是字符串的好哈希函数的重复问题。 - M.J. Rayburn
11个回答
66
我和微软研究员Paul Larson一起研究了一些哈希表实现。他在多个数据集上调查了许多字符串哈希函数，发现简单的101乘法加循环效果出奇地好。
unsigned int
hash(
const char* s,
unsigned int seed = 0)
{
unsigned int hash = seed;
while (*s)
{
hash = hash * 101 + *s++;
}
return hash;
}
- George V. Reilly
5
1嘿，乔治。我尝试了我在答案中发布的哈希基准测试代码。不错的发现。它在性能或冲突方面并不出色，但它总是给出一致的结果。看起来它是一个很好且便宜的通用字符串哈希候选者。 - Nils Pipenbrinck
1但是这仅适用于长度较小的字符串。对于大型情况，它大多数时间会溢出。 - Soumajyoti Sarkar
13Soumajyoti，溢出不重要。大多数哈希函数都会有溢出现象。关键是在低32位中获得足够好的位混合。 - George V. Reilly
2这类似于Java实现，但它使用31而不是101。 - Jorge Galvão
我们已经计算出给定字符串所有前缀的哈希值，现在如何找到子字符串的哈希值呢？
例如，考虑
s =“hello”，
s的所有前缀的哈希值为：
[104, 10605, 1071213, 108192621, 2337520240]
如何快速找到子字符串hel的哈希值？ - Chitturi Sai Suman19
来自我之前的一些旧代码：
/* 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;
}
它非常快。真的非常非常快。
- Dark Shikari
5
5可能速度很快，但它可能是有史以来最糟糕的哈希函数之一。 - Matthieu N.
6@Matthieu: 为什么？有很多重复的内容吗？你有什么参考资料可以让我了解更多吗？ - Albert
1@Albert：
^是可传递的，这很糟糕。FNVMultiple不是质数，这很糟糕。InitialFNV也不是质数，这可能好也可能不好，我不确定。 - Mooing Duck@MooingDuck FNVMultiple 似乎是一个质数。 - bysreg
116777619是一个（经过证明的）质数。2166136261是（经过证明的）合数（在2进制下未通过sprp测试）。https://primes.utm.edu/curios/includes/primetest.php - Nick
7
这总是取决于你的数据集。
我本人使用字符串的CRC32得到了出乎意料的好结果。对于各种不同的输入集，它都非常有效。
网上有很多好的CRC32实现可供使用。
编辑：几乎忘记了：这个页面有一个漂亮的哈希函数比赛，附有性能数字和测试数据：
http://smallcode.weblogs.us/<--在页面下方。
- Nils
6
我使用Jenkins哈希算法编写了一个布隆过滤器库，它有很好的性能。详情和代码请参见：http://burtleburtle.net/bob/c/lookup3.c
顺便说一下，这是Perl用于其哈希操作的算法。
- Dmitriy
1
2
对于字符串哈希，一个经典的建议是逐个遍历每个字母，将它们的ASCII/Unicode值加到累加器中，每次将累加器乘以质数。（允许哈希值溢出）
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应该在内部处理这些操作。
- Brian
1
1尤达条件警报！除此之外，这与Larson算法类似（我注意到这是早些时候发布的！）。 - Helge Klein
2
我进行了一些搜索，有趣的是，Paul Larson的小算法在这里http://www.strchr.com/hash_functions显示出在多种条件下具有最少的冲突，并且它非常快速，因为它是展开或表驱动的。Larson的算法就是上面简单的乘以101再加循环。
- Josh S
1
来自哈希函数全解析：
MurmurHash在游戏开发者圈子里相当受欢迎，被称为“通用哈希函数”。
这是一个不错的选择，但让我们看看是否可以找到更好的选择。如果你对数据了解得比“它将是未知数量的字节”更多，那么另一个不错的选择就是自己编写（例如，查看Won Chun的回复或Rune修改的xxHash/Murmur，专门针对4字节密钥等）。如果你了解你的数据，请尝试看看是否可以利用这些知识产生良好的效果！
如果没有更多的信息，我建议使用MurmurHash作为通用的非加密哈希函数。对于小字符串（程序中平均标识符的大小），非常简单而著名的djb2和FNV非常好。
在这里（数据大小小于10字节），我们可以看到其他算法的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;
}
{{link1：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）接受种子，您可以提供该种子以大大降低攻击者预测您的服务器软件生成的哈希值的能力。请记住这一点。
- felipecrv
1
@FelixSFD 我刚刚改进了答案。 - felipecrv
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接