Java

Question

所以我刚刚进入 Java 的面向对象编程，我必须制作这个散列字典。我应该用算法和 return 哈希值对名称进行哈希处理。实验室说要做

int n = s.length();
for (int i = 0; i < n; i++)
hash = g * hash + s.charAt(i);

其中 g = 31，s = 名字 + 姓氏；

我查看了这个并将其写入代码。我写的是

public int hashCode()     // part of the Name class
{
    int h = 0;
    String bothNames = first + last;
    for (int i = 0; i < bothNames.length(); i++) {
        h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1);
    }
    return h;
}

现在，当我运行将此代码用于 Name testName = new Name("Wayne", "Gretzky"); 并打印出 testName.hashCode()，我几乎总是得到 32 位整数限制，这意味着它没有溢出。但是，当我将 for 循环更改为

for (int i = 0; i < bothNames.length(); i++) {
    h = g*h + bothNames.charAt(i);
}

一下子又溢出来了。我真的不明白为什么会这样。这两个散列函数应该相同。为什么 h 在第一种情况下不会溢出？提前致谢。

Answer 1

问题是这样的：

h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1)

pow 方法返回一个很大的 double 值。你乘以一个整数给你一个更大的 double 值。然后 h += ... 执行从 double 到 int.

的 原始缩小 转换

double 到 int 的转换是 定义的 将任何大于 Integer.MAX_VALUE 的浮点值转换为 Integer.MAX_VALUE (!).

解决方案是使用整数算法计算 g^k；例如使用循环：

g⁰ = 1

g^k = g * g^{k - 1} (for k > 0).

Answer 2

让我们看看下面一行：

h += bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1);

考虑到 compound assignment operators 的性质，这相当于：

h = (int)(h + (bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1)));

如果不是 Math.pow returns 一个 double 这个事实就好了。考虑常规加宽规则：

h = (int)(intValue + (intValue * doubleValue))
h = (int)(intValue + doubleValue)
h = (int)(doubleValue)

最后一个 doubleValue 缩小为 int。如果字符串足够长，doubleValue 将从第一次迭代开始超过 Integer.MAX_VALUE。

Java - int 不会因散列而溢出

Java - int WON'T overflow with hashing

hash

overflow

hashcode