检查 HashSet<int[]> 中是否存在数组

Question

如何检查 HashSet 中是否存在数组？

例如：

int[] a = new int[]{0, 0};

HashSet<int[]> set = new HashSet<>();
set.add(a);

然后：

int[] b = new int[]{0, 0};

set.contains(b); // ===> true

Answer 1

使用数组

    int[] a = new int[] { 0, 0 };
    HashSet<int[]> set = new HashSet<>();
    set.add(a);

    int[] b = new int[] { 0, 0 };
    
    boolean contains = set.stream().anyMatch(c -> Arrays.equals(c, b));
    
    System.out.println("Contains? " + contains);

输出：

Contains? true

虽然它没有利用 HashSet 的快速查找。如评论中所述，这是不可能的，因为数组的 equals 和 hashCode 不认为包含相同顺序的相同数字的数组相等。一个数组只被认为等于它自己。因此，我们需要对集合进行线性搜索，以找到包含相同数字的数组（如果有的话）。我正在为此使用流管道。您也可以使用循环。

更快：使用列表

要利用 HashSet 中的快速查找，您可以使用列表而不是数组：

    List<Integer> a = List.of(0, 0);
    HashSet<List<Integer>> set = new HashSet<>();
    set.add(a);

    List<Integer> b = List.of(0, 0);
    
    System.out.println("Contains? " + set.contains(b));

Contains? true

List<Integer> 方法有 space 惩罚，但是，因为它存储 Integer 对象而不是 int 原语，后者通常占用更多 space.

既space又省时：开发自定义class

如果以上方法仍然不够有效——这是为了绝大多数目的——你可以使用你自己的 class 作为数字：

public class IntArray {

    int[] elements;
    
    public IntArray(int... elements) {
        // Make a defensive copy to shield from subsequent modifications of the original array
        this.elements = Arrays.copyOf(elements, elements.length);
    }

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

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        IntArray other = (IntArray) obj;
        return Arrays.equals(elements, other.elements);
    }

}

这将允许：

    IntArray a = new IntArray(0, 0);
    HashSet<IntArray> set = new HashSet<>();
    set.add(a);

    IntArray b = new IntArray(0, 0);
    
    System.out.println("Contains? " + set.contains(b));

Contains? true

现在我们几乎拥有原始 int 数组方法的 space 效率，以及 hashCode().

的时间效率

更多选项（谢谢，蓬松）

作为评论中的蓬松注释，还有更多选择，您可能需要自己研究一些。我在这里引用评论：

Also, there can be two key-based solutions if I'm not wrong: something like
public final class IntArrayKey {
    private final int[];
    ...
}
(suffers from possible array mutation or defensive array cloning), or something like
public final class Key<T> {
    private final Predicate<T> equals;
    private final IntSupplier hashCode;
    public static Key<int[]> of(final int[] array) {
        return new Key<>(that -> Arrays.equals(array, that), () -> Arrays.hashCode(array));
    }
to keep it generic.

And probably one more solution I can think of is using fastutil or Trove instead of List<Integer> (e.g. IntList that overrides equals and hashCode properly). Not sure it worth adding all possible solutions (perhaps there are more?) now. :)

Answer 2

您可以使用TreeSet instead of HashSet with a comparator that compares the contents of two arrays instead of the hash codes of two array objects. Then you can use TreeSet.contains方法如下：

int[] a = {0, 0};
int[] b = {0, 0};
int[] c = {0, 0};

HashSet<int[]> hashSet = new HashSet<>();
TreeSet<int[]> treeSet = new TreeSet<>(Arrays::compare);

hashSet.addAll(List.of(a, b, c));
treeSet.addAll(List.of(a, b));

System.out.println(hashSet.size()); // 3
System.out.println(treeSet.size()); // 1

System.out.println(treeSet.contains(a)); // true
System.out.println(treeSet.contains(b)); // true
System.out.println(treeSet.contains(c)); // true

检查 HashSet<int[]> 中是否存在数组

Check if an array exists in a HashSet<int[]>

java

arrays

collections

contains

hashset

使用数组

更快：使用列表

既space又省时：开发自定义class

更多选项（谢谢，蓬松）