C：简单快速的国际象棋哈希表？

Question

我想知道是否有人知道 C 中哈希表的良好实现。我想做的就是对棋盘进行哈希处理。我只是希望实施能够快速，并且能够一次性清理桌子。任何帮助将不胜感激！

Answer 1

在国际象棋中，多称为“换位表”。它是一种比哈希表更专业的数据结构。

转置表更像是缓存。它们比经典哈希表更快，因为它们的冲突处理要简单得多。旧条目最终会被驱逐。相反，经典哈希表绝不能删除条目，除非有要求。

我不知道换位表有可重用的实现。我见过的所有国际象棋引擎都有自己的实现。它包括两个方面：

• 换位表本身
• 哈希函数

  hash

  将位置映射到键（有关更多详细信息，请查看 Zobrist 哈希）

换位表本身非常简单。首先，您可以简单地使用一个大数组：

Entry* table = malloc(n * sizeof(Entry));
// ...

// clear transposition table
memset(table, 0, n * sizeof(Entry));

Position position; // the chess position
// ...

Key key = hash(position);

// probe
Entry entry = table[hash(position) % n];
if(entry.key == key)
{
  // found something --> entry can be used
  ...
}

// store
table[hash(position) % n] = updated_entry;

更高级的换位表通常使用多个槽，因此来自较深搜索的条目不会被来自较少搜索的条目驱逐。防止多线程引擎中的数据竞争也会使实际实现变得更加棘手。

这里有一些进一步的链接，可以帮助您编写自己的链接：

• https://www.chessprogramming.org/Transposition_Table
• https://en.wikipedia.org/wiki/Transposition_table