Long runtime/crash when using int[] as key in hashmap-CodePudding

I am following this lesson on dynamic programming: https://youtu.be/oBt53YbR9Kk?t=2330 I found that for some reason if I use a HashMap key with int[], using a large m and n value will take a very long time or crash. If I use a key that is a String instead, it works as expected.

Working Code

    public static void main(String[] args) {
        HashMap<String, Long> map = new HashMap<>();
        System.out.println(gridTraveler(18, 18, map));
    }

    /**
     * Grid Traveler problem
     * */
    public static Long gridTraveler(int m, int n, HashMap<String, Long> memo){
        String key = m   ","   n;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        if(m == 1 && n == 1) {
            return 1L;
        }
        if(m == 0 || n == 0){
            return 0L;
        }
        memo.put(key, gridTraveler(m - 1, n, memo)   gridTraveler(m, n - 1, memo));
        return memo.get(key);
    }

Broken Code

    public static void main(String[] args) {
        HashMap<int[], Long> map = new HashMap<>();
        System.out.println(gridTraveler(18, 18, map));
    }

    /**
     * Grid Traveler problem
     * */
    public static Long gridTraveler(int m, int n, HashMap<int[], Long> memo){
        int[] key = new int[]{m,n};
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        if(m == 1 && n == 1) {
            return 1L;
        }
        if(m == 0 || n == 0){
            return 0L;
        }
        memo.put(key, gridTraveler(m - 1, n, memo)   gridTraveler(m, n - 1, memo));
        return memo.get(key);
    }

Question: Why does an int[] key cause my code to crash compared to just using a String as a key?

CodePudding user response：

Arrays do not override the equals() or hashCode() method from java.lang.Object, but the java.lang.String class does. So, your Map will grow with new objects all the time until it crashes due to memory limits, even though there are already "equal" arrays as keys in the Map. But from the point of view of java, they are not "equal".

CodePudding user response：

What's more, you could use List as the key of Map, then different List objects with same elements are considered equal.

Declare the map with HashMap<List<Integer>, Long>. Call Arrays.stream(new int[]{1, 2, 3}).boxed().collect(Collectors.toList()) to convert an int array to a List.

CodePudding user response：

Yet another way, which would make particularly good sense for larger arrays that take time to copy, would be to wrap each array in an object that properly implements equals and hashCode. You could use java.util.Arrays.equals and java.util.Arrays.hashCode as the guts of the two methods.

Similarly, you could just call java.util.Arrays.hashCode to convert each of your arrays to a key that will properly "equal" another key when the two original arrays contained the same values.