Long runtime/crash 在 hashmap 中使用 int[] 作为键时

Question

我正在学习动态规划的课程：https://youtu.be/oBt53YbR9Kk?t=2330 我发现出于某种原因，如果我将 HashMap 键与 int[] 一起使用，则使用较大的 m 和 n 值将花费很长时间或崩溃。如果我改用字符串形式的键，它会按预期工作。

工作代码

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

代码损坏

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

问题：与仅使用字符串作为键相比，为什么 int[] 键会导致我的代码崩溃？

Answer 1

数组不会覆盖 java.lang.Object 中的 equals() 或 hashCode() 方法，但 java.lang.String class 会。因此，您的 Map 将一直随着新对象的增长而增长，直到由于内存限制而崩溃，即使 Map 中已经有“相等”的数组作为键。但是从java的角度来看，它们并不“相等”。

Answer 2

另外，你还可以使用List作为Map的key，那么不同的List对象相同的元素就被认为是相等的。

用 HashMap<List<Integer>, Long> 声明地图。调用 Arrays.stream(new int[]{1, 2, 3}).boxed().collect(Collectors.toList()) 将 int 数组转换为 List。

Answer 3

还有另一种方法，对于需要时间复制的较大数组特别有意义，将每个数组包装在一个正确实现 equals 和 hashCode 的对象中。您可以使用 java.util.Arrays.equals 和 java.util.Arrays.hashCode 作为这两种方法的核心。

同样，您可以调用 java.util.Arrays.hashCode 将每个数组转换为一个键，当两个原始数组包含相同的值时，该键将正确地“等于”另一个键。

Long runtime/crash 在 hashmap 中使用 int[] 作为键时

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

java

dynamic-programming