典型的哈希函数首先将搜索键转换为称为哈希码的整数值，然后将哈希码压缩为哈希表的索引。 Java 的根类 Object 有 hashCode 方法，该方法返回整数哈希码。默认情况下，该方法返回对象的内存地址。 hashCode方法的通用契约如下：
每当重写 equals 方法时，都应该重写 hashCode 方法，以确保两个相等的对象返回相同的哈希码。在程序执行过程中，多次调用hashCode方法会返回相同的整数，前提是对象的数据没有改变。两个不相等的对象可能有相同的哈希码，但是你应该实现 hashCode 方法来避免太多这样的情况。
基本类型的哈希码
对于byte、short、int和char类型的搜索键，只需将它们转换为int即可。因此，任何一种类型的两个不同搜索键将具有不同的哈希码。
对于 float 类型的搜索键，使用 Float.floatToIntBits(key) 作为哈希码。请注意，floatToIntBits(float f) 返回一个 int 值，其位表示与浮点数 f 的位表示相同。因此，float类型的两个不同搜索键将具有不同的哈希码。
对于 long 类型的搜索键，简单地将其转换为 int 并不是一个好的选择，因为所有仅前 32 位不同的键将具有相同的哈希码。为了考虑前32位，将64位分成两半，并执行异或运算将两半组合起来。这个过程称为折叠。 long 键的哈希码是
int hashCode = (int)(key ^ (key >> 32));
注意>>是右移运算符，将位向右移动32位。例如，1010110 >> 2 产生0010101。 ^ 是按位异或运算符。它对二进制操作数的两个相应位进行操作。例如，1010110 ^ 0110111 产生1100001.
对于 double 类型的搜索键，首先使用 Double.doubleToLongBits 方法将其转换为 long 值，然后执行折叠，如下所示：
长位 = Double.doubleToLongBits(key);
int hashCode = (int)(位 ^ (位 >> 32));
字符串的哈希码
搜索键通常是字符串，因此为字符串设计一个好的哈希函数很重要。一种直观的方法是将所有字符的 Unicode 相加作为字符串的哈希码。如果应用程序中的两个搜索键不包含相同的字母，则此方法可能有效，但如果搜索键包含相同的字母，例如 tod 和 dot.
，则会产生大量冲突
更好的方法是生成考虑字符位置的哈希码。具体来说，令哈希码为
s0*b(n – 1) + s1*b(n – 2) + c + sn-1
其中 si 是s.charAt(i)。该表达式是某个正 b 的多项式，因此称为 多项式哈希码。使用霍纳规则进行多项式计算（请参阅案例研究：将十六进制转换为十进制），可以按如下方式有效计算哈希码：
(…((s0*b + s1)b + s2)b + … + sn-2)b + sn-1
此计算可能会导致长字符串溢出，但算术溢出在 Java 中被忽略。您应该选择适当的值 b 以尽量减少碰撞。实验表明，b 的最佳选择是 31、33、37、39 和 41。在 String 类中，使用多项式哈希代码覆盖 hashCode，其中 b 为 31.
压缩哈希码
键的哈希码可能是一个超出哈希表索引范围的大整数，因此您需要缩小它以适应索引的范围。假设哈希表的索引在0和N-1之间。将整数缩放到 0 和 N-1 之间的最常见方法是使用
h(hashCode) = hashCode % N
怪兽AI数字人
数字人短视频创作，数字人直播，实时驱动数字人
44 查看详情
为了确保索引分布均匀，请选择 N 为大于 2 的质数。
理想情况下，您应该为N选择一个素数。然而，找到一个大的素数是很耗时的。在 java.util.HashMap 的 Java API 实现中，N 设置为 2 次方的值。这种选择是有充分理由的。当N是2的幂的值时，
h(hashCode) = hashCode % N
与
相同
h(hashCode) = hashCode & (N – 1)
与符号&是按位AND运算符。如果两个相应位都是 1，则两个相应位的 AND 会产生 1。例如，假设N = 4且hashCode = 11，11 % 4 = 3，这与01011 & 00011 = 11相同。 & 运算符的执行速度比 % 运算符快得多。
为了确保散列分布均匀，在java.util.HashMap的实现中，还使用了补充散列函数和主散列函数。该函数定义为：
private static int SupplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
返回 h ^ (h >>> 7) ^ (h >>> 4);
}
^ 和 >>> 是按位异或和无符号右移运算。位运算比乘法、除法和求余运算快得多。您应该尽可能用按位运算替换这些运算。
完整的哈希函数定义为：
h(hashCode) =supplementalHash(hashCode) % N
这与
相同
h(hashCode) =supplementalHash(hashCode) & (N – 1)
因为N是2的幂的值。
以上就是哈希函数和哈希码的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/509184.html
微信扫一扫 
支付宝扫一扫 
