btreemap 与 hashmap 的转置 table
btreemap vs hashmap for transposition table
我创建了一个 minimax 算法，它使用 alpha beta 修剪和转置 table 来加快搜索速度。我目前正在使用一个哈希图，它使用棋盘状态作为键并将分数保存为值。 （游戏是 5x5 棋盘上的井字游戏）
这个问题是散列很慢，并且使用整个棋盘状态作为密钥会占用大量内存。棋盘状态由具有 3 种可能类型的二维枚举数组表示：空白、X 和 O。我想使用我自己的哈希（可能是 zobrist）作为键并且根本不保存棋盘状态，但是哈希图会拿走我的钥匙并再次散列。我考虑过使用将键视为唯一的 btree 映射，但访问时间是 log(n) 而不是 O(1)。我也不关心键的顺序，所以 btree 似乎并不适合这里。
所以我的问题是，哪种数据结构在这里最理想？即使它对我的密钥进行了第二次哈希处理，我也应该使用哈希映射吗？
我一直在做类似的事情，这就是我根据你的情况做出的结果：
紧凑的电路板表示：假设一个 5x5 电路板，每个单元格具有 3 个可能值之一：这意味着每个单元格可以使用 2 位，总共 25*2=50 位。这些将适合 u64。这使得哈希映射中的 hashing/storing 个条目非常便宜。
在我的例子中，我还使用了 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 and 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) 实现了移动以加快移动速度。
对所有这些都持保留态度。就我而言，它有助于加快搜索速度，但您必须单独测试您的案例。
我创建了一个 minimax 算法，它使用 alpha beta 修剪和转置 table 来加快搜索速度。我目前正在使用一个哈希图，它使用棋盘状态作为键并将分数保存为值。 （游戏是 5x5 棋盘上的井字游戏）
这个问题是散列很慢，并且使用整个棋盘状态作为密钥会占用大量内存。棋盘状态由具有 3 种可能类型的二维枚举数组表示：空白、X 和 O。我想使用我自己的哈希（可能是 zobrist）作为键并且根本不保存棋盘状态，但是哈希图会拿走我的钥匙并再次散列。我考虑过使用将键视为唯一的 btree 映射，但访问时间是 log(n) 而不是 O(1)。我也不关心键的顺序，所以 btree 似乎并不适合这里。
所以我的问题是，哪种数据结构在这里最理想？即使它对我的密钥进行了第二次哈希处理，我也应该使用哈希映射吗？
我一直在做类似的事情，这就是我根据你的情况做出的结果：
紧凑的电路板表示：假设一个 5x5 电路板，每个单元格具有 3 个可能值之一：这意味着每个单元格可以使用 2 位，总共 25*2=50 位。这些将适合
u64。这使得哈希映射中的 hashing/storing 个条目非常便宜。在我的例子中，我还使用了
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 and 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) 实现了移动以加快移动速度。
对所有这些都持保留态度。就我而言，它有助于加快搜索速度，但您必须单独测试您的案例。