代码之家 › 专栏 › 技术社区 › CDR

C的最小哈希函数?

hashtable hash c

CDR · 技术社区 · 17 年前

我不能使用Boox:Hash,因为我必须坚持C,不能使用C++。

但是,我需要散列大量(10000到100K)的令牌字符串(5到40字节长度),以便在这些字符串中搜索最快。

对于一个简单的任务来说,MD5、SHA1或任何长哈希函数都显得太重,我不做加密。另外还有存储和计算成本。

因此,我的问题是:

在大多数实际情况下,最简单的哈希算法可以确保防止碰撞。
哈希值要使用多少位?我正在为32位系统开发。Perl/python中的哈希算法也使用32位哈希吗?或者我必须跳到64?
关于使用通用脚本语言实现哈希表:实现是检查冲突还是可以完全避免该部分?

6 回复 | 直到 10 年前

gnud 17 年前

您可以在以下位置找到一个好的(和快速的)哈希函数和一个有趣的阅读: http://www.azillionmonkeys.com/qed/hash.html

唯一不应该检查冲突的时候,是如果使用一个完美的哈希——一个老式的查找表,比如 gperf .

Sean Allred 11 年前

Here 是已知最著名的哈希函数的一个很好的概述。
32位可以正常工作。
你总是需要检查冲突,除非你想写一个有趣的哈希表:)

TStamper 17 年前

的常规哈希函数 hash table lookup . 它规定 不用于加密目的 但是,既然您指定了不打算这样做,那么您应该是正常的。

它包括 散列函数概述 试一试

amo-ej1 17 年前

如果您使用的是类似于POSIX的系统,并且坚持使用普通的C语言,那么我只需使用系统已经提供的功能即可。man 3 hcreate向您提供所有详细信息,或者您可以在此处找到在线版本 http://linux.die.net/man/3/hcreate

Dru G 17 年前

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

Majid Azimi 13 年前

xxhash 是相当快速和容易的选择。一个简单的代码将使用 XXH32 功能:

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

它是32位哈希。自从 len 是 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);