java - 我将如何散列一个矩形？

Question

我有一个 Rectangle 类。它具有长度、宽度和面积（所有整数）。我想对它进行散列，使得具有相同长度和宽度的每个矩形散列到相同的值。有什么方法可以做到这一点？

编辑：我理解这是一个广泛的问题。这就是为什么我要求“一种”方式来做到这一点。不是最好的方法。

Answer 1

一个好的和简单的方案是计算一对整数的哈希值，如下所示：

hash = length * CONSTANT + width

CONSTANT根据经验，如果是素数，您将获得最佳结果（即最少的数字冲突） 。很多人¹推荐一个值 like 31，但最好的选择取决于和值的最可能范围。如果它们是严格有界的，并且足够小，那么你可以做得比.lengthwidth31

但是，31对于实际目的来说可能已经足够了²。此级别的一些冲突不太可能产生显着的性能差异，即使是完美的哈希函数也不能消除哈希表级别的冲突......您使用哈希值的模数。

---

^{1 - 我不确定这个数字来自哪里，或者是否有实证研究支持它......在一般情况下。我怀疑它来自（ASCII）字符串的散列。但是31是素数...并且它是梅森素数 ( 2^7 - 1)，这意味着如果硬件倍数很慢，则可以使用移位和减法来计算它。}

^{2 - 我排除了您需要担心有人故意创建哈希函数冲突以试图“破坏”某些东西的情况。}

Answer 2

您可以使用具有HashCodeBuilder类的 Apache Commons 库。假设您有一个Rectangle带有 awidth和 a的类height，您可以添加以下方法：

@Override
public int hashCode(){
  return new HashCodeBuilder().append(width).append(height).append(children).toHashCode();
}

Answer 3

您想要的（正如您对问题的评论中所阐明的那样）是不可能的。有 N 个可能的 hashCode，每个 int 一个，其中 N 约为 42 亿。假设矩形必须具有正尺寸，则有 ((N * N) / 4) 个可能的矩形。你建议如何让它们适合 N 个 hashCodes？当 N > 4 时，可能的矩形比 hashCode 多。