Huk*_*ABA 0 math hash perfect-hash
根据http://java-bytes.blogspot.com/2009/10/hashcode-of-string-in-java.html:"首先,它是一个众所周知的事实,即没有完美的哈希算法,没有碰撞."
作者实际上是在谈论而不是在理论上对吗？因为从理论上讲,这里是一个完美的哈希函数:"对于给定的对象,给它分配一个新的数字".有无数的数字,所以我们总会有东西分配给一个独特的对象.实际上,这是不可行的,因为我们的内存量有限.
通常,散列函数从一组对象(宇宙)映射到较小的一组对象(codomain).通常,Universe是一个无限集,例如所有字符串的集合或所有数字的集合,并且codomain是有限集合,例如所有512位字符串的集合,或0之间的所有数字的集合在Java中,hashCode对象上的函数具有可以用a表示的值的codomain int,它是所有32位整数.
我相信作者在说"没有完美的哈希函数"时所说的是没有可能的方法将所有字符串的无限集合映射到所有32位整数的集合而不至少有一次冲突.实际上,如果您选择2 个32 + 1个不同的字符串,则保证至少有一个碰撞.
你的论点 - 我们不能只为每个对象分配一个不同的哈希码吗？ - 隐含假设哈希函数的codomain是无限的.例如,如果您尝试使用此方法为字符串构建哈希函数,则哈希函数的codomain必须是所有可能自然数的集合,因为存在无限多个字符串.大多数编程语言不支持以这种方式工作的哈希码,尽管你是正确的,理论上这可行.当然,有人可能反对并说这不算作有效的散列函数,因为通常散列函数具有有限的codocins.
希望这可以帮助!