5 Replies Latest reply: Mar 20, 2011 5:48 AM by 848710 RSS

    Different hashcodes for different-looking array (but the same memory-wise)

    848710
      (I posted something similar here as well, but it's kind of urgent:
      http://www.java-forums.org/advanced-java/40756-hashmap-treating-isomorphic-but-different-objects-same-key.html)

      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.
      Any board layout is represented as an int[8][8]. The HashMap takes as a key a board configuration and is supposed to give back an an object containing information about possible moves.

      But I have a problem. Suppose I have a board (4x4 for legibility):

      Code:
      int[][] board = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};

      And suppose it gives a hashCode of say '1607178090'.

      Then, when I change the board;
      board = {{0,0,0,0},{0,0,0,0},{1,1,1,1},{1,1,1,1}};
      I want the the hashCode to be different, so my hashMap will recognize it as a different board.


      ---

      I tried making a Matrix object and overriding equals and hashCode, but I'm not quite sure what to change. The Java API says the hashCode for arrays is based on the content, though the following code gives back the same hashCode twice. I don't really understand this:
      int[] a1 = {0,1,2};
      System.out.println(a1.getHash());
      a1[0] = 1;
      System.out.println(a1.getHash());




      By the way, my Matrix class is the following:
      import java.util.Arrays;

      public class Matrix {
      public int[][] board;
      public Matrix() {
      }

      public Matrix(int[][] b){
           board=b;
      }

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

      Edited by: 845707 on 19-mrt-2011 2:20
        • 1. Re: Different hashcodes for different-looking array (but the same memory-wise)
          Kayaman
          845707 wrote:
          I don't really understand this:
          int[] a1 = {0,1,2};
          System.out.println(a1.getHash());
          a1[0] = 1;
          System.out.println(a1.getHash());
          Me neither, does array have a method called "getHash();" these days?
          In case you meant hashCode(), what you're calling there is Object's hashCode(), which would stay the same for the object during its lifetime.

          In your example code you're correctly using Arrays.hashCode(), so why did you write an example that doesn't represent your actual code?
          • 2. Re: Different hashcodes for different-looking array (but the same memory-wise)
            796440
            845707 wrote:
            (I posted something similar here as well, but it's kind of urgent:
            Please keep your urgency to yourself. It's not the concern of anybody here.
            http://www.java-forums.org/advanced-java/40756-hashmap-treating-isomorphic-but-different-objects-same-key.html)
            However, it is appreciated that you're up front about your crossposts.

            >
            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.
            Any board layout is represented as an int[8][8]. The HashMap takes as a key a board configuration and is supposed to give back an an object containing information about possible moves.

            But I have a problem. Suppose I have a board (4x4 for legibility):

            Code:
            int[][] board = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};

            And suppose it gives a hashCode of say '1607178090'.

            Then, when I change the board;
            board = {{0,0,0,0},{0,0,0,0},{1,1,1,1},{1,1,1,1}};
            I want the the hashCode to be different, so my hashMap will recognize it as a different board.
            Then you have to remove() the key() and re-put the key/value pair. HashMap has no way of knowing that a key has changed after it was put(). The general rule is: Don't use mutable objects for keys in hash-based Maps or elements in hash-based Collections. If you violate the rule, you must remove/re-add whenever anything that affects hashCode() or equals() changes.

            Additionally, if I understand correctly, you're using an array as a key. I can't imagine a scenario where that would be a good idea. If a key is never equals() to another object, it's a useless key, and since arrays don't override the equals() method, no two distinct array objects can ever return true from equals() even if their elements are identical.

            If you want {1, 2, 3, 4} to be a key that maches another {1, 2, 3, 4}, use Lists.

            I won't read any further or comment on anything else. There's enough here to address for now.
            • 3. Re: Different hashcodes for different-looking array (but the same memory-wise)
              YoungWinston
              845707 wrote:
              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.
              Any board layout is represented as an int[8][8]. The HashMap takes as a key a board configuration and is supposed to give back an an object containing information about possible moves.
              Then my suggestion would be to create a Board class that encapsulates your array, and provide an equals() method that compares the array contents, and a hashCode() method that generates a hashcode based on the array contents. Then your HashMap becomes HashMap<Board>, and you should be hunky-dory.

              Winston
              • 4. Re: Different hashcodes for different-looking array (but the same memory-wise)
                848710
                I find your animosity (first comment) and cockiness (last comment) disconcerting. I don't think you are right though, I put the int[][] in a Matrix-class/object and called deepHashCode instead of hashCode. This seems to work.
                • 5. Re: Different hashcodes for different-looking array (but the same memory-wise)
                  848710
                  This is exactly what I needed YoungWinston, thanks!

                  Kayaman: yes, I made an error. I always mix up hashCode() with the non-existent getHash().