哈希函数和哈希码

今天golang学习网给大家带来了《哈希函数和哈希码》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

典型的哈希函数首先将搜索键转换为称为哈希码的整数值，然后将哈希码压缩为哈希表的索引。 Java 的根类 Object 有 hashCode 方法，该方法返回整数哈希码。默认情况下，该方法返回对象的内存地址。 hashCode方法的通用契约如下：

1. 每当重写 equals 方法时，都应该重写 hashCode 方法，以确保两个相等的对象返回相同的哈希码。
2. 在程序执行过程中，多次调用hashCode方法会返回相同的整数，前提是对象的数据没有改变。
3. 两个不相等的对象可能有相同的哈希码，但是你应该实现 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

为了确保索引分布均匀，请选择 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的幂的值。

到这里，我们也就讲完了《哈希函数和哈希码》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！