Fast hashing of 2-dimensional array

Question

I'm building a Reversi player using the standard alpha beta pruning search algorithm. I'm trying to add a translation table to store previously calculated nodes in the search tree. So I need to hash a 2 dimensional array representing the game board (the state) and store a value for that.

I can't come up with anything better than a double for loop iterating over my arrays and adding all values together multiplying them with the offsets to get unique hash values.

@Override
public int hashCode() {
    if (dirtyHash) {
        int hash = 0;
        for (int i = 0; i < Board.SIZEX; i++)
            for (int j = 0; j < Board.SIZEY; j++)
                hash += board[i][j] * (i + Board.SIZEY * j);

        hashValue = hash;
        dirtyHash = false;
    }

    return hashValue;
}

I suspect there must be a much smarter way to do this? Anyone got any ideas?

Answer 1

I would use java standard library as a first try:

int hash = java.util.Arrays.deepHashCode( board );

Once everything works well, profile your whole app, to check if the hashcode computation is really a performance bottleneck.

Answer 2

If you want to handle this yourself here is one way you could do it.

There are three values for each cell on the board: empty, black, white. That means you can use two bits per cell on the board. And since the board is 8x8 or 64 cells, you can encode the board in two long primitives. Maybe one of them tells you whether a particular cell is empty, and if it's not, the other tells you its color.

You do not even need to convert this representation into a 2D array. You can use bitwise operators on the longs directly in your methods to work with the board.

The hash value could then be the XOR of the two longs, or something like that.