Pesquisando Coleções Java

"Este elemento está na coleção?" parece uma única pergunta, mas o Java a responde de meia dúzia de maneiras diferentes, com custos distintos e tipos de retorno distintos. Saber qual usar transforma um loop crítico de 50 milissegundos em um de 50 microssegundos. Este capítulo é um tour pelos métodos de pesquisa em coleções, pelos mapas que os envolvem e pelos auxiliares estáticos de Collections.

O modelo mental orientado a custo

O custo de cada método de pesquisa é determinado pela coleção subjacente, não pelo ponto de chamada. Escolha a coleção certa desde o início e suas pesquisas serão eficientes; escolha a errada e nenhuma chamada de método inteligente vai te salvar.

Duas regras gerais:

1. Se você usa contains com frequência, use um Set. Construir um HashSet a partir de uma List e consultá-lo quase sempre é mais rápido do que list.contains em um loop.
2. Se os dados estão ordenados e indexados, use Collections.binarySearch. Compensa a partir de aproximadamente 30 elementos na maioria das JVMs.

Collection.contains(o)

Toda Collection o possui. A semântica é baseada em igualdade:

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

Para uma List, isso é uma varredura linear — O(n). Para um HashSet, é uma busca em bucket de hash — O(1) esperado. Para um TreeSet, é uma travessia de árvore O(log n). A assinatura do método é a mesma; o custo não é.

null é permitido (o método retorna se a coleção contém algum elemento null), a menos que a coleção rejeite null diretamente — TreeSet com ordenação natural, EnumSet, ConcurrentHashMap.keySet().

List.indexOf e lastIndexOf

Listas suportam mais do que apenas "sim/não" — elas retornam a posição:

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

Varredura linear a partir do início (ou do fim). Para um ArrayList<String> com mil elementos, isso funciona bem. Para um milhão, construa um Map<String, Integer> uma vez e consulte-o.

Map.containsKey, containsValue, get, getOrDefault

Os métodos de pesquisa específicos de mapa se dividem claramente:

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 é a armadilha. Ele percorre cada entrada toda vez. Se você se pegar chamando-o mais de uma vez, construa um mapa inverso (Map<V, K>) ou um Set<V> de valores uma vez e consulte-o.

getOrDefault é uma pequena mas importante mudança de padrão: substitui o velho idioma Integer n = map.get(k); if (n == null) n = 0; por uma única linha, e o valor padrão é usado somente quando a chave está ausente — não quando o valor é null. (Para "ausente ou null," use Objects.requireNonNullElse(map.get(k), 0).)

Collections.binarySearch

Busca binária em uma lista ordenada:

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

Duas pré-condições:

1. A lista deve estar ordenada na ordem que a pesquisa utilizará. Se você ordenou com um comparador, passe o mesmo comparador para binarySearch. Ordens incompatíveis produzem resultados sem sentido (silenciosamente — sem exceção).
2. A lista deve ser indexada (ArrayList, não LinkedList). Em uma lista encadeada, a busca binária é O(n log n), pior do que a varredura linear.

O valor de retorno codifica tanto "encontrado" quanto "onde inserir":

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
}

A aritmética -i - 1 é a forma como toda rotina de "encontrar ou inserir" no JDK lida com uma falha. Vale a pena memorizar.

Collections.frequency e disjoint

Dois auxiliares que encapsulam padrões de pesquisa comuns:

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). Para consultas repetidas com alvos diferentes, conte uma vez com um stream em um Map<T, Long>.

disjoint é implementado de forma inteligente: ele itera a coleção menor e verifica contains na maior se a maior for um Set, trocando os argumentos internamente. Portanto, Collections.disjoint(largeList, smallSet) é O(largeList) — e mais rápido do que fazer o próprio.

Pesquisa baseada em Stream

Streams lidam com "encontrar o primeiro elemento correspondente" com findFirst / findAny, e "há alguma correspondência" com 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);

Streams fazem curto-circuito em findFirst e anyMatch — eles param assim que uma correspondência é encontrada. São a resposta mais limpa para pesquisa baseada em predicados. Eles não são mais rápidos do que contains para pesquisa de igualdade na estrutura de dados correta — um HashSet.contains sempre vencerá stream().anyMatch(x -> x.equals(target)).

Optional<T> merece atenção própria (tem um capítulo na parte de programação funcional). Por ora: findFirst().isPresent() é a expressão mais limpa de "encontramos algo?" para um predicado.

LinkedHashSet para "contains e ordem"

Um padrão comum: você precisa de contains rápido e iteração em ordem de inserção. LinkedHashSet é a resposta:

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

add retorna true apenas na primeira vez. O conjunto rejeita duplicatas em O(1) e preserva a ordem de inserção para iteração. Essa é a ferramenta certa para "desduplicar mantendo a ordem" — nem HashSet (perde a ordem) nem ArrayList (contains lento) é tão bom.

Um exemplo prático: comparando cinco estratégias de pesquisa nos mesmos dados

O programa abaixo preenche 100 000 strings em diferentes coleções e mede cinco estratégias de busca para 1 000 ocorrências aleatórias: ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch em uma lista ordenada e stream().anyMatch.

O que observar na execução:

• HashSet.contains e Collections.binarySearch no ArrayList ordenado são dramaticamente mais rápidos do que ArrayList.contains para buscas repetidas. A tabela hash vence para "qualquer igualdade," a busca binária vence quando os dados precisam ser mantidos ordenados por outros motivos também.
• TreeSet.contains fica logo atrás, mas não é gratuito — cada busca percorre uma árvore de profundidade ~log₂(100 000) ≈ 17, com erros de cache para ponteiros de árvore.
• stream().anyMatch para pesquisa de igualdade é a pior opção aqui: mesmo O(n) que list.contains, mas com sobrecarga extra de alocação por consulta. Use-o para predicados, não para igualdade simples em uma lista.
• A chamada com "chave ausente" retornou um valor negativo, e -i - 1 forneceu o índice onde "zzz" seria inserido para manter a lista ordenada. Essa é a mesma convenção que TreeMap.subMap e Arrays.binarySearch usam.

O que vem a seguir

Você já cobriu iteração, ordenação, classificação e pesquisa — as quatro operações mecânicas para as quais o framework de coleções existe. O capítulo final desta parte aborda a história moderna para a única coisa que nenhum deles tocou: imutabilidade. Coleções não modificáveis em Java cobre List.of, Set.of, Map.of e os wrappers Collections.unmodifiable* — quando cada um é a escolha certa e por que um padrão de "cópia defensiva" que antes ocupava quatro linhas agora cabe em uma.

Prática