Búsqueda en colecciones de Java

"¿Está este elemento en la colección?" parece una sola pregunta, pero Java la responde de media docena de formas distintas, con costes diferentes y tipos de retorno diferentes. Saber cuál usar puede convertir un bucle caliente de 50 milisegundos en uno de 50 microsegundos. Este capítulo es un recorrido por los métodos de búsqueda en colecciones, los mapas que las envuelven y los helpers estáticos de Collections.

El modelo mental orientado al coste

El coste de cada método de búsqueda lo determina la colección subyacente, no el lugar donde se llama. Elige la colección correcta desde el principio y tus búsquedas serán gratuitas; elige la equivocada y ninguna llamada ingeniosa te salvará.

Colección	`contains` / consulta	Por qué
`HashSet`, `LinkedHashSet`, `HashMap.keySet()`	O(1) esperado	Búsqueda por bucket hash
`TreeSet`, `TreeMap.keySet()`	O(log n)	Árbol rojo-negro
`ArrayList`, `LinkedList`, `Vector`	O(n)	Recorrido lineal
`ArrayList` ordenado + `Collections.binarySearch`	O(log n)	Búsqueda binaria en lista indexada
`LinkedList` + `Collections.binarySearch`	O(n)	La búsqueda binaria debe indexar — O(n) por paso

Dos reglas prácticas:

Si usas contains con frecuencia, usa un Set. Construir un HashSet a partir de una List y consultarlo casi siempre es más rápido que list.contains en un bucle.
Si los datos están ordenados e indexados, usa Collections.binarySearch. Vale la pena a partir de unos 30 elementos en la mayoría de JVMs.

`Collection.contains(o)`

Toda Collection lo tiene. La semántica se basa en igualdad:

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

Para una List, esto es un recorrido lineal — O(n). Para un HashSet, es una búsqueda por bucket hash — O(1) esperado. Para un TreeSet, es un recorrido de árbol de O(log n). La firma del método es la misma; el coste no lo es.

Se permite null (el método devuelve si la colección contiene algún elemento null), a menos que la colección rechace null directamente — TreeSet con ordenación natural, EnumSet, ConcurrentHashMap.keySet().

`List.indexOf` y `lastIndexOf`

Las listas soportan más que un simple "sí/no" — devuelven la posición:

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

Recorrido lineal desde el frente (o desde el final). Para un ArrayList<String> de mil elementos, esto está bien. Para un millón, construye un Map<String, Integer> una vez y consúltalo.

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

Los métodos de búsqueda específicos de los mapas se dividen 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 es la trampa. Recorre cada entrada cada vez. Si te encuentras llamándolo más de una vez, construye un mapa inverso (Map<V, K>) o un Set<V> de valores una vez y consúltalo.

getOrDefault es un pequeño pero importante cambio de patrón: reemplaza el antiguo idioma Integer n = map.get(k); if (n == null) n = 0; con una sola línea, y el valor por defecto solo se usa cuando la clave está ausente — no cuando el valor es null. (Para "ausente o null," usa Objects.requireNonNullElse(map.get(k), 0).)

`Collections.binarySearch`

Búsqueda binaria en una 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

Dos precondiciones:

La lista debe estar ordenada en el orden que usará la búsqueda. Si la ordenaste con un comparador, pasa el mismo comparador a binarySearch. Los órdenes incompatibles producen resultados sin sentido (silenciosamente — sin excepción).
La lista debería estar indexada (ArrayList, no LinkedList). En una lista enlazada, la búsqueda binaria es O(n log n), peor que el recorrido lineal.

El valor de retorno codifica tanto "encontrado" como "dónde insertar":

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
}

Esa aritmética de -i - 1 es la forma en que toda rutina "buscar o insertar" en el JDK maneja un fallo. Vale la pena memorizarlo.

`Collections.frequency` y `disjoint`

Dos helpers que encapsulan patrones de búsqueda comunes:

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 es O(n). Para consultas repetidas con diferentes objetivos, cuenta una vez con un stream en un Map<T, Long> en su lugar.

disjoint está implementado de forma inteligente: itera la colección más pequeña y comprueba contains en la más grande si la más grande es un Set, intercambiando argumentos internamente. Así, Collections.disjoint(largeList, smallSet) es O(largeList) — y más rápido que implementarlo tú mismo.

Búsqueda basada en streams

Los streams manejan "encontrar el primer elemento que coincida" con findFirst / findAny, y "¿hay alguna coincidencia?" con 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);

Los streams realizan cortocircuito en findFirst y anyMatch — se detienen tan pronto como se encuentra una coincidencia. Son la respuesta más clara para la búsqueda basada en predicados. No son más rápidos que contains para búsqueda de igualdad en la estructura de datos correcta — un HashSet.contains siempre vencerá a stream().anyMatch(x -> x.equals(target)).

Optional<T> merece atención propia (tiene un capítulo en la parte de programación funcional). Por ahora: findFirst().isPresent() es la expresión más clara de "¿encontramos algo?" para un predicado.

`LinkedHashSet` para "contains y orden"

Un patrón común: necesitas contains rápido y iteración en orden de inserción. LinkedHashSet es la respuesta:

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

add devuelve true solo la primera vez. El conjunto rechaza duplicados en O(1) y preserva el orden de inserción para la iteración. Esa es la herramienta correcta para "deduplicar manteniendo el orden" — ni HashSet (pierde el orden) ni ArrayList (contains lento) es tan bueno.

Un ejemplo práctico: comparando cinco estrategias de búsqueda con los mismos datos

El programa siguiente inserta 100 000 strings en distintas colecciones y mide cinco estrategias de consulta para 1 000 coincidencias aleatorias: ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch en una lista ordenada y 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)");
  }
}

Qué extraer de la ejecución:

HashSet.contains y Collections.binarySearch en el ArrayList ordenado son dramáticamente más rápidos que ArrayList.contains para consultas repetidas. La tabla hash gana para "cualquier igualdad," la búsqueda binaria gana cuando los datos deben mantenerse ordenados por otras razones también.
TreeSet.contains va muy cerca, pero no es gratuito — cada consulta recorre un árbol de profundidad ~log₂(100 000) ≈ 17, con fallos de caché para los punteros del árbol.
stream().anyMatch para búsqueda de igualdad es la peor opción aquí: el mismo O(n) que list.contains pero con sobrecarga de asignación adicional por consulta. Úsalo para predicados, no para igualdad simple en una lista.
La llamada con "clave ausente" devolvió un valor negativo, y -i - 1 dio el índice donde se insertaría "zzz" para mantener la lista ordenada. Esa es la misma convención que usan TreeMap.subMap y Arrays.binarySearch.

Qué viene a continuación

Ya has cubierto iteración, ordenación, clasificación y búsqueda — las cuatro operaciones mecánicas para las que existe el framework de colecciones. El capítulo final de esta parte es la historia moderna para lo único que ninguna de ellas tocó: la inmutabilidad. Java Unmodifiable Collections cubre List.of, Set.of, Map.of, y los wrappers Collections.unmodifiable* — cuándo cada uno es la elección correcta y por qué un patrón de "copia defensiva" que antes ocupaba cuatro líneas ahora cabe en una.

Práctica

Llamas a `Collections.binarySearch(sortedList, key)` y el resultado es `-5`. ¿En qué índice habría que insertar `key` para mantener la lista ordenada?

`4` — para un fallo, el punto de inserción es `-resultado - 1``-5` — las colecciones de Java admiten índices negativos para inserciones de búsqueda binaria`5` — la magnitud del resultado negativo es el punto de inserción`0` — un resultado negativo significa que la lista no está ordenada y la búsqueda abortó antes de encontrar una posición

El modelo mental orientado al coste

Collection.contains(o)

List.indexOf y lastIndexOf

Map.containsKey, containsValue, get, getOrDefault

Collections.binarySearch

Collections.frequency y disjoint