检查 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);

输出：

包含？真实

但它没有利用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));

包含？真实

不过，List<Integer>方法会占用空间，因为它存储的是Integer对象，而不是int基元，后者通常会占用更多空间。

既节省空间又节省时间：开发自定义类

如果以上仍然不够有效——对于绝大多数目的来说都是如此——你可以使用自己的类来计算数字：

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

包含？真实

现在我们几乎有了原始int阵列方法的空间效率和hashCode()的时间效率。

更多选择(谢谢，蓬松(

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

此外，如果我没有错的话，可能有两种基于密钥的解决方案：像

public final class IntArrayKey {
private final int[];
...
}

(遭受可能的阵列突变或防御性阵列克隆(，或类似的东西

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

以保持其通用性。

也许我能想到的另一个解决方案是使用fastutil或Trove而不是List<Integer>(例如。IntList其适当地覆盖CCD_ 13和CCD_。不确定它的价值现在添加所有可能的解决方案(也许还有更多？(。：(

Answer 2

您可以使用TreeSet而不是HashSet，并使用比较器来比较两个数组的内容，而不是两个数组对象的hash代码。然后可以使用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