什么是好的哈希函数？我在大学的数据结构课程中看到了很多哈希函数和应用程序,但我大多认为很难创建一个好的哈希函数.作为避免碰撞的经验法则,我的教授说:
function Hash(key)
return key mod PrimeNumber
end
(mod是C和类似语言中的%运算符)
使用素数作为哈希表的大小.我觉得这是一个很好的功能,以避免碰撞和快速,但我怎么能做一个更好的？字符串键对数字键有更好的散列函数吗？
我有许多不相关的命名事物,我想快速搜索."aardvark"在任何地方始终都是"aardvark",因此对字符串进行散列并重用整数可以很好地加速比较.整个名称集是未知的(并随着时间的推移而变化).什么是快速字符串哈希算法,它将生成小(32或16)位值并具有低冲突率？
我想看一个特定于C/C++的优化实现.
我在我的PHP驱动的站点上有一些代码创建一个随机哈希(使用sha1()),我用它来匹配数据库中的记录.
发生碰撞的几率是多少？我应该生成哈希,然后首先检查它是否在数据库中(我宁愿避免额外的查询)或自动插入它,基于它可能不会与另一个冲突的概率.
假设我有一个哈希算法,它很好而且流畅(任何一个哈希值的出现几率与其他值相同).
现在说我知道挑选2个哈希并且发生碰撞的几率(为了论证)50000:1.
现在说我挑了100个哈希.考虑到一组2中碰撞的几率,如何计算100个值内的碰撞几率？
对此有什么一般解决方案,以便我可以提出一些哈希尝试,之后赔率低于某个可接受的阈值？例如,我可以说"一批49999哈希值创建具有很高的碰撞机会".