CODEWITHSUNDEEP
javaarraysalgorithm
krystah
krystah

Reputation: 3733

Java: Implementing hashCode() to ensure permutations of an int array always returns same hash

I am trying to make my hashCode()-implementation return the same hashCode for all permutations of an int-array.

Requirements:

I have already written the functions to provide me with all the permutations (rotations and reflections) of the arrays, but I don't really understand how I can make them all return the same code, since there are no object properties to base the code upon.

What I've tried so far is gathering the Arrays.hashCode() of all the permutations, summing them up into a long, dividing them by the number of permutations and returning the result as an int.

While this doesn't feel like a good solution (using the median is quite vague, thus might result in collisions), it's not working anyway. I've found objects that are not among the valid permutations to return the same hashCode.

Example 1: Reflection
These two are equal because arr2 is a reflection of arr1.

int[] arr1 = {0,2,4,1,3}     int[] arr2 = {4,2,0,3,1}   
[X 0 0 0 0]                  [0 0 0 0 X]
[0 0 X 0 0]                  [0 0 X 0 0]
[0 0 0 0 X]                  [X 0 0 0 0]
[0 X 0 0 0]                  [0 0 0 X 0]
[0 0 0 X 0]                  [0 X 0 0 0]


Example 2: Rotation
These two are permutations of each other because arr2 is a rotated arr1.

int[] arr1 = {0,2,4,1,3}     int[] arr2 = {4,1,3,0,2}   
[X 0 0 0 0]                  [0 0 0 0 X]
[0 0 X 0 0]                  [0 X 0 0 0]
[0 0 0 0 X]                  [0 0 0 X 0]
[0 X 0 0 0]                  [X 0 0 0 0]
[0 0 0 X 0]                  [0 0 X 0 0]

Q: How can I implement a hashCode()-function to return the same hash for every array-object that is a permutation of one another, one that would return the same hashCode for all of the above examples?

Update:
The reason I cannot sort and compare the arrays is that all arrays that will ever be compared will all contain the values 0..n-1. The reason for this is that the index represents the chessboard row, while the value represents the column at which the queen is placed. (See n queens puzzle if you're interested).
Hence, I am unable to calculate the hashcode by sorting first. Any other ideas?

Upvotes: 0

Views: 881

Answers (5)

Alex
Alex

Reputation: 13951

Based on your description, it sounds like you're doing a brute-force solution to the N-queens problem, whereby you generate every possible position of the queens on the board, eliminate reflections/rotations so you're left with all unique board layouts, and then search for acceptable layouts. As mentioned in the other answers, you cannot rely on hashCode alone for duplicate elimination, because even a well-written hash function has the possibility of collisions.

Instead, I'd suggest defining a canonical layout for a given equivalence set of rotations/reflections. One likely approach would be to define a sort ordering for your layouts, doing a pairwise comparison of elements, until you find an unequal position. The canonical representation for a given layout would be the layout with the lowest ordering.

Then, as you generate your layouts, the first thing you do is get the canonical representation of that layout, and only proceed if you've not yet seen the canonical version. For instance:

 public class Chessboard implements Comparable<Chessboard> {

    private int[] rows;

    public boolean equals(Object other) {
      return other != null && 
             other instanceof Chessboard && 
             Arrays.equals(rows, other.rows);
    }

    public int hashCode() {
       return Arrays.hashCode(rows);
    }

    public int compareTo(Chessboard other) {
       if (rows.length != other.rows.length) {
          return rows.length - other.rows.length;
       }
       for (int i = 0; i < rows.length; i++) {
          int c = rows[i] - other.rows[i];
          if (c != 0) return c;
       }
       return 0;
    }

    public List<Chessboard> getPermutations() {
       /* Your permutations code here. */
    }

    public Chessboard getCanonicalLayout() {
       List<Chessboard> permutations = getPermutations();
       Collections.sort(permutations);
       return permutations.get(0);
    }

    public static void main(String[] args) {
       Set<Chessboard> checked = new HashSet<Chessboard>();
       for (Chessboard b : getAllLayouts()) {
          Chessboard c = b.getCanonicalLayout();
          if (checked.contains(c)) {
             continue;
          }
          checked.add(c);
          if (isSolution(c)) {
             System.out.println("Found a solution: " + c);
          }
       }
    }
 }

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 134005

The simplest way to do it would be to sum all the values in the array and then use a bit mixer to spread the bits in the result. The sum of all the values will be the same regardless of the order, so you're guaranteed that any permutation of the array will result in the same value.

For example:

int hash = 0;
for (int i = 0; i < array.length; ++i)
{
    hash += array[i];
}

// See link below for reference
hash ^= (hash >>> 20) ^ (hash >>> 12);
return h ^ (hash >>> 7) ^ (hash >>> 4);

I got the bit mixer code from http://burtleburtle.net/bob/hash/integer.html. That page is full of good information that you probably want to know.

You might also consider working in the array length if it's different among the arrays you'll be comparing. You could also multiply the result by the highest (or lowest) value in the array, etc. Anything that would help you differentiate.

Upvotes: 2

JB Nizet
JB Nizet

Reputation: 691775

You could simply sort the array, and then use Arrays.hashCode() to compute the hashCode.

Your collection looks like a Bag, or MultiSet. Several libraries have implementations for such a data structure. Guava for example.

Upvotes: 3

Henry
Henry

Reputation: 43738

Sort the arrays before you calculate the hash or compare them within equals.

Upvotes: 1

rgettman
rgettman

Reputation: 178263

Create a class that wraps your array.

The hashCode method needs to perform an operation that is commutative, so that different permutations have the same hash code. Compute a hash code that is the sum of the elements in the array. The sum will not change if the order changes.

You should override equals also.

Upvotes: 1

Related Questions