Ricerca nelle Java Collections

"Questo elemento è nella collection?" sembra una domanda sola, ma Java risponde in una mezza dozzina di modi diversi, con costi e tipi di ritorno differenti. Sapere quale scegliere trasforma un hot loop da 50 millisecondi in uno da 50 microsecondi. Questo capitolo è un tour dei metodi di ricerca sulle collections, le mappe che le avvolgono e gli helper statici in Collections.

Il modello mentale orientato al costo

Il costo di ogni metodo di ricerca è determinato dalla collection sottostante, non dal sito di chiamata. Scegli la collection giusta fin dall'inizio e le ricerche saranno gratuite; scegli quella sbagliata e nessuna chiamata di metodo intelligente ti salverà.

Due regole empiriche:

1. Se usi molto contains, usa un Set. Costruire un HashSet da una List e interrogarlo è quasi sempre più veloce di list.contains in un ciclo.
2. Se i dati sono ordinati e indicizzati, usa Collections.binarySearch. Conviene dopo circa 30 elementi sulla maggior parte delle JVM.

Collection.contains(o)

Ce l'ha ogni Collection. La semantica è basata sull'uguaglianza:

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

Per una List, si tratta di una scansione lineare — O(n). Per un HashSet, è un lookup con hash-bucket — O(1) atteso. Per un TreeSet, è un'esplorazione dell'albero O(log n). La firma del metodo è la stessa; il costo no.

null è ammesso (il metodo restituisce se la collection contiene un elemento null), a meno che la collection non rifiuti null del tutto — TreeSet con ordinamento naturale, EnumSet, ConcurrentHashMap.keySet().

List.indexOf e lastIndexOf

Le liste supportano più del semplice "sì/no" — restituiscono la posizione:

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

Scansione lineare dall'inizio (o dalla fine). Per un ArrayList<String> di mille elementi, va bene. Per un milione, costruisci una Map<String, Integer> una volta e interrogala.

Map.containsKey, containsValue, get, getOrDefault

I metodi di ricerca specifici delle mappe si dividono nettamente:

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 è la trappola. Scorre ogni voce ogni volta. Se ti ritrovi a chiamarlo più di una volta, costruisci una mappa inversa (Map<V, K>) o un Set<V> di valori una sola volta e interroga quello.

getOrDefault è un piccolo ma importante cambio di paradigma: sostituisce il vecchio idioma Integer n = map.get(k); if (n == null) n = 0; con una riga sola, e il valore predefinito viene usato solo quando la chiave è assente — non quando il valore è null. (Per "assente o null," usa Objects.requireNonNullElse(map.get(k), 0).)

Collections.binarySearch

Ricerca binaria su una lista ordinata:

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

Due precondizioni:

1. La lista deve essere ordinata nell'ordine che la ricerca utilizzerà. Se hai ordinato con un comparatore, passa lo stesso comparatore a binarySearch. Ordini non corrispondenti producono risultati privi di senso (in silenzio — nessuna eccezione).
2. La lista dovrebbe essere indicizzata (ArrayList, non LinkedList). Su una lista collegata, la ricerca binaria è O(n log n), peggiore della scansione lineare.

Il valore di ritorno codifica sia "trovato" che "dove inserire":

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
}

Quell'aritmetica -i - 1 è il modo in cui ogni routine "trova o inserisci" nel JDK gestisce una mancata corrispondenza. Vale la pena memorizzarla.

Collections.frequency e disjoint

Due helper che racchiudono pattern di ricerca comuni:

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). Per query ripetute con target diversi, conta una volta con uno stream in una Map<T, Long>.

disjoint è implementato in modo intelligente: itera la collection più piccola e controlla contains sulla più grande se quest'ultima è un Set, scambiando gli argomenti internamente. Quindi Collections.disjoint(largeList, smallSet) è O(largeList) — più veloce di un'implementazione manuale.

Ricerca basata su Stream

Gli stream gestiscono "trova il primo elemento corrispondente" con findFirst / findAny, e "c'è qualche corrispondenza?" 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);

Gli stream cortocircuitano su findFirst e anyMatch — si fermano non appena trovano una corrispondenza. Sono la risposta più pulita per la ricerca basata su predicati. Non sono più veloci di contains per la ricerca per uguaglianza sulla struttura dati giusta — un HashSet.contains batterà sempre stream().anyMatch(x -> x.equals(target)).

Optional<T> merita attenzione a parte (ha un capitolo nella parte sulla programmazione funzionale). Per ora: findFirst().isPresent() è l'espressione più pulita per "abbiamo trovato qualcosa?" con un predicato.

LinkedHashSet per "contains e ordine"

Un pattern comune: hai bisogno di contains veloce e iterazione in ordine di inserimento. LinkedHashSet è la risposta:

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

add restituisce true solo la prima volta. Il set rifiuta i duplicati in O(1) e preserva l'ordine di inserimento per l'iterazione. È lo strumento giusto per "deduplica mantenendo l'ordine" — né HashSet (perde l'ordine) né ArrayList (contains lento) sono altrettanto buoni.

Un esempio pratico: confronto di cinque strategie di ricerca sugli stessi dati

Il programma seguente inserisce 100 000 stringhe in diverse collections e misura cinque strategie di ricerca per 1 000 hit casuali: ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch su una lista ordinata e stream().anyMatch.

Cosa ricavare dall'esecuzione:

• HashSet.contains e Collections.binarySearch sull'ArrayList ordinato sono drasticamente più veloci di ArrayList.contains per lookup ripetuti. La hash table vince per "qualsiasi uguaglianza," la ricerca binaria vince quando i dati devono essere mantenuti ordinati anche per altri motivi.
• TreeSet.contains è vicino, ma non gratuito — ogni lookup percorre un albero di profondità ~log₂(100 000) ≈ 17, con cache miss per i puntatori dell'albero.
• stream().anyMatch per la ricerca per uguaglianza è l'opzione peggiore qui: stesso O(n) di list.contains ma con overhead aggiuntivo di allocazione per ogni query. Usalo per predicati, non per semplice uguaglianza su una lista.
• La chiamata con "chiave mancante" ha restituito un valore negativo, e -i - 1 ha fornito l'indice in cui "zzz" verrebbe inserito per mantenere la lista ordinata. È la stessa convenzione usata da TreeMap.subMap e Arrays.binarySearch.

Cosa viene dopo

Hai ora affrontato iterazione, ordinamento, sorting e ricerca — le quattro operazioni meccaniche per cui esiste il framework delle collections. L'ultimo capitolo in questa parte è la storia moderna per l'unica cosa che nessuno di essi ha toccato: l'immutabilità. Java Unmodifiable Collections tratta List.of, Set.of, Map.of e i wrapper Collections.unmodifiable* — quando ognuno è la scelta giusta, e perché un pattern "copia difensiva" che una volta richiedeva quattro righe ora si scrive in una.

Esercizi