1

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

我想将这些点放入一个哈希表中，其中点是关键。

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

class Point {
   public double x;
   public double y;

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

3 回答 3

2

数字倾向于聚集在大多数坐标平面上；因为，我们倾向于使用舒适范围内的数字。出于这个原因，普通的异或组合是不可取的，因为所有的数字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;
}

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

于 2012-06-07T16:38:56.660 回答
0

我不确定双精度的散列有多好，但你应该能够做到：

public int hashCode() {
  return x.hashCode() ^ y.hashCode();
}

如果这在测试中产生了太多的冲突（你这样做对吗？），你可以通过位移、幻数等来改变它。真的，各种按位运算。

这是Java吗？我的答案基于我对 C# 的经验。

于 2012-06-07T16:30:35.067 回答
0

你可以使用任何你想要的功能。这完全取决于您的坐标是什么典型值，以及您希望散列函数有多好。

例如，如果您的所有积分都在 1 到 100 万之间，那么您可以使用类似的东西（这是 C++ 代码，不知道您使用的是什么语言）。

size_t hashCode = (size_t)x * (size_t)y;

或者您可以添加这些值，或将这些值相乘，或者做任何您想做的事情。

size_t hashCode = (size_t)(x+y);

或者

size_t hashCode = (size_t)(x*y);

甚至

size_t hashCode = (size_t)(x*y) + (size_t)(x+y);
于 2012-06-07T16:35:26.473 回答