什么是好的哈希函数?我在大学的数据结构课程中看到了很多哈希函数和应用程序,但我主要了解到很难制作一个好的哈希函数。作为避免冲突的经验法则,我的教授说:
function Hash(key)
return key mod PrimeNumber
end(在C和类似语言中,mod是%运算符)
其中质数是哈希表的大小。我知道这是一个比较好的函数来避免冲突,而且速度也很快,但是我怎么才能做得更好呢?对于字符串键和数字键,有没有更好的哈希函数?
发布于 2009-04-14 08:13:55
用于在基本上任何类型的数据上执行“普通”哈希表查找- Paul Hsieh的这个是我使用过的最好的一个。
http://www.azillionmonkeys.com/qed/hash.html
如果您关心密码安全或任何其他更高级的东西,那么YMMV。如果你只是想要一个用于哈希表查找的强大的通用哈希函数,那么这就是你正在寻找的。
发布于 2008-08-29 16:31:54
对于通用散列,没有“好的散列函数”这样的东西。是的,我知道有一种叫做“通用散列”的东西,但这不是我的意思)。根据上下文的不同,不同的标准决定了散列的质量。已经有两个人提到了SHA。这是一个加密的哈希,它对哈希表来说一点也不好,你的意思可能是。
哈希表有非常不同的要求。但是,由于不同的数据类型公开了不同的信息,可以对其进行散列,因此很难找到一个通用的散列函数。作为一条经验法则,最好将一个类型包含的所有信息都考虑在内。这并不总是那么容易,甚至是不可能的。出于统计(因此冲突)的原因,在问题空间上生成良好的扩散也是很重要的,即所有可能的对象。这意味着当对100到1050之间的数字进行散列时,让最重要的数字在散列中扮演重要角色是不好的,因为对于大约90%的对象来说,这个数字将是0。更重要的是让最后三个数字决定哈希值。
同样,在对字符串进行散列时,考虑所有字符也很重要-除非事先知道所有字符串的前三个字符是相同的;考虑这些字符是一种浪费。
这实际上是我建议阅读Knuth在《计算机编程艺术》第三卷中所说的内容的案例之一。另一个很好的读物是Julienne Walker的The Art of Hashing。
发布于 2008-10-25 14:26:08
散列函数有两个主要目的:
如果不知道哈希的用途,推荐它是不可能的。
如果你只是在程序中创建一个哈希表,那么你不需要担心算法的可逆性或可破解性……SHA-1或AES是完全不必要的,你最好使用variation of FNV。与您提到的简单素数模式相比,FNV实现了更好的离散性(因此冲突更少),并且更适合于不同的输入大小。
如果您使用散列来隐藏和验证公共信息(例如散列密码或文档),那么您应该使用经过公众审查的主要散列算法之一。The Hash Function Lounge是一个很好的起点。
https://stackoverflow.com/questions/34595
复制相似问题