java - 为什么我的 HashMap 识别出不应该是键的散列键？

Question

我正在编写黑白棋游戏程序，我正在按以下方式存储在 HashMap 中找到的可能走法:

Hashmap<Matrix, PossibleMovesVector>

Matrix 是一个包含int[8][8] 的对象，它描述了当前棋盘的情况。它以下列方式覆盖 hashCode() 和 equals()。 (这是必要的，因为多维数组的标准 hashCode() 不查看嵌套数组的内容。)

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + Arrays.deepHashCode(board);
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Matrix other = (Matrix) obj;
    if (!Arrays.equals(board, other.board))
        return false;
    return true;
}

这似乎工作正常。但是当我测试它并在我的屏幕上绘制大约 100 个左右的新板时，我突然在我的控制台中收到以下消息:

Recognized hashCode xxxxxxxxxx
Getting moves from HashMap...

但这发生在一 block 我知道是新的板上。难不成奥赛罗有那么多状态，以至于哈希码会重复自己？这是我能找到的唯一解释。那，或者我的代码有问题。但我不认为最后一种情况是这样，因为它需要很长时间才能出错。

编辑:这就是我的程序的大致工作方式。 getMoves() 有点罗嗦，但它所做的就是:检查棋盘是否已经检查过棋步，如果没有检查可能的棋步。
- 每当玩家移动时，m.board 都会更改。 (而不是创建一个全新的 Matrix 对象。)
- boardHash 包含另一个哈希表(尽管我更喜欢简单的数组)，它存储可能的移动是针对玩家 1 还是玩家 2。在我之前的帖子中，我认为这无关紧要，因此将其简化为单个 vector 。

代码大致是这样的:

public void Init(){  
    //Initialize board  
    m_board = new Matrix(new int[8][8]);  
    m_board.Init();  
    //Compute initial possible moves  
    boardHash.put(m_board, new HashMap<Integer, Vector<Matrix>>());  
    boardHash.get(m_board).put(whosTurn, getPossibleMoves(whosTurn));  
}   

    public Vector<Matrix> getPossibleMoves(int forWho) {
        // Assign variable so the code doesn't get too cluttered
        HashMap<Integer, Vector<Matrix>> moveMap = boardHash.get(m_board);

        // Maybe moveMap doesn't even exist is our lookup table yet
        if(moveMap == null){
            System.out.println("\nNever before seen board...");
            moveMap = new HashMap<Integer, Vector<Matrix>>();
            boardHash.put(m_board, moveMap);
            moveMap.put(forWho,getPossibleMoves(forWho));
        }else{
            System.out.println("\nRecognized hashCode "+m_board.hashCode());                
            // If it does exist, maybe no possible moves are stored in it 
            if(moveMap.get(forWho)==null){  
                boardHash.put(m_board, m_board.board);
                //So then make it:
                // System.out.println("No moves for "+side+" yet...");
                Vector<Matrix> v_possMoves = new Vector<Matrix>();
                //For every empty square on the current field...
                for(int column = 0; column<8; column++){
                    for(int row = 0; row<m_board.board[column].length; row++){
                        if(m_board.board[column][row] == 0){
                            //Check if this move is valid, and if it is, return the resulting board
                            Matrix possibleMoveMatrix = new Matrix(makeLines(column,row,forWho));
                            if(possibleMoveMatrix.board != null){
                                //add it to the vector
                                v_possMoves.add(possibleMoveMatrix);
                            }
                        }
                    }
                }
                if(v_possMoves.isEmpty()){
                    System.out.println("No possible moves for player "+forWho);
                }
                moveMap.put(forWho,v_possMoves);
            }
        }
        return moveMap.get(forWho);
        }

Answer 1

编辑:我刚刚想到了一些肯定会导致问题的东西。你曾经修改过 Matrix 中的数组吗？将键添加到 map 后，您绝不能更改键中的相关值 - 这可能会导致误报甚至漏报(您可以使用在 put 中使用的相同键引用，如果您进行了影响哈希码的更改，则找不到与 get 的匹配项，例如)。

---

不清楚是什么代码在打印“已识别的哈希代码”部分……但听起来像是假设哈希代码是唯一的。 不要那样做。它们不应该是唯一的。它们意味着可能相等性的指示 - 一种使查找内容更快的优化。这个想法是，如果您找到匹配的哈希码，您应该始终检查“真正的”相等性。

您还没有说出数组中的值是什么，但假设它们是 0(空)1(黑色)和 2(白色)，则这些值的可能组合 远 比一个普通的 ol' 32 位哈希码可以表示...您有 3⁶⁴ 种可能性，这比 2³² 多。现在我敢说其中大部分都不是真正可行的奥赛罗棋盘，但如果 Arrays.deepHashCode 试图针对这种情况进行优化，以便为所有有效的提供唯一的哈希码，我会感到惊讶黑白棋棋盘，即使这是可能的。

作为旁注，您的 hashCode 方法比它需要的要复杂得多。试试这个:

@Override
public int hashCode() { 
  return Arrays.deepHashCode(board); 
}