Проверить, существует ли массив в HashSet<int[]>

Как проверить, существует ли массив в 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
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
0
2 138
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Использование массивов

    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). Не уверен, что стоит добавление всех возможных решений (возможно, их больше?) сейчас. :)

Для полноты картины стоит добавить собственное решение класса ключей, поскольку создание такого экземпляра класса ключей может быть дешевле с точки зрения использования памяти (особенно для больших примитивных массивов, которые не обязательно используют целые числа из кеша Integer + это сработает для других «экзотических» случаев, таких как double[] или char[]), и быстрее (особенно для больших коллекций, ориентированных на хэш, где использование линейного поиска снижает производительность).

terrorrussia-keeps-killing 26.12.2020 09:53

Хороший вопрос, @fluffy, спасибо. Вы можете добавить это в свой собственный ответ, если хотите, или я могу добавить его в свой. А пока я упомянул космический штраф, вдохновленный вашим комментарием.

Ole V.V. 26.12.2020 09:58

Да, добавьте его, если хотите: лучше (на мой взгляд) один ответ, который охватывает большинство/все случаи. Кроме того, может быть два решения на основе ключей, если я не ошибаюсь: что-то вроде 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)); }, чтобы сохранить его общим.

terrorrussia-keeps-killing 26.12.2020 10:11

И, вероятно, еще одно решение, которое я могу придумать, — это использовать fastutil или Trove вместо List<Integer> (например, IntList, который правильно переопределяет equals и hashCode). Не уверен, что стоит добавлять все возможные решения (возможно, их больше?) сейчас. :)

terrorrussia-keeps-killing 26.12.2020 10:13

Вы можете использовать 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

Другие вопросы по теме