覆盖滑动拼图问题的Hashcode函数

Question

我为滑动谜题的每个状态分配一个哈希码。我目前拥有的代码为不同的状态返回相同的哈希码。有谁知道一种有效的方法来唯一散列滑动谜题的状态?

public int hashCode() {
int total = 2;

if(board[0][0] == -1) {
total += 9;
}
else{
total += 9 * board[0][0];
}
if(board[0][1] == 1){
total += 1;
}
else{
total += 1 * board[0][1];
}
if(board[0][2] == 2){
total += 2;
}
else{
total += 2 * board[0][2];
}
if(board[1][0] == 3){
total += 3;
}
else{
total += 3 * board[1][0];
}
if(board[1][1] == 4){
total += 4;
}
else{
total += 4 * board[1][1];
}

. .等

Answer 1

哈希码可以不唯一。哈希冲突是现实生活中的一个事实，实现应该能够处理。

你所寻找的更多的是一个状态的代表。这个谜题的一种状态是数字0 (?意思是空)，1-8。因此，您正在寻找排列的唯一数字表示。

这将被称为Lehmer代码:

https://en.wikipedia.org/wiki/Permutation Numbering_permutations

理论说了这么多，但如何实现呢?下面是一个建议的算法:

https://www.researchgate.net/figure/The-Lehmer-code-A-complete-translation-from-permutation-to-decimal-by-way-of-the_fig1_230831447

Answer 2

计算数组的哈希码是一个常见的任务，Java API提供了一个方法:

Arrays.deepHashCode(board)

(如果您对数组的内容有额外的了解，您可能能够制作一个更好的哈希码函数，但是通用的哈希码函数相当不错，您的时间可能更好地花在其他地方优化)

如果您对Java API是如何做到这一点感到好奇，下面是实现的突出部分:

public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}

可以看到，在添加下一个元素之前，实现将前面的结果与一个常量相乘。如果我们将结果存储在以31为基数的位置数系统中，那么这将把前一个结果的数字向左移动一个位置，然后在最低的数字中添加有关新元素的信息。由于前面的数字已经被移开，所以新旧数字之间没有重叠，只要结果不溢出，就可以完美地重构信息。即使结果溢出，它也会减少2的次幂，因为31是2的素数，所以旧数字的一些信息会保留下来。

如果您知道您的数组包含较小的数字(例如，小于15)，那么将其乘以15而不是31是更可取的，因为它可以在开始溢出之前编码更多的元素，从而稍微更好地分散散列值。