java - 如何散列 2D 平面中的几何点？

Question

简单地说，我有很多 (x, y) 形式的点。

我想将这些点放入哈希表中，以点为键。

我应该如何实现 Point 类的 hashCode() 方法？以Java为语言

class Point {
   public double x;
   public double y;

   @Override
   public int hashCode() {
      // How do I implement here?
   }
}

Answer 1

数字倾向于聚集在大多数坐标平面上；因为，我们倾向于喜欢使用舒适范围内的数字。出于这个原因，平凡的异或组合是不可取的，因为所有 x == y 的数字都会发生冲突，所有 x + 1 == y 和等等。

为避免这种情况，我建议您先反转 y 坐标的字节，然后再与 x 坐标进行异或运算。这会将一个输入的可变性最大的区域(低位字节)与另一个输入的可变性最小的区域(高位字节)结合起来。当考虑数字簇时(比如 x 的值在 1 到 1000 之间)，这样的算法将给出更均匀的分布。

由于散列算法在散列生成数字字段而无需大量聚类时效果最佳，因此这种解决方案实际上会使与散列相关的数据结构更快，因为散列冲突不那么频繁。

当然，以下是未优化的，您可能可以对其进行调整以满足您的需要，但这是基本思想:

public int hashCode() {

    long bits = Double.doubleToLongBits(y);
    byte[] ybits = new byte[] {
        (byte)((y >> 56) & 0xff),
        (byte)((y >> 48) & 0xff),
        (byte)((y >> 40) & 0xff),
        (byte)((y >> 32) & 0xff),
        (byte)((y >> 24) & 0xff),
        (byte)((y >> 16) & 0xff),
        (byte)((y >> 8) & 0xff),
        (byte)((y >> 0) & 0xff),
    };
    byte[] xbits = new byte[] {
        (byte)((x >> 56) & 0xff),
        (byte)((x >> 48) & 0xff),
        (byte)((x >> 40) & 0xff),
        (byte)((x >> 32) & 0xff),
        (byte)((x >> 24) & 0xff),
        (byte)((x >> 16) & 0xff),
        (byte)((x >> 8) & 0xff),
        (byte)((x >> 0) & 0xff),
    };
    // this combines the bytes of X with the reversed order
    // bytes of Y, and then packs both of those into 4 bytes
    // because we need to return an int (4 bytes).
    byte[] xorbits = new byte[] {
         (xbits[0]^ybits[7])^(xbits[4]^ybits[3]),
         (xbits[1]^ybits[6])^(xbits[5]^ybits[2]),
         (xbits[2]^ybits[5])^(xbits[6]^ybits[1]),
         (xbits[3]^ybits[4])^(xbits[7]^ybits[0]),
    };

    int value = 0;
    for (int i = 0; i < 3; i++) {
       value = (value << 8) + (by[i] & 0xff);
    }
    return value;
}

我建议的初始优化是将哈希码缓存在对象中以供后续查找，如果分析表明这是一个问题，也许可以更有效地管理创建/销毁的数组。