java - 如何有效地对二维数组进行哈希处理(存储在 HashSet 中)？

Question

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

下面是我类(class)的领域:

 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 个 PuzzleBoards。

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

提前致谢 =)

Answer 1

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

结果是否溢出无关紧要:如果可能的话，您想要的只是让不同的对象返回不同的哈希码。哈希的实际值并不重要。