c++ - 转置表使算法变慢（我做错了吗？）

我使用 Zobrist 密钥（64 位）存储每个位置。我将这些论文存储在 std::vector 中。一开始我 std::vector::reserve(1,000,000)。搜索一个位置时，要花很长时间检查key是否在向量中，如果是，则需要很长时间才能找到它。

当转置向量变得如此长时，这种情况发生在稍后的深度，重新计算位置而不是寻找转置会更快。

我试过的：

- 将键插入从最小到最大排序的向量中，然后使用二进制搜索来定位它们。

- 将密钥推送到向量，每次我想检查密钥时，循环遍历向量以检查匹配的密钥。

此外，如果它有助于有效地散列密钥不是问题，我已经实现了它，以便每次移动时它都会更新。

标签： c++chess

您可以使用大小为 2 的幂的向量，并屏蔽掉 Zobrist 散列的相应部分以获取向量的索引。例如：

std::vector<whatever> x(0x100000)
std::int64_t hash = get_hash_from_somewhere();
whatever& value = x[hash & 0xFFFFF];

如果该掩码导致太多冲突，您可能需要使用更复杂的掩码。