HashMap treating isomorphic but different objects as the same key

[MartyP]

Dear all,

I'm trying to program the game of Reversi on my computer and I represent the game tree as a lookup table using a HashMap.

It looks something like this:

HashMap<int[][], ReversiMove> g_lookupTable;

Any board layout is represented as an int[8][8], and the HashMap is supposed to give back ReversiMove, an obect containing detailed information about possible moves from that lay-out, etc.

But I have a problem. Suppose I have two arrays a1 and a2 that are isomorphic:

int[][] a1 = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
int[][] a2 = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};

Both are 8x8 integer arrays containing only zeroes, but they are different objects.

I would like my HashMap to work for a1 and a2 like it is the same object, so

g_lookupTable.put(a1,something);
g_lookupTable.get(a2);

would yield 'something'

Is it possible to achieve this? Should I change the way my HashMap works?

[masijade]

You would have to write an object that contains the array (a matrix object, essentially) and then override the equals and hashcode methods (see the API docs for Object for more information on that).

[MartyP]

You would have to write an object that contains the array (a matrix object, essentially) and then override the equals and hashcode methods (see the API docs for Object for more information on that).

Well... I told Eclipse to do that but I'm not quite sure what's going on in hashCode().

import java.util.Arrays;

public class Matrix {
    private final int[][] array;
    public Matrix(int col, int row) {
        array = new int[col][row];
    }
    
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.hashCode(array);
		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(array, other.array))
			return false;
		return true;
	}
}

But the equals() method seems to be exactly what I wanted.

[toadaly]

Are you using

HashMap<int[][], ReversiMove> g_lookupTable;

...or are you using

HashMap<Matrix, ReversiMove> g_lookupTable;

You need to use a Matrix as the HashMap key, not an int[][].

[MartyP]

Are you using

HashMap<int[][], ReversiMove> g_lookupTable;

...or are you using

HashMap<Matrix, ReversiMove> g_lookupTable;

You need to use a Matrix as the HashMap key, not an int[][].

Yes, yes, that's what masijade told me. But I was wondering what the difference between the original hashcode (for int[][]) and this is:

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

[masijade]

In that the second one concentrates on the contents of the array rather than on its reference value.

[MartyP]

But it uses Arrays.hashCode(array)... Does that mean that int[][] on itself didn't use Arrays.hashCode(array)? Why would it use the reference value?!
An array is an object just like Matrix is, right?

[MartyP]

Oh by the way, it doesn't work. I hadn't even tested it yet.

The way it is now: I understand the following code should give back different hashCodes for different-looking versions of board and the same for the same-looking.
But it doesn't, it still gives a code seemingly based on the reference value.

import java.util.Arrays;

public class Matrix {
    public int[][] board;
    public Matrix() {
    }
    
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		
		result = prime * result + Arrays.hashCode(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;
	}
}

Do I have to iterate over the array in the equals() method to check it contains the same information or something???

[pbrockway2]

it still gives a code seemingly based on the reference value.

Yes that code gives a hash value based on the identity (reference value) of the elements of the board array.

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;

    [color=blue]System.out.print("Calculating hash code based on " + board.length);
    System.out.println(" elements of the board array");[/color]
    result = prime * result + Arrays.hashCode(board);
    [color=blue]System.out.println("    returning " + result);[/color]
    return result;
}

Have you read the API docs for the particular form of the ARrays.hashCode() you are using?

[MartyP]

Well, the Java API says:

The value returned by this method is the same value that would be obtained by invoking the hashCode method on a List containing a sequence of Integer instances representing the elements of a in the same order. If a is null, this method returns 0.

List:
Returns the hash code value for this list. The hash code of a list is defined to be the result of the following calculation:
int hashCode = 1;
Iterator<E> i = list.iterator();
while (i.hasNext()) {
E obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}

So doesn't that mean that this:

int[] a1 = {0,1,2};
System.out.println(a1.getHash());

would give a different hashcode than

a1[0] = 1;
System.out.println(a1.getHash());

Since the first element changed from 0 to 1?
But when I try it out, a1 has the same hashcode before and after.


In my own code it amounts to this:

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
	    System.out.println("Calculating hash code based on: ");
		result = prime * result + Arrays.hashCode(board);
		for(int c=0;c<board.length;c++){
			for(int r=0;r<board.length;r++){
				System.out.print(""+board[c][r]+"");
			}
			System.out.println();
		}
	    System.out.println("    returning " + result);
		return result;
	}

Output:

Calculating hash code based on: 
00000000
00000000
00000000
00021000
00012000
00000000
00000000
00000000
    returning 1607178090
 (on 1607178090)

Calculating hash code based on: 
00000000
00000000
00000000
00021000
00011100
00000000
00000000
00000000
    returning 1607178090
 (on 1607178090)

I just don't get this.

(I see only now that this is the inverse of my original question; but this is more useful to me now.)

[pbrockway2]

What makes you think you are calling the hashCode(int[] a) method?

My suggestion of printing the length of the array argument you are using was intended to nudge you in the direction of seeing that you are not, in fact, calling this version of the hashCode() method.

[MartyP]

What makes you think you are calling the hashCode(int[] a) method?

My suggestion of printing the length of the array argument you are using was intended to nudge you in the direction of seeing that you are not, in fact, calling this version of the hashCode() method.

Oh, I'm sorry I didn't get that.

The code contains

result = prime * result + Arrays.hashCode(board);

I thought hashCode(int[][] a) would call deepHashCode(int[][] a), since it is a nested array. But it doesn't, I now see in the API.

hashCode

public static int hashCode(Object[] a)
Returns a hash code based on the contents of the specified array. If the array contains other arrays as elements, the hash code is based on their identities rather than their contents. It is therefore acceptable to invoke this method on an array that contains itself as an element, either directly or indirectly through one or more levels of arrays.
For any two arrays a and b such that Arrays.equals(a, b), it is also the case that Arrays.hashCode(a) == Arrays.hashCode(b).

The value returned by this method is equal to the value that would be returned by Arrays.asList(a).hashCode(), unless a is null, in which case 0 is returned.

See Also:
deepHashCode(Object[])

So calling deepHashCode(ar) instead of cashCode(ar) should make it all OK?

[MartyP]

Yes, it works! Thanks for your help!

[pbrockway2]

You're welcome. I'm gvlad you've got it sorted out!