如何有效地散列二维数组（存储在 HashSet 中）？

Question

我编写了一个名为 PuzzleBoard 的类，它代表 nxn 板。我将在 HashSet 中保留多个 PuzzleBoard 对象，因此我必须覆盖“int hashCode()”方法。

下面是我的类的字段：

 private int N;
 private int[][] puzzle;
 private int blankCellX;
 private int blankCellY;
 private int cost;

Eclipse 自动为我生成的是：

 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + N;
  result = prime * result + blankCellX;
  result = prime * result + blankCellY;
  result = prime * result + cost;
  result = prime * result + Arrays.hashCode(puzzle);
  return result;
 } 

认为该方法没有考虑二维数组的内容，我将其更改为：

 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + N;
  result = prime * result + blankCellX;
  result = prime * result + blankCellY;
  result = prime * result + cost;
  for (int i = 0; i < N; ++i)
   result = prime * result + Arrays.hashCode(puzzle[i]);
  return result;
 } 

但是，该方法的问题是完成时间太长：O(N^2) 此外; 'result' 变量很可能会溢出。

现在，我的问题是，如何编写一个不需要太长时间即可完成的高效哈希方法。而且;在 HashSet 中插入或搜索对象应该是高效的（接近恒定时间）。

在最坏的情况下，N 将为 10，并且 HashSet 将包含约 1000 个 PuzzleBoard。

我为什么要做这一切？ 我正在使用 A* 算法实现 N-Puzzle 问题的解决方案。因此，在算法的某个阶段，给定当前节点（板的配置），我将空白单元向上、向下、向右或向左移动以生成新的子节点。因此，谜题配置通常会有 1 或 2 个单元格的差异。我将所有探索过的节点存储在 HashSet 中。

预先感谢 =)

Answer 1

哈希码不需要是唯一的，如果是的话那就更好了。由于 HashSet 中的项目数量相对较少（~1000），因此您可以选择少量合适的数据来一起哈希。例如，也许您只需要“拼图”表的第一行，或者“成本”变量对于不同的实例可能有足够的不同，您可以将其用作差异的良好来源。

结果是否溢出并不重要：您想要的只是让不同的对象在可能的情况下返回不同的哈希码。哈希值的实际值并不重要。

Answer 2

此方法不考虑二维数组的内容

您还可以使用 util.Arrays#deepHashCode()。

但是这个方法的问题是完成时间太长：O(N^2)

如果你想对其中所有的 N^2 个整数进行哈希处理，你就不能走得更快吗？如果 N 至多为 10，那么 Big-O 表示法又是什么呢？ O(n^2) 并不意味着慢。我不认为你的 hashCode 方法效率低下。低效率或一些 O(n^2) 很可能是在其他地方......不过，如果经常调用此方法（并且 PuzzleBoard 是不可变的），您可能希望缓存 hashCode 值。

“结果”变量很可能溢出。

没问题！ Java 中定义了溢出。

此外；在 HashSet 中插入或搜索对象应该是高效的（接近恒定时间）。

插入很可能只是摊销常数时间。当 HashSet 满了时，将创建一个新的更大的 HashSet。所有元素都被复制到其中，所有的 hashCode 都必须重新计算。尝试为 HashSet 设置一个初始容量？

result = prime * result + cost;

您确定要将成本（我假设是深度）包含在 equals 和 hashCode 中吗？无论我花了多少步骤才到达那里，两个配置都是相同的，对吗？

~1000 个拼图板

如果我没记错的话，上次我解决这个谜题时我有很多超过 1000 个配置。