Using an array as a hash key in Java?

Question

I have a function that does some calculations. It accepts a int array and returns an integer based on the contents of the int array that's passed to it.

As my application is doing hundreds of theses calculations I'm trying to set up a way to store those calculation results in a hashmap so it don't have to recalculate the calculation it already did recently. To do this though I'd need to use the int arrays as my keys to the hashmap.

At the moment this is printing size 2, I want it to be printing size 1:

LinkedHashMap hashmap = new LinkedHashMap();

int test[] = {1,2,3};
int test2[] = {1,2,3};

hashmap.put(test, 1);
hashmap.put(test2, 1);

System.out.println("Size: "+hashmap.size());

What's the best way to achieve this? I could create a method to convert the arrays to some kind of string encoding the arrays data but I don't think that would be the best solution.

Answer 1

It is currently printing 2 because they are two different arrays with two different hashCodes, so although they have the same elements, they are not the same for the purposes of a set. You should create your own object which has an array as a variable inside of the Object. Then it will override the equals and hashCode method so that the value will be the same based on the values in the array.

e.g.:

 public class MyClass
 {
        private int[] array;

       public boolean equals(Object o)
       {
           if(! (o instance of MyClass) ) return false;
           //loop through the arrays to see they are equal
         }

        public int hashCode()
       {  
           //loop through the array and return a number that is based off of the values in the array such as array[0] ^ array[1] + array[2] * array[3] / array[4] ...

        }
 }

Answer 2

Use Apache commons StringUtils.join() method to create unique array key. It takes an array as a parameter and calls toString() on each element to get each elements string representation. Each elements string representation is then joined into one string with a separator in between if one is specified:

import org.apache.commons.lang3.StringUtils;

int[] a = {1, 2, 3}
String key= StringUtils.join(a, '-');
System.out.println(key);

Produces:

1-2-3

Answer 3

As others have suggested, you should create a class that wraps the array and implements hashCode() and equals() in a consistent way.

Other answers either suggest to convert your int[] array into a String or indicate you should iterate over it to calculate a hash value or check for equality.

I suggest you use Java's Arrays utility class to efficiently calculate an array-based hash value and check for array equality:

public class Key {

    private final int[] values;

    public Key(int[] values) {
        this.values = values;
    }

    @Override
    public boolean equals(Object another) {
        if (another == this) {
            return true;
        }
        if (another == null) {
            return false;
        }
        if (another.getClass() != this.getClass()) {
            return false;
        }
        Key key = (Key) another;
        return Arrays.equals(this.values, key.values);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(this.values);
    }
}

Then, use it in your map:

Map<Key, Integer> map = new LinkedHashMap<>(); // preserve insertion order?

int test[] = {1, 2, 3};
int test2[] = {1, 2, 3};

Key key = new Key(test);
Key key2 = new Key(test2);

map.put(key, 1);
map.put(key2, 1);

map.size(); // 1

Note: This implementation of Key takes the array's elements order into account, meaning that two Keys will be different if constructed from two arrays with the same elements in different order:

int[] v1 = {1, 2, 3};
int[] v2 = {2, 1, 3};

Key k1 = new Key(v1);
Key k2 = new Key(v2);

k1.equals(k2); // false!

If you want two Keys to be equal despite their array's elements order, you should turn the int[] array into a HashSet in the Key class's constructor and then implement Key's equals() and hashCode() methods by delegating to their respective implementations in the HashSet.

Answer 4

I would create array specific key, and then store in the cache that key and the calculated result:

public static void main() {
   Map<String, Integer> hashmap = new HashMap<>();
   int[] arr1 = {1, 2, 3};
   int[] arr2 = {1, 2, 3};
   hashmap.put(Arrays.hashCode(arr1), 1);
   hashmap.put(Arrays.hashCode(arr2), 1);
   System.out.println("Size: "+hashmap.size());
}

The code prints Size: 1