Why does my HashMap recognize hash keys that aren't supposed to be keys yet?

Question

I'm programming the game of Othello and I am storing the possible moves found in a HashMap in the following way:

Hashmap<Matrix, PossibleMovesVector>

Matrix is an object which contains an int[8][8], which describes the current board situation. It overrides hashCode() and equals() in the following way. (This was necessary because the standard hashCode() for multidimensional arrays don't look at the contents of nested arrays.)

@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;
}

This seemed to work OK. But when I tested it out, and painted about 100 or so new boards on my screen, I suddenly got the following message in my console:

Recognized hashCode xxxxxxxxxx
Getting moves from HashMap...

But this happens for a board which I know is new. Can it be that Othello has so many states that hashcodes repeat themselves? This is the only explanation I could find. That, or there's something wrong in my code. But I don't think that last scenario's the case, because it takes so long to go wrong.

EDIT: This is roughly how my program works. getMoves() is a bit wordy, but all it does is: check if the board has already been checked for moves, if it's not go check the possible moves.
- Whenever a player makes a move m.board is changed. (Instead of making a whole new Matrix object.)
- boardHash contains another hash table (I would prefer a plain and simple array, though) which stores whether the possible move is for player 1 or player 2. In my previous post I didn't think this was relevant, so simplified it to a single vector.

The code, roughly, looks like this:

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

Using Arrays.equals in your implementation of equals() is not right. You should be using Arrays.deepEquals. So your implementation of equals() will end in:

Matrix other = (Matrix) obj; return Arrays.deepEquals(board, other.board);

See http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html

Answer 2

EDIT: I've just thought of something which could certainly cause a problem. Do you ever modify the array in Matrix? You mustn't change the relevant values within a key after adding it to a map - it will potentially cause false positives and even false negatives (you could use the same key reference you used in put and not find a match with get if you've made a change which affects the hash code, for example).

---

It's not clear what code is printing the "Recognized hashCode" part... but it sounds like it's assuming hash codes are unique. Don't do that. They're not supposed to be unique. They're meant to be an indication of possible equality - an optimization to make finding something faster. The idea is that if you find a matching hash code, you should always check for "real" equality.

You haven't said what the values in your array are, but assuming they're 0 (empty) 1 (black) and 2 (white) there are far more possible combinations of those than a plain ol' 32-bit hash code can represent... you've got 3⁶⁴ possibilities, which is rather more than 2³². Now I dare say most of those aren't really feasible Othello boards, but I'd be surprised if Arrays.deepHashCode attempted to optimize for exactly this case, in order to provide unique hash codes for all valid Othello boards, even if that is possible.

As a side note, your hashCode method is rather more complicated than it needs to be. Try this:

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