根据http://java-bytes.blogspot.com/2009/10/hashcode-of-string-in-java.html：“首先，众所周知的事实是没有完美的散列算法，其中有没有碰撞。”
作者说的是实际而不是理论上的，对吗？因为理论上，这里有一个完美的哈希函数：“对于给定的对象，给它分配一个新的数字”。有无限数量的数字，所以我们总是有一些东西可以分配给一个独特的对象。但在实践中这是不可行的，因为我们的内存量有限。
问问题
790 次
1 回答
11
通常，散列函数从一组对象（宇宙）映射到一组较小的对象（共域）。通常，宇宙是一个无限集，例如所有字符串的集合或所有数字的集合，而余域是一个有限集，例如所有 512 位字符串的集合，或 0 之间的所有数字的集合和一些数字 k 等。在 Java 中，hashCode对象上的函数有一个可以用 表示的值的共同域int，它都是 32 位整数。
我相信作者在说“没有完美的哈希函数”时所谈论的是，不可能将所有字符串的无限集合映射到所有 32 位整数的集合中而不会发生至少一次冲突. 实际上，如果您选择 2 32 + 1 个不同的字符串，则可以保证至少发生一次碰撞。
你的论点 - 我们不能只为每个对象分配一个不同的哈希码吗？- 隐含假设哈希函数的余域是无限的。例如，如果您要尝试使用这种方法为字符串构建散列函数，则散列函数的余域必须至少与所有可能的自然数的集合一样大，因为字符串的数量是无限的。大多数编程语言不支持以这种方式工作的哈希码，尽管理论上这可以工作是正确的。当然，有人可能会反对并说这不算是有效的散列函数，因为散列函数通常具有有限的 codomain。
希望这可以帮助！
于 2013-04-12T19:15:01.593 回答