Как проверить, существует ли массив в 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
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)); }
чтобы он был универсальным.
И, возможно, еще одно решение, о котором я могу думать, использует фасттил или Trove вместо
List<Integer>
(например, IntList который правильно переопределяетequals
иhashCode
). Не уверен, что стоит добавление всех возможных решений (возможно, их больше?) сейчас. :)
Хороший вопрос, @fluffy, спасибо. Вы можете добавить это в свой собственный ответ, если хотите, или я могу добавить его в свой. А пока я упомянул космический штраф, вдохновленный вашим комментарием.
Да, добавьте его, если хотите: лучше (на мой взгляд) один ответ, который охватывает большинство/все случаи. Кроме того, может быть два решения на основе ключей, если я не ошибаюсь: что-то вроде 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, который правильно переопределяет equals
и hashCode
). Не уверен, что стоит добавлять все возможные решения (возможно, их больше?) сейчас. :)
Вы можете использовать TreeSet вместо HashSet с компаратором, который сравнивает содержимое двух массивов вместо хэш-кодов двух объектов массива. Затем вы можете использовать метод 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
Для полноты картины стоит добавить собственное решение класса ключей, поскольку создание такого экземпляра класса ключей может быть дешевле с точки зрения использования памяти (особенно для больших примитивных массивов, которые не обязательно используют целые числа из кеша
Integer
+ это сработает для других «экзотических» случаев, таких какdouble[]
илиchar[]
), и быстрее (особенно для больших коллекций, ориентированных на хэш, где использование линейного поиска снижает производительность).