rust - 换位表的btreemap vs hashmap

Question

我创建了一个minimax算法，该算法使用alpha beta修剪和换位表来加快搜索速度。我目前正在使用一个哈希图，该哈希图使用板状态作为键并将分数保存为值。 (游戏是在5x5板上的井字游戏)
这样做的问题是散列很慢，并且由于 key 占用了大量内存，因此使用整个板状态。董事会状态由具有3种可能类型的枚举的二维数组表示:空白，X和O。我想使用自己的哈希(可能是zobrist)作为键，而根本不保存董事会状态，但是哈希图会拿走我的 key ，然后再次对其进行哈希处理。我考虑过使用btree映射将键视为唯一键，但是访问时间为log(n)而不是O(1)。我也完全不在乎键的顺序，因此btree似乎并不适合这里。
所以我的问题是，哪种数据结构在这里比较理想？即使哈希表第二次哈希了我的 key ，我仍应使用哈希表吗？

Answer 1

我一直在做类似的事情，这就是我最终适应了您的情况的结果:

紧凑型板表示形式:假设一块5x5板，每个单元具有3个可能值之一:这意味着每个单元可以使用2位，总计25 * 2 = 50位。这些将适合u64。这使得哈希图中的哈希/存储条目相当便宜。
就我而言，我还使用了u64(请参阅https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L20-L22)，并考虑将这个值直接用作哈希值(指定一个自己的散列器，该哈希器只是将值通过隧道传输)，但是如果我没记错的话，使用“真实的”哈希函数就可以了更快。 (可能会有更好的碰撞行为吗？)

我最终手动插入了回溯的内容(请参阅https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L247-L253和https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L267-L272)，这大大加快了事情的进行。

我使用生成的查找表(https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L17，https://github.com/phimuemue/brainball_solver/blob/master/build.rs#L37-L79)实现了移动，以加快移动速度。

所有这些都应与一粒盐一起服用。就我而言，它有助于加快搜索速度，但您必须分别测试您的情况。