rust - 转置表的 btreemap 与 hashmap

Question

我创建了一个极小极大算法，它使用 alpha beta 剪枝和换位表来加速搜索。我目前正在使用一个 HashMap ，该 HashMap 使用棋盘状态作为键并将分数保存为值。 (游戏是 5x5 棋盘上的井字游戏)

这样做的问题是散列速度很慢，并且使用整个棋盘状态作为 key 会占用大量内存。棋盘状态由具有 3 种可能类型的二维枚举数组表示:Blank、X 和 O。我想使用我自己的哈希(可能是 zobrist)作为键，根本不保存棋盘状态，但 HashMap 会拿走我的 key 并再次散列它。我考虑过使用 btree 映射，它将键视为唯一，但访问时间是 log(n) 而不是 O(1)。我也根本不关心键的顺序，因此 btree 似乎并不适合这里。

所以我的问题是，哪种数据结构是理想的？即使它第二次对我的 key 进行哈希处理，我也应该使用 HashMap 吗？

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 )来实现移动，以加快移动速度。

所有这些都必须持保留态度。就我而言，它有助于加快搜索速度，但您必须单独测试您的案例。