java - 如何使 HashMap 以数组为键工作？

Question

我使用布尔数组作为 HashMap 的键。但是问题是当不同的数组作为键传递时，HashMap 无法获取键，尽管元素是相同的。（因为它们是不同的对象）。

我怎样才能使它与数组作为键一起工作？这是代码：

public class main {
public static HashMap<boolean[], Integer> h;


public static void main(String[] args){
    boolean[] a = {false, false};

    h = new HashMap<boolean[], Integer>();
    h.put(a, 1);


    if(h.containsKey(a)) System.out.println("Found a");

    boolean[] t = {false, false};

    if(h.containsKey(t)) System.out.println("Found t");
    else System.out.println("Couldn't find t");

}

}

两个数组a都t包含相同的元素，但 HashMap 不返回任何t.

我如何使它工作？

score 33 · Accepted Answer

你不能这样做。两者t和a将具有不同hashCode()的值，因为该java.lang.Array.hashCode()方法继承自Object，它使用引用来计算哈希码（默认实现）。因此，数组的哈希码是依赖于引用的，这意味着您将获得和的不同哈希码t值a。此外，equals这对这两个数组不起作用，因为这也是基于参考的。

boolean您可以做到这一点的唯一方法是创建一个将数组保留为内部成员的自定义类。然后，您需要覆盖equals并hashCode确保包含具有相同值的数组的实例是相等的并且也具有相同的哈希码。

一个更简单的选择可能是List<Boolean>用作键。根据文档，hashCode()实现List定义为：

int hashCode = 1;
Iterator<E> i = list.iterator();
while (i.hasNext()) {
    E obj = i.next();
    hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}

如您所见，它取决于列表中的值而不是参考，因此这应该适合您。

score 12 · Accepted Answer

不可能对数组执行此操作，因为任何两个不同的数组都不会比较equals，即使它们具有相同的元素。

例如，您需要从容器类进行映射ArrayList<Boolean>（或者简单地说List<Boolean>。也许BitSet会更合适。

score 5 · Accepted Answer

Map实现依赖于密钥equals和hashCode方法。java中的数组是直接扩展的Object，它们使用默认值并且equals只比较。hashCodeObjectidentity

如果我是你，我会创建一个类Key

class Key {
    private final boolean flag1;
    private final boolean flag2;

    public Key(boolean flag1, boolean flag2) {
        this.flag1 = flag1;
        this.flag2 = flag2;
    }

    @Override
    public boolean equals(Object object) {
        if (!(object instanceof Key)) {
            return false;
        }

        Key otherKey = (Key) object;
        return this.flag1 == otherKey.flag1 && this.flag2 == otherKey.flag2;
    }

    @Override
    public int hashCode() {
        int result = 17; // any prime number
        result = 31 * result + Boolean.valueOf(this.flag1).hashCode();
        result = 31 * result + Boolean.valueOf(this.flag2).hashCode();
        return result;
    }
}

之后，您可以将密钥用于Map：

Map<Key, Integer> map = new HashMap<>();

Key firstKey = new Key(false, false);
map.put(firstKey, 1);

Key secondKey = new Key(false, false) // same key, different instance
int result = map.get(secondKey); // --> result will be 1

参考：来自一个字段的 Java 哈希码

score 3 · Accepted Answer

问题

正如其他人所说，Java 数组继承.hashcode()和继承.equals()自 Object，它使用数组或对象地址的哈希值，完全忽略其内容。解决此问题的唯一方法是将数组包装在一个对象中，该对象根据数组的内容实现这些方法。这就是 Joshua Bloch 写第 25 条：“Prefer lists to arrays”的原因之一。Java 提供了几个执行此操作的类，或者您可以编写自己的使用Arrays.hashCode()并Arrays.equals()包含这些方法的正确和有效实现的类。太糟糕了，它们不是默认实现！
只要可行，就对任何基于散列的集合的键使用深度不可修改（或不可变）的类。如果您在将数组（或其他可变对象）存储为哈希表中的键之后对其进行修改，那么它几乎肯定会在该哈希表中的未来.get()或.contains()测试中失败。另请参阅可变哈希映射键是一种危险的做法吗？

具体解决方案

// Also works with primitive:    (boolean... items)
public static List<Boolean> bList(Boolean... items) {
    List<Boolean> mutableList = new ArrayList<>();
    for (Boolean item : items) {
        mutableList.add(item);
    }
    return Collections.unmodifiableList(mutableList);
}

ArrayList根据其内容实现.equals()and （正确且有效），因此each 具有相同的哈希码，并且将等于 each other 。.hashCode()bList(false, false)bList(false, false)
将其包裹起来Collections.unmodifiableList()可以防止修改。

修改您的示例以使用 bList() 只需要更改一些声明和类型签名。它和你原来的一样清晰，几乎一样简短：

public class main {
    public static HashMap<List<Boolean>, Integer> h;

    public static void main(String[] args){
        List<Boolean> a = bList(false, false);

        h = new HashMap<>();
        h.put(a, 1);

        if(h.containsKey(a)) System.out.println("Found a");

        List<Boolean> t = bList(false, false);

        if(h.containsKey(t)) System.out.println("Found t");
        else System.out.println("Couldn't find t");
    }
}

通用解决方案

public <T> List<T> bList(T... items) {
    List<T> mutableList = new ArrayList<>();
    for (T item : items) {
        mutableList.add(item);
    }
    return Collections.unmodifiableList(mutableList);
}

上述解决方案的其余部分没有改变，但这将利用 Java 的内置类型推断来处理任何原语或对象（尽管我建议只使用不可变类）。

图书馆解决方案

而不是bList()使用Google Guava's ImmutableList.of()或我自己的Paguro's vec()或其他提供此类预测试方法的库（加上不可变/不可修改的集合等）。

劣质解决方案

这是我在 2017 年的原始答案。我把它留在这里是因为有人觉得它很有趣，但我认为它是二流的，因为 Java 已经包含 ArrayList 和 Collections.unmodifiableList() 可以解决这个问题。使用 .equals() 和 .hashCode() 方法编写自己的集合包装器比使用内置方法更费力、更容易出错、更难验证，因此更难阅读。

这应该适用于任何类型的数组：

class ArrayHolder<T> {
    private final T[] array;
    @SafeVarargs
    ArrayHolder(T... ts) { array = ts; }
    @Override public int hashCode() { return Arrays.hashCode(array); }
    @Override public boolean equals(Object other) {
        if (array == other) { return true; }
        if (! (other instanceof ArrayHolder) ) {
            return false;
        }
        //noinspection unchecked
        return Arrays.equals(array, ((ArrayHolder) other).array);
    }
}

这是您转换为使用 ArrayHolder 的具体示例：

// boolean[] a = {false, false};
ArrayHolder<Boolean> a = new ArrayHolder<>(false, false);

// h = new HashMap<boolean[], Integer>();
Map<ArrayHolder<Boolean>, Integer> h = new HashMap<>();

h.put(a, 1);

// if(h.containsKey(a)) System.out.println("Found a");
assertTrue(h.containsKey(a));

// boolean[] t = {false, false};
ArrayHolder<Boolean> t = new ArrayHolder<>(false, false);

// if(h.containsKey(t)) System.out.println("Found t");
assertTrue(h.containsKey(t));

assertFalse(h.containsKey(new ArrayHolder<>(true, false)));

我使用了 Java 8，但我认为 Java 7 拥有你需要的一切。我使用TestUtils测试了 hashCode 和 equals 。

score 2 · Accepted Answer

You could create a class that contains the array. Implements the hashCode() and equals() methods for that class, based on values:

public class boolarray {
  boolean array[];

  public boolarray( boolean b[] ) {
     array = b;
  }

  public int hashCode() {
    int hash = 0;
    for (int i = 0; i < array.length; i++)
       if (array[i])
          hash += Math.pow(2, i);
    return hash;
  }

  public boolean equals( Object b ) {
     if (!(b instanceof boolarray))
        return false;
     if ( array.length != ((boolarray)b).array.length )
        return false;
     for (int i = 0; i < array.length; i++ )
        if (array[i] != ((boolarray)b).array[i])
           return false;
     return true;
  }
}

You can then use:

 boolarray a = new boolarray( new boolean[]{ true, true } );
 boolarray b = new boolarray( new boolean[]{ true, true } );
 HashMap<boolarray, Integer> map = new HashMap<boolarray, Integer>();
 map.put(a, 2);
 int c = map.get(b);
 System.out.println(c);

score 1 · Accepted Answer

可能是因为 Array 返回的 equals() 方法的行为与您预期的不同。您应该考虑实现自己的收集并覆盖 equals() 和 hashCode()。

score 1 · Accepted Answer

Map 用于equals()测试您的键是否相同。

该方法在Object测试中的默认实现==，即引用相等。因此，由于您的两个数组不是同一个数组，因此equals始终返回 false。

您需要对Arrays.equals两个数组进行 map 调用以检查是否相等。

您可以创建一个使用的数组包装类，Arrays.equals然后这将按预期工作：

public static final class ArrayHolder<T> {

    private final T[] t;

    public ArrayHolder(T[] t) {
        this.t = t;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 23 * hash + Arrays.hashCode(this.t);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final ArrayHolder<T> other = (ArrayHolder<T>) obj;
        if (!Arrays.equals(this.t, other.t)) {
            return false;
        }
        return true;
    }
}

public static void main(String[] args) {
    final Map<ArrayHolder<Boolean>, Integer> myMap = new HashMap<>();

    myMap.put(new ArrayHolder<>(new Boolean[]{true, true}), 7);
    System.out.println(myMap.get(new ArrayHolder<>(new Boolean[]{true, true})));
}

score 1 · Accepted Answer

boolean[] t;
t = a;

如果您给出这个，而不是boolean[] t = {false, false};，那么您将获得所需的输出。

这是因为将Map存储reference为key，并且在您的情况下，尽管t具有相同的值，但它的引用与a.

因此，当你给予时t=a，它会起作用。

它与此非常相似：-

String a = "ab";
String b = new String("ab");

System.out.println(a==b); // This will give false.

两者a&b持有相同的值，但有不同的引用。因此，当您尝试使用比较参考时==，它会给出false。

但如果你给，a = b;然后试着比较reference，你会得到true。

score 1 · Accepted Answer

您可以使用接受外部散列和比较策略（trove）的库。

class MyHashingStrategy implements HashingStrategy<boolean[]> {

    @Override
    public int computeHashCode(boolean[] pTableau) {
        return Arrays.hashCode(pTableau);
    }

    @Override
    public boolean equals(boolean[] o1, boolean[] o2) {
        return Arrays.equals(o1, o2);
    }
}


Map<boolean[], T> map = new TCustomHashMap<boolean[],T>(new MyHashingStrategy());

java - 如何使 HashMap 以数组为键工作？

9 回答 9

Related

Reference