哈希函数和哈希码

典型的哈希函数首先将搜索键转换为称为哈希码的整数值，然后将哈希码压缩为哈希表的索引。 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位分成两半，并执行异或运算将两半组合起来。这个过程称为折叠。 长键的哈希码是

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 幂的值。

以上是哈希函数和哈希码的详细内容。更多信息请关注PHP中文网其他相关文章！