4

我正在创建一个国际象棋程序，该程序利用先前评估位置的哈希表来（希望）减少搜索时间。唯一的问题是我使用 ArrayList 来存储哈希值，并且查找时间会根据我存储的位置数而增加。如何获得一个具有独立于当前大小的查找时间的哈希表？（请原谅我，我在 java 方面有点菜鸟，目标 c 真的是我的事）

编辑：如果重要的话，我正在使用 Zobrist 快速散列技术。根据一些试验，我确定不是哈希键的生成占用了大量时间。散列方法非常快，其对速度的影响几乎不明显。

4

3 回答 3

5

标准的 Java HashMap 非常好，并且已经可供您使用，但是如果您想要 Java 中最快的地图，请使用 Trove ( http://trove4j.sourceforge.net/html/overview.html )，它填充了以下数据结构针对性能进行了优化。

于 2013-01-09T02:31:18.503 回答
4

首先是一个初步说明：在国际象棋术语中，术语转置表比“哈希表”更常见，并且会在 Google 上为您提供更好的搜索结果。

考虑到这一点，转置表和通用哈希表（例如，Java Map）之间有一个重要区别：

映射是一个关联数组，它保证在插入新值时不会删除现有条目。通常，这是您想要的，但是当您编写国际象棋引擎时，如果您不删除或覆盖旧条目，您很快就会耗尽内存。

相比之下，转置表更像是一个缓存，它只包含最近的条目。它可以实现为一个简单的固定大小的数组，由当前位置的哈希值寻址。计算密钥的一种众所周知且非常有效的方法是Zobrist 散列（您已经在问题中提到它）。该键用于索引数组。添加新条目时，它们将简单地覆盖现有条目。

这里有一些伪代码来说明这个想法：

// the transposition table entry
class TTEntry {
  long hashKey; // should be at least 64-bit to be safe

  // other information, e.g.:
  Move move;
  int distance;
  // ...
}

TTEntry[] ttable = ... // the more memory, the better

Entry getTTEntry(Board board) {
  long hashKey = board.getHashKey();
  int index = hashKey % ttable.length;
  return ttable[index];
}

void store(Board board) {
  Entry entry = getTTEntry(board);
  entry.hashKey = board.getHashKey();
  entry.move = ...;
  entry.distance = ...;
}

void probe(Board board) {
  Entry entry = getTTEntry(board);
  if (entry.hashKey == hashKey) {
    // entry found
    // ... do something with entry.move and entry.distance
  }
}

您说您使用了一个，ArrayList但您的查找时间随着存储位置的数量而增加。如果您使用上面示例中的技术，那将永远不会发生。它不仅与搜索到的位置数量无关，而且它也会比 a 快HashMap，后者内部要复杂得多。

于 2013-01-14T23:12:37.710 回答
2

java.util.HashMap是你最好的选择。键查找是O(1)（摊销的），它是一个非常好的通用 HashMap。

这并不是说它是最佳的：如果您知道如何并且有很多时间/决心，您当然可以设计一个自定义哈希图实现以更好地适应您的特殊情况。但是一个常规的 HashMap 绝对是开始的地方——你以后总是可以优化的。

于 2013-01-09T02:23:22.040 回答