Java 中浮点数的哈希码

Question

我有一个 class，带有两个浮点变量和 hashCode 方法（当前代码片段中没有 equals）：

public class TestPoint2D {
    private float x;
    private float z;

    public TestPoint2D(float x, float z) {
        this.x = x;
        this.z = z;
    }

    @Override
    public int hashCode() {
        int result = (x != +0.0f ? Float.floatToIntBits(x) : 0);
        result = 31 * result + (z != +0.0f ? Float.floatToIntBits(z) : 0);
        return result;
    }
}

下面测试

@Test
public void tempTest() {
    TestPoint2D p1 = new TestPoint2D(3, -1);
    TestPoint2D p2 = new TestPoint2D(-3, 1);

    System.out.println(p1.hashCode());
    System.out.println(p2.hashCode());
}

returns 相同值：

-2025848832

在这种情况下，我无法在 HashSet / HashMap 中使用我的 TestPoint2D

任何人都可以建议如何在这种情况下实施 hashCode 或与此相关的解决方法吗？

P.S。又增加了一项测试：

@Test
public void hashCodeTest() {
    for (float a = 5; a < 100000; a += 1.5f) {
        float b = a + 1000 / a; // negative value depends on a
        TestPoint3D p1 = new TestPoint3D(a, -b);
        TestPoint3D p2 = new TestPoint3D(-a, b);
        Assert.assertEquals(p1.hashCode(), p2.hashCode());
    }
}

并通过证明

TestPoint2D(a, -b).hashCode() == TestPoint2D(-a, b).hashCode()

Answer 1

我会使用 Objects.hash():

public int hashCode() {
   return Objects.hash(x, z);
}

来自 Javadoc：

public static int hash(Object... values)

Generates a hash code for a sequence of input values. The hash code is generated as if all the input values were placed into an array, and that array were hashed by calling Arrays.hashCode(Object[]). This method is useful for implementing Object.hashCode() on objects containing multiple fields. For example, if an object that has three fields, x, y, and z, one could write:

Answer 2

根据 java 规范，2 个对象可以具有相同的 hashCode，但这并不意味着它们相等...

概率很小但是exist...

另一方面，同时覆盖 equals 和 hashcode 始终是一个好习惯...

Answer 3

据我了解，您希望键之间有很多对称的点对，因此您需要一种不会为它们提供相同代码的 hashCode 方法。

我做了一些测试，故意给 x 的符号赋予额外的意义往往会使对称点彼此远离。看这个测试程序：

public class Test {
  private float x;
  private float y;

  public static void main(String[] args) {
    int collisions = 0;
    for (int ix = 0; ix < 100; ix++) {
      for (int iz = 0; iz < 100; iz++) {
        Test t1 = new Test(ix, -iz);
        Test t2 = new Test(-ix, iz);
        if (t1.hashCode() == t2.hashCode()) {
          collisions++;
        }
      }
    }
    System.out.println(collisions);

  }

  public Test(float x, float y) {
    super();
    this.x = x;
    this.y = y;
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = (x >= 0) ? 1 : -1;
    result = prime * result + Float.floatToIntBits(x);
    result = prime * result + Float.floatToIntBits(y);
    return result;
  }
  // Equals omitted for compactness
}

如果没有 result = (x >= 0) ? 1 : -1; 行，它是由 Eclipse 生成的 hashCode()，并计算 9802 个对称点碰撞。有了这条线，它就算作一次对称点碰撞。

Answer 4

这些自动生成的哈希码函数不是很好。

问题是小整数会导致非常 "sparse" 和相似的位码。

要理解问题，请看实际计算。

System.out.format("%x\n", Float.floatToIntBits(1));
System.out.format("%x\n", Float.floatToIntBits(-1));
System.out.format("%x\n", Float.floatToIntBits(3));
System.out.format("%x\n", Float.floatToIntBits(-3));

给出：

如您所见，- 是 IEEE 浮点数中的最高位。与 31 的乘法不会显着改变它们：

问题是最后全是0。它们通过与任何素数的整数乘法得到保留（因为它们是 base-2 0，而不是 base-10！）。

所以恕我直言，最好的策略是采用移位，例如：

final int h1 = Float.floatToIntBits(x);
final int h2 = Float.floatToIntBits(z);
return h1 ^ ((h2 >>> 16) | (h2 << 16));

但您可能需要查看 Which hashing algorithm is best for uniqueness and speed? 和 test 以了解整数作为浮点数的特定情况。

Java 中浮点数的哈希码

Hash Codes for Floats in Java

java

floating-point

hashcode