具有两个int属性的自定义类的hashCode是什么？

Question

在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中的键HashMap和作为元素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可能太长,让他们一起将不会被转换.

Answer 1

你不能改变你的类型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)的哈希码中,int本身对于int值,某种散列的从64位至32 long等.

编辑:我不记得为什么31和17一起工作的细节.它们都是素数的事实可能是有用的 - 但是从我记忆中来看,为什么这样的哈希背后的数学通常是合理的(尽管不如预先知道可能值的分布的哈希那样)要么困难,要么不太了解.我知道乘以31便宜(左移5并减去原值)......

Answer 2

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

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

Answer 3

我知道不相等的对象可以使用相同的哈希码.但是,冲突越多,性能就越差(例如,在哈希表中).

据我所知,从最好的映射ž ²→ ž是"优雅的配对功能"(谷歌它).这是实施

// 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,那么这将具有零的哈希冲突.

Answer 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 起可用，还有其他原始类型的版本。

优点：它是干的、流畅的并且完全清楚需要做什么。它不会受到隐式装箱的影响，也不使用隐式可变参数。它相对快速且便宜。通过向数组初始值设定项添加额外的数字可以轻松扩展它。

缺点：它不如复制粘贴方法那么快。如果哈希码被频繁调用，请考虑。

此致。