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

Question

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

Answer 1

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

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

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

• 换位表本身
• 将位置映射到键的哈希函数 hash(有关更多详细信息，请查看 Zobrist hashing)

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

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;

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

以下是一些进一步的链接，可以帮助您编写自己的链接:

• http://chessprogramming.wikispaces.com/Transposition+Table
• https://en.wikipedia.org/wiki/Transposition_table