Java中的快速哈希表

Question

我正在创建一个国际象棋程序,它利用先前评估位置的哈希表来(希望)减少搜索时间.唯一的问题是我使用ArrayList来存储哈希值,并且查找时间会根据我存储的位置而增加.如何获得具有独立于当前大小的查找时间的哈希表？(原谅我,我有点像java的菜鸟,客观c真是我的事)

编辑:如果重要,我正在使用Zobrist快速散列技术.基于一些试验,我已经确定它不是占用大量时间的哈希键的生成.散列方法非常快,它对速度的影响几乎不明显.

Answer 1

标准的Java HashMap非常好并且已经可以使用了,但是如果你想在Java中使用惊人的最快的地图,可以使用Trove(http://trove4j.sourceforge.net/html/overview.html),它充满了数据结构.优化性能.

Answer 2

首先，初步说明：在国际象棋术语中，术语“转置表”比“哈希表”更常见，并且会给您在 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但您的查找时间随着存储位置的数量而增加。如果您使用上面示例中的技术，则永远不会发生这种情况。它不仅与搜索位置的数量无关，而且比HashMap内部复杂得多的 a 更快。