Поиск в коллекциях Java

«Есть ли этот элемент в коллекции?» — звучит как один вопрос, но Java отвечает на него полудюжиной разных способов с разными затратами и разными типами возвращаемых значений. Умение выбрать нужный способ превращает горячий цикл продолжительностью 50 миллисекунд в 50-микросекундный. Эта глава — обзор методов поиска в коллекциях, отображениях и статических помощниках класса Collections.

Мысленная модель с учётом стоимости

Стоимость каждого метода поиска определяется используемой коллекцией, а не местом вызова. Выберите правильную коллекцию заранее — и поиск будет почти бесплатным; выберите неправильную — и никакой умный вызов метода не поможет.

Коллекция	`contains` / поиск	Почему
`HashSet`, `LinkedHashSet`, `HashMap.keySet()`	O(1) ожидаемое	Поиск по хэш-бакету
`TreeSet`, `TreeMap.keySet()`	O(log n)	Красно-чёрное дерево
`ArrayList`, `LinkedList`, `Vector`	O(n)	Линейный перебор
Отсортированный `ArrayList` + `Collections.binarySearch`	O(log n)	Бинарный поиск по индексированному списку
`LinkedList` + `Collections.binarySearch`	O(n)	Бинарный поиск требует индексации — O(n) на каждом шаге

Два практических правила:

Если вы часто вызываете contains, используйте Set. Создание HashSet из List и последующие запросы к нему почти всегда быстрее, чем list.contains в цикле.
Если данные отсортированы и индексированы, используйте Collections.binarySearch. Это окупается примерно после 30 элементов на большинстве JVM.

`Collection.contains(o)`

Этот метод есть в каждой Collection. Семантика основана на равенстве:

boolean has = list.contains("alpha");        // uses .equals

Для List это линейный перебор — O(n). Для HashSet — поиск по хэш-бакету — O(1) ожидаемое. Для TreeSet — обход дерева — O(log n). Сигнатура метода одинакова; стоимость — нет.

null допускается (метод возвращает true, если коллекция содержит элемент null), если только коллекция не отвергает null явно — как TreeSet с естественным упорядочиванием, EnumSet, ConcurrentHashMap.keySet().

`List.indexOf` и `lastIndexOf`

Списки поддерживают не только ответ «да/нет» — они возвращают позицию:

int firstA = list.indexOf("alpha");          // -1 if absent
int lastA  = list.lastIndexOf("alpha");

Линейный перебор от начала (или с конца). Для ArrayList<String> из тысячи элементов это нормально. Для миллиона — создайте Map<String, Integer> один раз и запрашивайте его.

`Map.containsKey`, `containsValue`, `get`, `getOrDefault`

Методы поиска, специфичные для отображений, чётко разделяются:

map.containsKey("alpha");                    // O(1) for HashMap, O(log n) for TreeMap
map.get("alpha");                             // returns the value or null
map.getOrDefault("alpha", 0);                 // returns the value or your default
map.containsValue("v");                       // O(n) — scans every entry

containsValue — это ловушка. Он перебирает все записи каждый раз. Если вы вызываете его больше одного раза, создайте обратное отображение (Map<V, K>) или Set<V> значений один раз и запрашивайте его.

getOrDefault — небольшой, но важный сдвиг в подходе: он заменяет старый идиом Integer n = map.get(k); if (n == null) n = 0; одной строкой, и значение по умолчанию используется только при отсутствии ключа — не когда значение равно null. (Для «отсутствует или null» используйте Objects.requireNonNullElse(map.get(k), 0).)

`Collections.binarySearch`

Бинарный поиск по отсортированному списку:

List<String> sorted = new ArrayList<>(...);
Collections.sort(sorted);
int hit  = Collections.binarySearch(sorted, "delta");      // 2  (some index)
int miss = Collections.binarySearch(sorted, "zeta");       // negative

Два предусловия:

Список должен быть отсортирован в том порядке, в котором будет выполняться поиск. Если сортировка выполнялась с компаратором, передайте тот же компаратор в binarySearch. Несовпадающие порядки дают бессмысленные результаты (без исключений).
Список должен быть индексированным (ArrayList, а не LinkedList). На связном списке бинарный поиск работает за O(n log n) — хуже линейного.

Возвращаемое значение кодирует и «найдено», и «куда вставить»:

int i = Collections.binarySearch(sorted, key);
if (i >= 0) {
  // key is at index i
} else {
  int insertAt = -i - 1;
  sorted.add(insertAt, key);             // keeps the list sorted
}

Арифметика -i - 1 — это способ, которым каждая процедура «найти или вставить» в JDK обрабатывает промах. Стоит запомнить.

`Collections.frequency` и `disjoint`

Два вспомогательных метода, обёртывающих распространённые паттерны поиска:

int n = Collections.frequency(coll, "alpha");        // how many times "alpha" appears
boolean none = Collections.disjoint(a, b);           // no element of a is in b

frequency работает за O(n). Для повторных запросов с разными целями подсчитайте значения один раз с помощью stream в Map<T, Long>.

disjoint реализован умно: он перебирает меньшую коллекцию и вызывает contains на большей, если та является Set, меняя аргументы местами под капотом. Поэтому Collections.disjoint(largeList, smallSet) работает за O(largeList) — и быстрее, чем написанная вручную реализация.

Поиск через Stream

Stream обрабатывают «найти первый подходящий элемент» с помощью findFirst / findAny, а «есть ли хоть одно совпадение» — с помощью anyMatch / allMatch / noneMatch:

Optional<Person> match = people.stream()
    .filter(p -> p.age() >= 18 && p.name().startsWith("A"))
    .findFirst();

boolean any = people.stream().anyMatch(p -> p.age() >= 65);
boolean all = people.stream().allMatch(p -> p.age() >= 0);
boolean non = people.stream().noneMatch(p -> p.age() < 0);

Stream выполняют сокращённое вычисление для findFirst и anyMatch — они останавливаются, как только находят совпадение. Это самый чистый ответ для поиска по предикату. Они не быстрее contains при поиске по равенству на правильной структуре данных — HashSet.contains всегда обгонит stream().anyMatch(x -> x.equals(target)).

Optional<T> заслуживает отдельного внимания (у него есть глава в части про функциональное программирование). Пока: findFirst().isPresent() — самое чистое выражение «нашли ли мы что-нибудь?» для предиката.

`LinkedHashSet` для «contains и порядок»

Распространённый паттерн: вам нужен быстрый contains и итерация в порядке вставки. LinkedHashSet — это решение:

LinkedHashSet<String> seen = new LinkedHashSet<>();
for (String line : input) {
  if (seen.add(line)) System.out.println(line);    // print first occurrences only
}

add возвращает true только в первый раз. Множество отвергает дубликаты за O(1) и сохраняет порядок вставки для итерации. Это правильный инструмент для «дедуплицировать с сохранением порядка» — ни HashSet (теряет порядок), ни ArrayList (медленный contains) не справятся так же хорошо.

Практический пример: сравнение пяти стратегий поиска на одних данных

Программа ниже помещает 100 000 строк в разные коллекции и измеряет время пяти стратегий поиска для 1 000 случайных запросов: ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch на отсортированном списке и stream().anyMatch.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class SearchingShowcase {
  public static void main(String[] args) {
    int N = 100_000;
    int Q = 1_000;
    List<String> data = new ArrayList<>(N);
    for (int i = 0; i < N; i++) data.add("k" + i);

// Build the same data in several shapes
    HashSet<String>   asHash   = new HashSet<>(data);
    TreeSet<String>   asTree   = new TreeSet<>(data);
    List<String>      sortedAL = new ArrayList<>(data);
    Collections.sort(sortedAL);

// Pick Q random keys to look up
    Random rng = new Random(7);
    List<String> queries = IntStream.range(0, Q)
        .mapToObj(i -> "k" + rng.nextInt(N))
        .toList();

long t1 = System.nanoTime();
    int hits1 = 0;
    for (String q : queries) if (data.contains(q)) hits1++;
    long durList = System.nanoTime() - t1;

long t2 = System.nanoTime();
    int hits2 = 0;
    for (String q : queries) if (asHash.contains(q)) hits2++;
    long durHash = System.nanoTime() - t2;

long t3 = System.nanoTime();
    int hits3 = 0;
    for (String q : queries) if (asTree.contains(q)) hits3++;
    long durTree = System.nanoTime() - t3;

long t4 = System.nanoTime();
    int hits4 = 0;
    for (String q : queries) if (Collections.binarySearch(sortedAL, q) >= 0) hits4++;
    long durBin = System.nanoTime() - t4;

long t5 = System.nanoTime();
    int hits5 = 0;
    for (String q : queries) if (data.stream().anyMatch(q::equals)) hits5++;
    long durStream = System.nanoTime() - t5;

System.out.println("strategy             hits   time (ms)");
    System.out.println("-----------------------------------");
    System.out.printf("ArrayList.contains  %5d   %d%n", hits1, durList   / 1_000_000);
    System.out.printf("HashSet.contains    %5d   %d%n", hits2, durHash   / 1_000_000);
    System.out.printf("TreeSet.contains    %5d   %d%n", hits3, durTree   / 1_000_000);
    System.out.printf("binarySearch (AL)   %5d   %d%n", hits4, durBin    / 1_000_000);
    System.out.printf("stream.anyMatch     %5d   %d%n", hits5, durStream / 1_000_000);

// --- The missing-key arithmetic: -i - 1 is the insertion point ---
    int miss = Collections.binarySearch(sortedAL, "zzz");
    int insertAt = -miss - 1;
    System.out.println("\nbinarySearch('zzz') = " + miss
        + "   insertAt = " + insertAt
        + "   list size = " + sortedAL.size() + "   (would append at end)");
  }
}

Что стоит вынести из запуска:

HashSet.contains и Collections.binarySearch на отсортированном ArrayList значительно быстрее ArrayList.contains для повторных запросов. Хэш-таблица побеждает при «любом равенстве», бинарный поиск — когда данные нужно держать отсортированными и по другим причинам.
TreeSet.contains совсем рядом, но не бесплатен — каждый запрос проходит по дереву глубиной ~log₂(100 000) ≈ 17 с промахами кэша для указателей дерева.
stream().anyMatch для поиска по равенству — худший вариант здесь: то же O(n), что и list.contains, но с дополнительными накладными расходами на аллокацию при каждом запросе. Используйте его для предикатов, а не для простого равенства по списку.
Вызов с отсутствующим ключом вернул отрицательное значение, а -i - 1 дало индекс, куда вставить "zzz", чтобы список остался отсортированным. Это та же конвенция, которую используют TreeMap.subMap и Arrays.binarySearch.

Что дальше

Вы теперь рассмотрели итерацию, упорядочивание, сортировку и поиск — четыре механических операции, ради которых существует collections framework. Последняя глава этой части посвящена современной истории о том, чего ни одна из них не касалась: неизменяемости. Java Unmodifiable Collections охватывает List.of, Set.of, Map.of и обёртки Collections.unmodifiable* — когда каждый из них является правильным выбором и почему паттерн «защитной копии», который раньше занимал четыре строки, теперь умещается в одну.

Практика

Вы вызываете `Collections.binarySearch(sortedList, key)` и результат равен `-5`. По какому индексу нужно вставить `key`, чтобы список остался отсортированным?

`4` — при промахе точка вставки равна `-result - 1``-5` — коллекции Java поддерживают отрицательные индексы для вставок при бинарном поиске`5` — абсолютная величина отрицательного результата является точкой вставки`0` — отрицательный результат означает, что список не отсортирован и поиск прервался до нахождения позиции

Мысленная модель с учётом стоимости

Collection.contains(o)

List.indexOf и lastIndexOf

Map.containsKey, containsValue, get, getOrDefault

Collections.binarySearch

Collections.frequency и disjoint