好的2D坐标哈希函数

Question

我想使用一个HashMap来将(x, y)坐标映射到相应的值上。 那么，hashCode()函数该如何定义呢？ 在这种情况下，我只存储形式为(x, y)，且y-x=0,1,...,M-1 (M是某个参数)的整数坐标。

- I Like to Code

---

我认为默认的Eclipse哈希生成器会给出31*x+y。 - k_g

你想要找到精确匹配还是近似坐标？ - martinstoeckli

@martinstoeckli 我只对查找精确匹配感兴趣，即获取键（x，y）对应的值并设置键（x，y）对应的值。 - I Like to Code

Answer 1

要从两个数字中获取唯一值，可以使用在此处描述的双射算法： < x; y >= x + (y + ( (( x +1 ) /2) * (( x +1 ) /2) ) )

这将为您提供可用于哈希码的唯一值。

public int hashCode()
{
      int tmp = ( y +  ((x+1)/2));
               return x +  ( tmp * tmp);
}

- Mani

Answer 2

我通常使用 Objects.hash(Object... value) 为一系列项生成哈希码。

该哈希码的生成方式，就好像所有输入值都被放置在一个数组中，并通过调用 Arrays.hashCode(Object[]) 对该数组进行哈希。

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

对于三维坐标，请使用Objects.hash(x, y, z)。

如果您希望手动处理它，可以使用以下方式计算hashCode：

// For 2D coordinates
hashCode = LARGE_PRIME * X + Y;

// For 3D coordinates
hashCode = LARGE_PRIME^2 * X + LARGE_PRIME * Y + Z;

- Adithya Upadhya

Answer 3

你考虑过将x或y的值移动可用位数的一半吗？

对于“经典”的8位，每个轴只有16个单元格，但是对于今天的“标准”32位，每个轴的单元格数量增加到超过65k个。

@override
public int hashCode() {
    return x | (y << 15);
}

显而易见的是，只要x和y都在0到0xFFFF（0-65535，包括）之间，这种方法才有效，但这已经足够大了，超过了42亿个单元格。

编辑： 另一个选择是，如果你知道实际大小，可以使用x + y * width（其中width当然是朝x方向的）。

- yes

---

欢迎来到SO。我认为你可能提出了一个有效的观点，但是你的帖子可能会被关闭，因为它不符合SO的问答格式。考虑重新表述你的帖子作为对OP问题的回答，并添加代码和/或其他示例，以展示你的解决方案如何实现。 - m00am

Answer 4

为了计算具有多个属性的对象的哈希码，通常会实现一种通用解决方案。此实现使用一个常数因子来组合属性，该因子的值是discussions的主题。似乎因子33或397通常会导致哈希码的良好分布，因此它们适用于字典。

这是C＃的一个小例子，但应该很容易适应Java：

public override int GetHashCode()
{
  unchecked // integer overflows are accepted here
  {
    int hashCode = 0;
    hashCode = (hashCode * 397) ^ this.Hue.GetHashCode();
    hashCode = (hashCode * 397) ^ this.Saturation.GetHashCode();
    hashCode = (hashCode * 397) ^ this.Luminance.GetHashCode();
    return hashCode;
  }
}

这个方案也适用于您的坐标，只需将属性替换为X和Y值即可。请注意，我们应该防止整数溢出异常，在DotNet中，可以通过使用unchecked代码块来实现。

- martinstoeckli

Answer 5

这取决于您打算使用哈希码的目的：

如果您计划将其用作一种索引，例如，知道 x 和 y 将散列为存储 (x, y) 数据的索引，最好使用向量来进行此类操作。

Coordinates[][] coordinatesBucket = new Coordinates[maxY][maxX];

但如果你必须为每个（x，y）组合拥有唯一的哈希值，那么尝试将坐标应用于十进制表格（而不是加法或乘法）。例如，x=20 y=40 将给你一个简单且独特的代码 xy=2040。

- WTRIX