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?
PiNoYBoY82
问问题
51843 次
11 回答
64
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;
}
于 2008-09-20T08:46:37.293 回答
19
From some old code of mine:
/* 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;
}
Its fast. Really freaking fast.
于 2008-09-19T00:01:51.257 回答
8
Boost has an boost::hash library which can provides some basic hash functions for most common types.
于 2008-09-19T00:01:31.757 回答
7
That always depends on your data-set.
I for one had surprisingly good results by using the CRC32 of the string. Works very good with a wide range of different input sets.
Lots of good CRC32 implementations are easy to find on the net.
Edit: Almost forgot: This page has a nice hash-function shootout with performance numbers and test-data:
http://smallcode.weblogs.us/ <-- further down the page.
于 2008-09-18T23:59:19.903 回答
6
我已经使用 Jenkins 哈希编写了一个 Bloom 过滤器库，它具有出色的性能。
详细信息和代码可在此处获得：http: //burtleburtle.net/bob/c/lookup3.c
这就是 Perl 用于其散列操作的方法，fwiw。
于 2008-09-19T00:24:04.167 回答
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 应该在内部执行此操作。
于 2008-09-19T00:18:57.487 回答
2
我做了一些搜索，有趣的是，Paul Larson 的小算法出现在这里 http://www.strchr.com/hash_functions 在许多条件下测试的碰撞最少，而且它的速度非常快展开或表驱动。
拉森是简单的乘以 101 并在上面添加循环。
于 2012-02-20T02:41:45.030 回答
1
从哈希函数一直向下：
MurmurHash作为一种“通用哈希函数”非常流行，至少在游戏开发者圈子里是这样。
这是一个不错的选择，但是让我们稍后看看我们是否可以做得更好。另一个不错的选择，特别是如果您对数据的了解比“它将是未知的字节数”更多，是滚动您自己的（例如，参见 Won Chun 的回复，或 Rune 的修改后的 xxHash/Murmur，它们专门用于 4 字节密钥ETC。）。如果您知道您的数据，请始终尝试查看该知识是否可以用于良好的效果！
如果没有更多信息，我会推荐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;
}
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）接受一个种子，您可以提供该种子以大大降低攻击者预测您的服务器软件正在生成的哈希值的能力。记在脑子里。
于 2016-12-24T15:08:00.470 回答
0
如果您的字符串平均比单个缓存行长，但它们的长度+前缀相当独特，请考虑仅使用长度+前 8/16 个字符。（长度包含在 std::string 对象本身中，因此读起来很便宜）
于 2008-09-19T11:14:21.263 回答