如何处理国际象棋换位表哈希函数中的负值？

Question

我正在用 Java 编写一个国际象棋引擎。为了优化搜索速度，我实现了一个换位表来存储以前搜索的结果。在转置表中，位置通常表示为 64 位 Zobrist 哈希。

但是，由于这太大了，无法用作包含表值的数组的索引，因此国际象棋引擎使用另一个哈希函数来返回可以用作索引的较小数字。根据我在网上阅读的内容，第二个哈希函数常用的公式是：

index = zobristKey % entries.size

我的问题是，在Java中我使用（有符号）long作为我的zobrist键，这意味着结果索引有时会有负值，不能用作数组索引。我目前通过调用 Math.abs(index) 来解决这个问题，但结果我看到很多哈希表冲突。

我对哈希函数的一般理解不是那么强，而且我确信我在当前的实现中遗漏了一些东西。对于任何国际象棋引擎程序员/Java专家来说，计算这样的转置表的哈希表索引的正确方法是什么？

我的哈希函数从 Zobrist 键创建哈希表索引：

    private int getIndex(long zobristKey) { return Math.abs(Long.valueOf(zobristKey % entries.length).intValue()); }

Answer 1

如果

Math.abs

产生大量碰撞，没有其他选择可以避免。

话虽如此，应用

& Integer.MAX_VALUE

而不是

Math.abs

将更有效地避免密钥为

Long.MIN_VALUE

的边缘情况，其中

Math.abs

将返回负数。