Что-то вроде «содержит что-нибудь» для набора Java?

307

У меня есть два набора, A и B, одного типа.

Я должен найти, содержит ли A какой-либо элемент из множества B.

Что было бы лучшим способом сделать это без перебора наборов? В библиотеке Set есть contains(object)и containsAll(collection), но нет containsAny(collection).

java Рахул Гарг
источник
4
Вы пытаетесь избежать итерации из соображений эффективности или из-за чистоты кода?
ишавит

Ответы:

527

Не Collections.disjoint(A, B)сработает? Из документации:

Возвращает, trueесли две указанные коллекции не имеют общих элементов.

Таким образом, метод возвращает, falseесли коллекции содержат какие-либо общие элементы.

Frontline
источник
17
Предпочитайте это другим решениям, потому что это не изменяет ни один из наборов или создает новое.
devconsole
7
И является стандартным JRE, и работает с любыми коллекциями, а не только с установленными.
Пьер Генри
4
Я не думаю, что это самое быстрое, оно не будет закорачиваться, когда найден первый элемент пересечения.
Бен Хорнер
7
На самом деле он будет
закорочен,
3
@ Xipo прав. Проверьте grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/…
Луис Мартинес
156

Stream::anyMatch

С Java 8 вы можете использовать Stream::anyMatch.

setA.stream().anyMatch(setB::contains)
GPL
источник
1
Это именно то, что я искал! Спасибо :-) Я также не знал, что вы можете использовать переменные с синтаксисом ::!
Дантистон
1
@blevert, не могли бы вы объяснить, что происходит внутри anyMatch?
Криштиану
8
@Cristiano здесь, anyMatchбудет транслировать все элементы setAи вызывать их setB.contains()все. Если «true» возвращается для любого из элементов, выражение в целом будет иметь значение true. Надеюсь, это помогло.
Алексей Вулай
2
@Cristiano docs.oracle.com/javase/8/docs/api/java/util/stream/…
Луис Мартинес
31

Хороший способ реализовать containsAny для множеств - использовать Guava Sets.intersection () .

containsAnyвернул бы boolean, поэтому вызов выглядит так:

Sets.intersection(set1, set2).isEmpty()

Это возвращает истину, если множества не пересекаются, иначе ложь. Временная сложность этого, вероятно, немного лучше, чем retainAll, потому что вам не нужно делать клонирование, чтобы избежать изменения вашего исходного набора.

CaTalyst.X
источник
3
Единственный недостаток использования этого подхода - вы должны включать библиотеки гуавы. Что, я думаю, не является недостатком, потому что API коллекции Google очень сильны.
Мохаммад Аднан
@DidierL большинство функций утилит Guava Collections, включая эту, возвращают представления структур данных. Таким образом, в этом случае не нужно беспокоиться о «создании набора». Реализация интересно читать здесь, и / или увидеть JavaDoc: google.github.io/guava/releases/21.0/api/docs/com/google/common/...
Chut
@MohammadAdnan Еще одним недостатком является то, что он вычисляет полное пересечение - если set1 и set2 очень большие, это будет намного более ресурсоемким (как с точки зрения процессора, так и с точки зрения памяти), чем просто проверка, имеют ли они какой-либо общий элемент.
Марксама
16

Я использую org.apache.commons.collections.CollectionUtils

CollectionUtils.containsAny(someCollection1, someCollection2)

Вот и все! Возвращает true, если хотя бы один элемент находится в обеих коллекциях.

Прост в использовании, а название функции более наглядно.

Adam111p
источник
5

Используйте retainAll()в интерфейсе Set. Этот метод обеспечивает пересечение элементов, общих в обоих наборах. См. API документы для получения дополнительной информации.

Суреш Кумар
источник
Если цель избежать итерации для эффективности, retainAllвероятно, не поможет. Его реализация в AbstractCollectionитерациях.
ишавит
1
ишавит правильно. Учитывая, что OP ищет, существует ли какой-либо элемент в обоих наборах, надлежащий алгоритм будет иметь время O(1)выполнения в лучшем случае, в то время как retainAllбудет иметь что-то подобное O(N)(это будет зависеть от размера только 1 набора) лучшее время выполнения.
Зейчин
3

Я бы порекомендовал создать HashMapиз набора A, а затем выполнить итерацию по набору B и проверить, есть ли какой-либо элемент B в A. Это будет выполняться во O(|A|+|B|)времени (так как не будет столкновений), тогда как retainAll(Collection<?> c)должно выполняться во O(|A|*|B|)времени.

Zéychin
источник
3

Есть немного грубый способ сделать это. Если и только если набор A содержит некоторый элемент B, чем вызов

A.removeAll(B)

изменит набор А. В этом случае removeAll вернет true (как указано в документации по removeAll ). Но, вероятно, вы не хотите изменять набор A, поэтому вы можете подумать, что будете действовать с копией, вот так:

new HashSet(A).removeAll(B)

и возвращаемое значение будет истинным, если множества не различны, то есть они имеют непустое пересечение.

Также см. Коллекции Apache Commons

PLAP
источник
2

Вы можете использовать метод retainAll и получить пересечение двух ваших множеств.

Артем
источник
В большинстве случаев необходимо сохранить исходный набор, поэтому для retainAllего использования необходимо сделать копию исходного набора. Тогда это более эффективно для использования, HashSetкак предлагает Зейчин .
Петр Пудлак
Это изменение состояния, а не проверка состояния
Бен