C的最小哈希函数？

Question

我不能使用boost:hash因为我必须坚持使用C而不能使用C++.

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

MD5,SHA1或任何长哈希函数对于一个简单的任务来说似乎太重了,我没有做加密.此外还有存储和计算成本.

因此我的问题是:

1. 什么是最简单的哈希算法,可以确保在大多数实际情况下防止碰撞.

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

3. 关于常见脚本语言中哈希表的实现:实现是否检查冲突,还是可以完全避免该部分？

Answer 1

你可以找到一个好的(和快速的)哈希函数,以及一个有趣的读取 http://www.azillionmonkeys.com/qed/hash.html

唯一一次你不应该检查碰撞,如果你使用一个完美的哈希 - 一个很好的旧式查找表,如gperf.

Answer 2

1. 以下是最着名的已知哈希函数的概述.

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

3. 你总是需要检查碰撞,除非你想写一个有趣的哈希表:)

Answer 3

哈希表查找的一般哈希函数.它指定不要用于加密目的,但既然你指定你没有意图,那么你应该没问题.

这是包括散列函数的调查尝试

Answer 4

如果你使用类似posix的系统并且坚持使用普通的C语言,我只会使用系统已经提供的功能.man 3 hcreate为您提供所有详细信息,或者您可以在这里找到在线版本http://linux.die.net/man/3/hcreate