Java中如何使用数组作为哈希表的键？

Question

我有一个执行一些计算的函数。它接受一个整数数组，并根据传递给它的整数数组的内容返回一个整数。

由于我的应用程序正在进行数百个这些计算，我正在尝试设置一种方法来将这些计算结果存储在哈希映射中，这样它就不必重新计算最近已经完成的计算。然而，要做到这一点，我需要使用整数数组作为哈希映射的键。

目前，这将打印大小2，我希望它打印大小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());

如何实现这一目标最佳？我可以创建一个方法来将数组转换为某种字符串，以编码数组数据，但我认为这不是最好的解决方案。

- user11406

---

你可以将 List 存储在哈希映射中。 - khelwood

你可以使用任何对象作为哈希映射的键，为了你的目的，你可以使用List<Integer>代替int数组。 - beresfordt

可以使用List或者将数组包装在一个简单的类中，重写equals()/hashCode()方法；参见Arrays类。 - fge

你应该看一下Trove库。它支持原始集合、映射和自定义哈希策略。 - Clashsoft

大家对于 HashSet 有什么看法？ - Kick Buttowski

可能是Can a java array be used as a HashMap key的重复问题。 - Raedwald

Answer 1

它当前输出2是因为这两个数组具有不同的hashCode，尽管它们具有相同的元素，但对于设置目的而言，它们并不相同。您应该创建自己的对象，其中包含Object中的一个数组变量。然后，它将覆盖equals和hashCode方法，以便基于数组中的值来确定值是否相同。

例如：

 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] ...

        }
 }

- Gregory Basior

---

дҪ еҸҜд»ҘдҪҝз”ЁArrays.hashCode()е’ҢArrays.equals()жқҘзј–еҶҷдҪ зҡ„дёӨдёӘеҮҪж•°гҖӮ - Pham Trung

由于某些原因，我认为这个解决方案行不通。首先，根据作者的问题，有数百个数组需要处理。这个解决方案将为每个数组创建一个对象，这可能会对内存造成压力（如果涉及大量不同的数组），并最终导致程序崩溃。其次，在对象博客中高效访问数组hashCode将会是一个问题。第三，该解决方案没有提供一种存储数组计算结果的方法。那么现在怎么办？ - Sigismundus

Answer 2

使用Apache Commons StringUtils.join() 方法创建唯一的数组键。它以数组作为参数，并在每个元素上调用toString()方法以获取每个元素的字符串表示形式。然后，如果指定了分隔符，则将每个元素的字符串表示形式连接成一个字符串并在其中加入分隔符：

import org.apache.commons.lang3.StringUtils;

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

生成：

1-2-3

- Sigismundus

Answer 3

正如其他人建议的那样，您应该创建一个包装数组并以一致的方式实现hashCode()和equals()的类。

其他答案要么建议将您的int[]数组转换为String，要么指示您迭代它以计算哈希值或检查相等性。

我建议您使用Java的Arrays实用程序类来高效地计算基于数组的哈希值并检查数组的相等性：

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

然后，在你的地图中使用它：

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

注意：这个 Key 的实现会考虑数组元素的顺序，也就是说，如果用两个不同顺序的数组构造出来的 Key 是不同的：

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

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

k1.equals(k2); // false!

如果你想让两个Key对象在其数组元素顺序不同的情况下相等，你应该在Key类的构造函数中将int[]数组转换为HashSet，然后通过委托Key的equals()和hashCode()方法来实现它们在HashSet中的对应实现。

- fps

Answer 4

我会创建一个特定的数组键，然后将该键和计算出的结果存储在缓存中：

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

这段代码输出 Size: 1

- MaxZoom

---

Gregory Basior的回答更偏向于Java。 - m0skit0

这不正确，因为两个不同数组的hashCode可能产生相同的值。这就是使用键的equals操作来区分差异的地方，但是在这种方法中无法提供自定义equals操作。 - Solubris

@Solubris 只要两个数组的内容相同，产生相同的哈希值是完全可以的。请参阅文档获取更多详细信息。 - MaxZoom

@MaxXoom 我说过，两个不同的数组可能具有相同的哈希码，这是因为可以使用数组中元素的值来分离键，但由于只使用哈希码作为键，所以数组的元素对于任何哈希查找哈希映射都不可用。 - Solubris

@Solubris，你能给出一个支持你理论的代码示例吗？ - MaxZoom

请参考以下答案，了解哈希码冲突的示例：https://dev59.com/enM_5IYBdhLWcg3wcCnc - Solubris