Java中的快速哈希表

Question

我正在创建一个国际象棋程序，利用哈希表存储之前评估的位置（以减少搜索时间）。唯一的问题是我正在使用ArrayList存储哈希值，而查询时间会随着我存储的位置数量的增加而增加。如何获得一个具有独立于其当前大小的查找时间的哈希表？（对不起，我有点Java新手，客观C才是我的专长）

编辑：如果有影响的话，我正在使用Zobrist快速哈希技术。根据一些试验，我已经确定生成哈希键并不占用大量时间。哈希方法非常快，对速度的影响几乎不可察觉。

- Christian Daley

---

使用 HashMap（或 HashSet）。 - Oliver Charlesworth

Answer 1

首先，一个初步说明：在国际象棋术语中，“置换表”这个术语比“哈希表”更常见，在谷歌搜索中会获得更好的结果。

在此基础上，转置表和通用哈希表（例如 Java 的 Map）之间有重要的区别：

Map 是关联数组，插入新值时保证不删除任何现有条目。通常情况下，这也是您想要的，但如果您编写一个国际象棋引擎，则很快会耗尽内存，除非您删除或覆盖旧条目。

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

下面是一些伪代码来说明这个想法：

// 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，但是随着存储位置的增加，查找时间也增加了。如果您使用上面示例中的技术，这种情况永远不会发生。它不仅独立于搜索位置的数量，而且比 HashMap 更快，后者在内部更为复杂。

- Philipp Claßen

Answer 2

标准的Java HashMap已经很不错了，并且已经可以使用，但如果您想要在Java中使用速度最快的映射，请使用Trove（http://trove4j.sourceforge.net/html/overview.html），其中填充了针对性能进行优化的数据结构。

- Tom Carchrae

---

谢谢大家，我使用了HashMap，它运行得很好！尽管它会使我的评估变慢一些，但缓存位置所节省的时间完全弥补了这一点！ - Christian Daley

Answer 3

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

这并不意味着它是最优的：如果您知道如何并且有大量时间/决心，您肯定可以设计一个定制的哈希映射实现以更好地适应您的特殊情况。但是，常规的 HashMap 绝对是开始的地方 - 您始终可以稍后进行优化。

- mikera