39

在 Java 中，我有一个类，它表示具有 int 坐标的点

public class Point {
    int x = -1;
    int y = -1;

    public Point (int xNew, int yNew) {
        x = xNew; y = yNew;
    }

    public boolean equals (Object o) {
        // no need for (o instanceof Point) by design
        return x == ((Point)o).x && y == ((Point)o).y;
    }
}

我使用类的对象Point作为 a 中的键和 aHashMap中的元素HashSet。

该功能的最佳候选者是hashCode什么？我会把它加倍，这样左边的部分是 x，右边的部分是 y，例如： x = 4, y = 12，然后hashCode返回4.12。但是通过实现，它不能是double，只能是int。

这不是一个选项：

public int hashCode() {
    // no need to check for exception parseInt since x and y are valid by design
    return Integer.parseInt(Integer.toString(x) + Integer.toString(y));
}

因为值x和y可以太长，这样它们就不会一起被转换。

4

8 回答 8

57

您不能更改 的类型hashCode，也不应该更改。

我会选择类似的东西：

public int hashCode() {
    return x * 31 + y;
}

请注意，这意味着在大多数情况下，(a, b) 与 (b, a) 不同（与例如加法或异或运算不同）。如果您经常在现实生活中使用“切换”值的键，这将很有用。

它不是唯一的 - 但哈希码不必是唯一的。对于相等的值（为了正确性），它们只需要相同，并且（为了效率）“通常”对于不相等的值是不同的，并且分布合理。

一般来说，我通常遵循 Josh Bloch 在 Effective Java 中建议的相同模式：

public int hashCode() {
    int hash = 17;
    hash = hash * 31 + field1Hash;
    hash = hash * 31 + field2Hash;
    hash = hash * 31 + field3Hash;
    hash = hash * 31 + field4Hash;
    ...
    return hash;
}

field1Hash引用类型字段的哈希码（或空引用的 0），intint 值的哈希码，从 64 位到 32 位的某种哈希码long等在哪里。

编辑：我不记得为什么 31 和 17 可以很好地协同工作的细节。它们都是素数这一事实可能很有用 - 但据我记得，为什么像这样的散列通常是合理的（尽管不如预先知道可能值分布的散列好）的数学要么困难要么不是很好理解。我知道乘以 31 很便宜（左移 5 并减去原始值）...

于 2012-07-31T14:39:49.003 回答
12

我知道不相等的对象具有相同的哈希码是可以的。但是，冲突越多，性能就越差（例如，在哈希表中）。

据我所知，Z ² → Z的最佳映射是“优雅的配对函数”（google it）。这是实现

// x,y must be non-negative
int elegant(int x, int y) {
    return x < y ? y * y + x : x * x + x + y;
}


// returns a unique number for every x,y pair
int elegantSigned(int x, int y) {
    if (x < 0) {
        if (y < 0)
            return 3 + 4 * elegant(-x - 1, -y - 1);
        return 2 + 4 * elegant(-x - 1, y);
    }
    if (y < 0)
        return 1 + 4 * elegant(x, -y - 1);
    return 4 * elegant(x, y);
}

一旦乘法溢出，这将开始重叠。如果 x 和 y 的绝对值小于大约 46000，那么这将有零散列冲突。

于 2016-01-14T21:07:52.573 回答
10

只需使用java.util.Objects.hash(Object... values)。

public int hashCode() {
    return Objects.hash(field1,field2);
}

Objects.hash 实际上调用Arrays.hashCode(Object a[])

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}
于 2016-07-17T02:14:05.980 回答
4

这个问题已经很老了，但我认为只要 java 存在，这个想法就会成为现实。让我们分析上面的方法：

  1. Objects.hash(...)流利且清楚需要做什么，但它使用可变参数（隐式创建数组），此外，它隐式地装箱每一个原语，被传递到方法中。
  2. x * 31 + y高效：没有装箱，没有使用显式或隐式数组创建操作。但是，目前还不清楚需要做什么。为什么是 31，而不是42？对于那些熟悉散列如何工作的人来说，理解这样的代码没有困难，但其他人呢？第二个陷阱是难以扩展：例如，如果你想去 3D 并添加z坐标，你很容易忘记在散列代码中添加新值，因为它迫使你复制粘贴几乎相同的代码很多次。

我可以介绍第三种方法，上面的答案中没有提到：

@Override
public final int hashCode()
{
    final int[] numbers = {x, y};
    return Arrays.hashCode(numbers);
}

它使用一个临时数组来保存被散列的整数，并调用Arrays.hashCode()，它从 Java 1.5 开始可用，还有其他原始类型的版本。

优点：它是干的，流利的，完全清楚需要做什么。它不受隐式装箱的影响，也不使用隐式可变参数。它相对快速且便宜。它可以通过在数组初始化器中添加额外的数字来轻松扩展。

缺点：它不如复制粘贴方法快。如果经常调用哈希码，请考虑它。

此致。

于 2018-08-15T14:09:47.193 回答
3

通常值得考虑Apache Commons HashCodeBuilder

此类可以为任何类构建良好的 hashCode 方法。它遵循 Joshua Bloch 的《Effective Java》一书中规定的规则。编写一个好的 hashCode 方法实际上是相当困难的。此类旨在简化流程

我肯定会推荐看参考书Effective Java。

于 2012-07-31T14:42:17.217 回答
2

有一种生成哈希码操作的通用策略。在您的情况下，这将是：

public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + x;
    result = prime * result + y;
    return result;

}

于 2012-07-31T14:40:52.687 回答
1

您可能想看看Google Guava 的 Objects.hashCode(Object...)方法。

public int hashCode() {
  return Objects.hashCode(x, y);
}
于 2012-07-31T14:47:12.813 回答
-1

尝试添加他们的哈希码。?

return new Integer(x).hashCode()+new Integer(y).hashCode();

于 2012-07-31T14:38:58.823 回答