Results 1 to 14 of 14
  1. #1
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default HashMap treating isomorphic but different objects as the same key

    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:
    Java Code:
    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:

    Java Code:
    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

    Java Code:
    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?
    Last edited by MartyP; 03-17-2011 at 07:36 PM. Reason: spelling errors

  2. #2
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

    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).

  3. #3
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by masijade View Post
    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().
    Java Code:
    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.
    Last edited by MartyP; 03-18-2011 at 06:18 PM. Reason: oops

  4. #4
    toadaly is offline Senior Member
    Join Date
    Jan 2009
    Posts
    671
    Rep Power
    6

    Default

    Are you using

    Java Code:
    HashMap<int[][], ReversiMove> g_lookupTable;
    ...or are you using

    Java Code:
    HashMap<Matrix, ReversiMove> g_lookupTable;
    You need to use a Matrix as the HashMap key, not an int[][].

  5. #5
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by toadaly View Post
    Are you using

    Java Code:
    HashMap<int[][], ReversiMove> g_lookupTable;
    ...or are you using

    Java Code:
    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:

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

  6. #6
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

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

  7. #7
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    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?

  8. #8
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    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.
    Java Code:
    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???
    Last edited by MartyP; 03-18-2011 at 10:27 PM.

  9. #9
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

    Java Code:
    @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?

  10. #10
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    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:
    Java Code:
    int[] a1 = {0,1,2};
    System.out.println(a1.getHash());
    would give a different hashcode than
    Java Code:
    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:
    Java Code:
    	@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:
    Java Code:
    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.)
    Last edited by MartyP; 03-19-2011 at 08:47 AM.

  11. #11
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

  12. #12
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    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
    Java Code:
    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?

  13. #13
    MartyP is offline Member
    Join Date
    Mar 2011
    Posts
    10
    Rep Power
    0

    Default

    Yes, it works! Thanks for your help!

  14. #14
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

Similar Threads

  1. Replies: 1
    Last Post: 02-02-2011, 06:11 PM
  2. Replies: 2
    Last Post: 06-22-2010, 04:29 AM
  3. Replies: 7
    Last Post: 12-08-2009, 07:17 PM
  4. Replies: 1
    Last Post: 03-04-2009, 06:14 PM
  5. what is hashmap
    By gabriel in forum New To Java
    Replies: 5
    Last Post: 08-03-2007, 01:23 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •