44

我不能使用 boost:hash 因为我必须坚持使用 C 并且不能使用 C++。

但是，我需要散列大量（10K 到 100k）令牌字符串（5 到 40 字节长度），以便在这些字符串中搜索最快。

MD5、SHA1 或任何长散列函数对于一个简单的任务来说似乎太重了，我不是在做密码学。另外还有存储和计算成本。

因此我的问题：

  1. 在大多数实际情况下，可以确保防止冲突的最简单的哈希算法可能是什么。

  2. 哈希值使用多少位？我正在开发 32 位系统。Perl/Python 中的哈希算法是否也使用 32 位哈希？还是我必须跳到64？

  3. 关于在通用脚本语言中实现哈希表：实现是否检查冲突或者我可以完全避免那部分？

4

6 回答 6

24

您可以在http://www.azillionmonkeys.com/qed/hash.html

唯一不应该检查冲突的情况是，如果您使用完美的散列 - 一个很好的老式查找表，例如gperf。

于 2009-04-13T14:04:18.937 回答
11

  1. 这是最著名的散列函数的一个很好的概述。

  2. 32位应该可以正常工作。

  3. 你总是需要检查冲突，除非你想写一个有趣的哈希表:)

于 2009-04-13T14:02:43.560 回答
8

用于哈希表查找的通用哈希函数。它指定Do NOT use for cryptographic purpose，但由于您指定您没有这样做的意图，那么您应该没问题。

它包括对哈希函数的调查以尝试

于 2009-04-13T14:00:34.563 回答
5

如果您使用的是类似 posix 的系统并坚持使用纯 C，我会简单地使用系统已经提供的功能。man 3 hcreate 为您提供所有详细信息，或者您可以在此处找到在线版本http://linux.die.net/man/3/hcreate

于 2009-04-13T16:05:02.300 回答
2

尝试Adler32用于长字符串或Murmur2用于短字符串。

于 2009-04-13T14:12:22.180 回答
1

xxhash是一个非常快速和简单的选择。一个简单的代码将使用XXH32函数：

unsigned int XXH32 (const void* input, int len, unsigned int seed);

它是 32 位哈希。由于lenis int，对于大于2^31-1字节的更大数据，请使用以下内容：

void*         XXH32_init   (unsigned int seed);
XXH_errorcode XXH32_update (void* state, const void* input, int len);
unsigned int  XXH32_digest (void* state);
于 2013-10-22T08:48:16.360 回答