Java中一个Point类的hashCode方法

Question

我有一个简单的自定义点类，如下所示，我想知道我的hashCode实现是否可以改进，或者这已经是最好的了。

public class Point 
{
    private final int x, y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public int getX() 
    {
        return x;
    }

    public int getY()
    {
        return y;
    }

    @Override
    public boolean equals(Object other) 
    {
        if (this == other)
          return true;

        if (!(other instanceof Point))
          return false;

        Point otherPoint = (Point) other;
        return otherPoint.x == x && otherPoint.y == y;
    }


    @Override
    public int hashCode()
    {
        return (Integer.toString(x) + "," + Integer.toString(y)).hashCode();
    }

}

- Victor Parmar

---

你是如何尝试改进它的？你想尝试让它更快吗？ - David

你想保证唯一性？速度？ - Adrian

我想要保证两者 :) - Victor Parmar

Answer 1

请不要使用字符串。这背后有很多理论和几种实现方法（除法方法，乘法方法等）。如果你有一个小时的时间，可以观看这个MIT-Class。

话虽如此，Netbeans 7.1建议以下做法：

@Override
public int hashCode() {
    int hash = 7;
    hash = 71 * hash + this.x;
    hash = 71 * hash + this.y;
    return hash;
}

2015年10月更新

我有一段时间开始使用IntelliJ，现在生活更加幸福了。这是它自动生成的hashCode代码。相比之下，这部分代码更加简洁。请注意它也使用了质数。

@Override
public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
}

- Marsellus Wallace

---

有趣的是Netbeans提出了与Eclipse不同的建议，但实现的基础相似且坚实。+1 - nybbler

我很困惑，第二种实现方式怎么算是好的实现方式？ 即使是非常小的数字，例如（0,31），（1,0），您仍然会遇到碰撞。那似乎非常不利，不是吗？ - Christopher Shroba

@ChristopherShroba，你的评论非常有趣，我会在度假回来后研究一下！主要问题是，根据你的示例输入，result被初始化为0。不过，这就是IntelliJ 2016的做法... - Marsellus Wallace

没错，对于任何形如(a, 31b),(b,31a)的点都会发生碰撞。谢谢回复！我很想听听你对此的看法，有机会请告诉我！ - Christopher Shroba

@ChristopherShroba 如Java 文档中所述，hashcode的一般契约为1。如果两个对象根据equals(Object)方法是相等的，则在这两个对象上调用hashCode方法必须产生相同的整数结果。 2. 如果两个对象根据equals(java.lang.Object)方法不相等，则在这两个对象上调用hashCode方法不要求产生不同的整数结果。 - MaxZoom

Answer 2

根据Gevorg的建议，手动将所有重要成员字段的值相乘可能是最有效的，并且具有良好的价值分布。但是，如果您更喜欢可读性，则在Java 7中有很好的替代方案...

import java.util.Objects;

...

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

...或在Guava库中：

import com.google.common.base.Objects;

....

@Override
public int hashCode() {
    return Objects.hashCode(x, y);
}

这两个可变参数方法只是简单地委托给Arrays.hashCode(Object[] a)，因此由于将int自动装箱和创建对象引用数组而导致的性能影响应该比使用反射小得多，但仍会略微影响性能。

阅读起来非常方便，因为您可以轻松看到用于哈希码计算的字段，所有乘法和加法语法都隐藏在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;
}

- Natix

---

仍然容易受到任何形式为(x, 31y), (y, 31x)的一对数的影响，例如(0, 31)，(1, 0)或(3, 217)，(7, 93)。我想在这里引发一个广泛的问题讨论。是否有一种更强大的实现方式或者只用2个整数就可以处理这种问题（这取决于哈希码生成中使用的质数）？ - Marsellus Wallace

Answer 3

我建议您使用一种更简单且性能更高的方法，不需要字符串，也许可以使用Josh Bloch在这个答案中提到的方法，对于您的情况只需：

return 37 * x + y;

编辑：nybbler是正确的。实际上推荐的做法是：

int result = 373; // Constant can vary, but should be prime
result = 37 * result + x;
result = 37 * result + y;

- Matthew Flaschen

---

这并不完全是你链接答案中推荐的。你忽略了应该对每个字段单独进行操作，而不是同时进行。该算法生成[0,37]和[1,0]的相同结果。 - nybbler

请注意，新的实现仍会为形如（x，37y），（y，37x）的任何一对点生成碰撞。 - Marsellus Wallace

Answer 4

使用数字螺旋将二维点哈希为单个整数是一种非常好的方法！

http://ulamspiral.com/images/IntegerSpiral.gif

@Override
public int hashCode() {
    int ax = Math.abs(x);
    int ay = Math.abs(y);
    if (ax>ay && x>0) return 4*x*x-3*x+y+1;
    if (ax>ay && x<=0) return 4*x*x-x-y+1;
    if (ax<=ay && y>0) return 4*y*y-y-x+1;
    return 4*y*y-3*y+x+1;
}

虽然这种方法需要进行更多的计算，但不会发生不可预测的碰撞。它还具有一个好处，一般来说，离原点更近的点将具有较小的哈希值。（但是如果 x 或 y > sqrt(MAX_VALUE)，仍可能会溢出）

- Peter Whidden

Answer 5

我曾经自己编写哈希和相等函数，然后我发现了这个：）

import org.apache.commons.lang.builder.HashCodeBuilder;
import org.apache.commons.lang.builder.EqualsBuilder;

@Override
public boolean equals(Object obj) {
   return EqualsBuilder.reflectionEquals(this, obj);
 }
@Override
public int hashCode() {
   return HashCodeBuilder.reflectionHashCode(this);
 }

当然要记住以下内容：

由于反射涉及到动态解析的类型，某些Java虚拟机优化无法进行。 因此，在性能敏感的应用程序频繁调用的代码段中，应该避免使用反射操作， 因为它们的性能比非反射操作慢。 SRC

- Shawn

---

由于只有两个字段，您也可以使用此库，但要明确列出这些字段。 - Matthew Flaschen

如果这个类在集合中被大量使用，反射哈希码将会对性能造成很大的影响。 - user949300

我建议使用HashCodeBuilder.append方法。 - Matthew Flaschen

Answer 6

从JDK的Point类（继承自Point2d）：

public int hashCode() {
    long bits = java.lang.Double.doubleToLongBits(getX());
    bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
    return (((int) bits) ^ ((int) (bits >> 32)));
}

这看起来比你的实现略微好一些。

- Michael

Answer 7

您可以查看现有的Point类型类实现：

/**
343      * Returns the hashcode for this <code>Point2D</code>.
344      * @return a hash code for this <code>Point2D</code>.
345      */
346     public int hashCode() {
347     long bits = java.lang.Double.doubleToLongBits(getX());
348     bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
349     return (((int) bits) ^ ((int) (bits >> 32)));
350     }

来源：http://kickjava.com/src/java/awt/geom/Point2D.java.htm#ixzz1lMCZCCZw

可以在这里找到hashCode实现的简单指南。

- Kris

---

提醒所有使用此功能进行身份识别的人注意。哈希碰撞是现实存在的...例如：pastebin.com/6wM3W3Wv - vincent

Answer 8

默认情况下，Eclipse将使用类似于以下代码的hashCode()函数来处理您的Point类：

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + getOuterType().hashCode();
    result = prime * result + x;
    result = prime * result + y;
    return result;
}

至少，在hashCode算法中加入一个素数将有助于其“唯一性”。

- nybbler

---

也许你是误写了“Java”，而不是“Eclipse”。默认情况下，hashCode“通常通过将对象的内部地址转换为整数来实现”。 - Matthew Flaschen

@MatthewFlaschen 确实是这样。现在已经更新了，感谢你的指出。 - nybbler