为什么我的HashMap识别出不应该是键的哈希键？

Question

我正在编写奥赛罗的游戏,我正在HashMap以下列方式存储在a 中找到的可能移动:

Hashmap<Matrix, PossibleMovesVector>

Matrix是一个包含a的对象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块左右的新板时,我突然在控制台中收到以下消息:

已识别的hashCode xxxxxxxxxx
从HashMap获取移动...

但这种情况发生在我认识的新板上.可能是奥赛罗有这么多状态,哈希码重演了吗？这是我能找到的唯一解释.那,或者我的代码有问题.但我不认为最后一种情况是这样的,因为它需要很长时间才能出错.

编辑:这大致是我的程序的工作方式.getMoves()有点罗嗦,但它所做的只是:检查电路板是否已经检查过移动,如果没有检查可能的移动.
- 每当玩家移动时,m.board就会改变.(而不是制作一个全新的Matrix对象.)
- boardHash包含另一个哈希表(我更喜欢一个普通的简单数组),它存储可能的移动是针对玩家1还是玩家2.在我以前的帖子中我没有'认为这是相关的,因此将其简化为单个向量.

粗略地,代码如下所示:

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？在将密钥添加到地图后,您不得更改密钥中的相关值 - 这可能会导致误报甚至漏报(您可以使用您使用的相同密钥参考put,get如果您已经使用,则找不到匹配项例如,影响哈希码的更改.

目前尚不清楚哪些代码正在打印"已识别的hashCode"部分...但听起来它假设哈希码是唯一的.不要那样做.他们不应该是独一无二的.它们意味着可能的平等 - 一种优化,可以更快找到东西.我们的想法是,如果您找到匹配的哈希码,则应始终检查"真实"相等.

你还没说你的数组中的值,但假设他们是0(空)1(黑色)和2(白色),有远者比一个普通OL" 32位散列码的更可能的组合代表......你有3 ^64种可能性,相当于超过2 ³².现在我敢说大部分都不是真正可行的奥赛罗板,但是如果Arrays.deepHashCode试图针对这种情况进行优化我会感到惊讶,以便为所有有效的奥赛罗板提供唯一的哈希码,即使这是可能的.

作为旁注,您的hashCode方法比它需要的更复杂.试试这个:

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