hash - hadoop 中的 jenkinshash 保证什么？

Question

我知道 jenkinshash 为给定值生成一个整数 (2^32)。此链接中的文档: http://hbase.apache.org/apidocs/org/apache/hadoop/hbase/util/JenkinsHash.html

说返回: 一个 32 位值。键的每一位都会影响返回值的每一位。相差一位或两位的两个 key 将具有完全不同的哈希值。

对于给定的值，jenkinshash 最多可以返回 2^32 个不同的结果。如果我有超过 2^32 个值怎么办？它会为两个不同的值返回相同的结果吗？

谢谢

Answer 1

作为大多数哈希函数，是的，它可能会为不同的输入数据返回重复的哈希值。根据您链接到的文档，保证是一位或两位不同的值是不同的。一旦它们相差 3 位或更多位，您就没有唯一性保证。

哈希函数的输入数据可能比哈希函数的输出更大(具有更多独特的输入值)。这很容易使输出数据中必须存在重复项。考虑一个散列函数，它输出 1-10 范围内的整数，但接受 1-100 范围内的输入:很明显，多个值必须散列为相同的值值，因为您不能仅使用十个不同的整数来枚举值 1-100。这称为 pigeonhole principle .

然而，任何好的散列函数都会尝试平均分配输出值。在 1-10 示例中，您可以期望一个好的散列函数来为 2 提供与 6 大致相同的次数。

保证唯一性的散列函数称为perfect hash functions .它们都提供至少与输入数据基数相同的输出数据。输入整数 1-100 的完美哈希函数必须至少有 100 个不同的输出值。

请注意 according to Wikipedia Jenkins 哈希函数不是加密的。这意味着您应该避免使用它们来确保密码安全等，但您可以使用散列来进行稍微均匀的工作分配和校验和。