比较哈希代码实现

Question

我有一个任务是使用定义在java中实现字符串的哈希代码。我写了这段代码。

public int hash(String str) {
int hashValue = 0;
int power;
for (int i = 0; i < str.length(); i++) {
power = (str.length() -1 - i);
hashValue = hashValue + str.charAt(i) * (int) Math.pow(31, power);
}
return hashValue;
}

我发现我的方法中的结果与 hashcode(( 相同，仅适用于长度小于 8 的字符串。应该是这样还是我的方法不准确？我已经看到，对于超过 8 个字符的字符串，哈希代码可能已更改。

Answer 1

看看 jdk 中的哈希代码实现：

public static int hashCode(byte[] value) {
int h = 0;
int length = value.length >> 1;
for (int i = 0; i < length; i++) {
h = 31 * h + getChar(value, i);
}
return h;
}

可能会发生您的方法产生与此方法相同的结果的情况。其实没关系。它只是一种哈希方法。
请注意，散列方法不需要"准确"。 这是一种将任意对象(字符串(简化为 int 的方法。您可以使用任何您想要的方法。

Answer 2

字符串哈希代码的实现类似于 Java 的String类的hashCode实现，但由于 Java 以微妙的方式缩小了Math.pow返回的double到int，因此并不完全相同。

对于字符串"abcdefg"，长度为 7 个字符，您的方法和 Java 的方法一致 - 它们都返回 -1206291356。 对于字符串"abcdefgh"，长度为8个字符，you方法和Java的方法不一致 - 你的方法返回1858279332，而Java的方法返回1259673732。

首先，让我们介绍一下它们的相似之处。 以下是来自 Grepcode 的 Java 8 代码以供参考：

public int More ...hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

Java 的String实现每次循环发生时都会乘以31倍。 实际上，每个角色都有31的力量。

您的实现尝试通过使用返回double的Math.pow直接确定31乘以字符值的幂。 然后你把它投射回一个int，因为这就是哈希代码的类型。

现在，让我们讨论一下细微的区别。

Java的StringhashCode实现只会乘以和增加int- 即使发生溢出，它也int溢出，在此期间保留了较低的32位信息。

对于您使用Math.pow实现，JLS 第 5.1.3 节涵盖了将double向下转换为int时发生的原始收缩转换。

将

浮点数缩小到整数类型 T 的转换需要两个步骤：

1. 在第一步中，如果 T 长，则浮点数转换为长整型，如果 T 为字节、短整型、字符或整数，则转换为整数，如下所示：

   • 如果浮点数为 NaN (§4.2.3(，则转换的第一步的结果是 int 或长整型 0。

   否则，如果浮点

   • 数不是无穷大，则浮点值将舍入为整数值 V，并使用 IEEE 754 舍入到零模式 (§4.2.3( 向零舍入。然后有两种情况：

一个。如果 T 很长，并且这个整数值可以表示为长整型，那么第一步的结果就是长整型值 V。

b. 否则，如果此整数值可以表示为 int，则第一步的结果是 int 值 V。

• 否则，必须满足以下两种情况之一：

一个。该值必须太小(大量级或负无穷大的负值(，第一步的结果是 int 或 long 类型的最小可表示值。

二.该值必须太大(大量级或正无穷大的正值(，并且第一步的结果是int 或 long 类型的最大可表示值。

(粗体强调我的(

当您有一个 7 个字符的字符串时，您计算 31⁶，即 887,503,681，仍可表示为int。 但是，当您有一个 8 个字符的字符串时，您计算 31⁷，即 27,512,614,111，它太大而无法放入int- int 的最大值约为 20 亿。 缩小转换将其转换为最大整数值，即 2,147,483,647。 此时，您使用的值与 Java 的StringhashCode 方法有效使用的值不同。 真实答案的低 32位不会保留在您的方法中，因为它们在 Java 的StringhashCode方法中。 这是微妙的差异，当您的字符串更长 8 个字符时，它会改变您的值。