El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A la lliçó anterior vas desmuntar el HashMap peça a peça: la funció hash, els cubells, les col·lisions, el factor de càrrega, el rehash i —per fi— la raó exacta per la qual equals i hashCode han d'anar sempre junts. Aquesta inversió et retornarà interessos immediats, perquè un HashSet és literalment un HashMap amb valors ficticis. No és cap metàfora didàctica: és la seva implementació real, i la veuràs al codi font del JDK.

Un conjunt (Set) modela la idea matemàtica de conjunt: una col·lecció sense elements repetits. Aquesta única restricció resol tota sola una família sencera de problemes que amb llistes requereixen bucles i comprovacions: detectar duplicats, comprovar pertinença, creuar dues col·leccions per saber què tenen en comú o en què es diferencien. A BiblioTech ja vas fer servir un Set<String> com a apedaçament per no repetir ISBN; en acabar aquesta lliçó serà una peça de disseny amb tot el seu potencial desplegat.

També veuràs la diferència de rendiment més espectacular de tot el mòdul: buscar en un Set enfront de buscar en una List. No és un 20 % millor. Són cinc ordres de magnitud.

Contingut

Què és un conjunt
La interfície Set i la seva API
HashSet és un HashMap disfressat
add retorna boolean, i això ho canvia tot
Operacions de conjunt
HashSet, LinkedHashSet i TreeSet
TreeSet, SortedSet i NavigableSet
El perill de mutar un element desat
Conjunts immutables
contains en un Set enfront d'una List
Aplicació a BiblioTech
Errors Habituals i Consells
Exercicis

Què és un conjunt

Un Set és una col·lecció amb dues propietats definitòries:

No admet duplicats. Afegir un element que ja hi és no fa res.
No garanteix ordre (en el cas de HashSet). L'ordre de recorregut és impredictible i pot canviar.

import java.util.HashSet;
import java.util.Set;

Set<String> isbnCatalogats = new HashSet<>();

isbnCatalogats.add("978-0000000001");
isbnCatalogats.add("978-0000000002");
isbnCatalogats.add("978-0000000001");     // ja hi era: s'ignora

System.out.println(isbnCatalogats.size());      // 2, no 3
System.out.println(isbnCatalogats);             // ordre impredictible

Què significa exactament "ja hi era"? Aquí és on 03-09 i 05-05 s'ajunten: dos elements són el mateix si equals diu que ho són, i per arribar a comparar-los el conjunt fa servir hashCode. Tot el que vas aprendre sobre claus de mapa s'aplica exactament igual als elements d'un conjunt.

La pregunta que decideix entre List i Set:

Pregunta	Resposta	Col·lecció
Hi pot haver elements repetits, i cadascun compta?	Sí	`List`
Un repetit és un error o una dada redundant?	Sí	`Set`
Importa l'ordre i la posició?	Sí	`List`
Només m'importa "hi és o no hi és"?	Sí	`Set`

Exemples clars a BiblioTech:

El catàleg és una List: podria haver-hi dos exemplars del mateix llibre i l'ordre d'exhibició importa.
Els ISBN catalogats són un Set: un ISBN repetit és un error d'alta.
Els empleats amb préstecs vençuts són un Set: un empleat amb tres préstecs vençuts hi apareix una vegada.
Els avisos ja enviats són un Set: no volem enviar dues vegades el mateix.

Quan tries Set, la unicitat deixa de ser una cosa que has de vigilar i passa a estar garantida per l'estructura. Això és disseny: el tipus documenta i fa complir la regla.

La interfície `Set` i la seva API

Set estén Collection i, curiosament, no afegeix ni un sol mètode nou. El que canvia és el contracte: add pot rebutjar, i no hi ha accés per índex.

Mètode	Què fa	Complexitat a `HashSet`
`add(E e)`	Afegeix si no hi era. Retorna `false` si ja hi era	O(1)
`remove(Object o)`	Elimina. Retorna `true` si hi havia alguna cosa	O(1)
`contains(Object o)`	Hi és?	O(1)
`size()` / `isEmpty()`	Quants n'hi ha	O(1)
`clear()`	Buida	O(n)
`addAll(Collection c)`	Unió amb una altra col·lecció	O(m)
`retainAll(Collection c)`	Intersecció	O(n)
`removeAll(Collection c)`	Diferència	O(m)
`containsAll(Collection c)`	És superconjunt?	O(m)
`removeIf(Predicate)`	Elimina els que compleixin	O(n)
`forEach(Consumer)`	Recorre	O(n)
`iterator()`	Recorregut explícit	O(n)
`toArray(T[] a)`	Aboca a array	O(n)

El que no hi ha, i és important notar-ho:

No hi ha get(i). Un conjunt no té posicions. Per arribar a un element concret, o el recorres, o consultes si hi és amb contains.
No hi ha set(i, e) ni indexOf.
No hi ha ordre a HashSet. Si necessites ordre, canvies d'implementació.

Ús bàsic:

Set<String> empleatsAmbAvis = new HashSet<>();
empleatsAmbAvis.add("EMP-001");
empleatsAmbAvis.add("EMP-002");

if (empleatsAmbAvis.contains("EMP-001")) {            // O(1)
    System.out.println("A la Marta ja se la va avisar");
}

empleatsAmbAvis.remove("EMP-002");
System.out.println(empleatsAmbAvis.size());            // 1

for (String id : empleatsAmbAvis) {                    // for-each: l'unica forma de recorrer
    System.out.println(id);
}

`HashSet` és un `HashMap` disfressat

Obre java.util.HashSet al JDK i hi trobaràs això:

public class HashSet<E> extends AbstractSet<E> implements Set<E> {

    private transient HashMap<E, Object> map;          // un HashMap per dins

    // El valor fictici que s'associa a TOTES les claus
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;    // put retorna null si la clau era nova
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public int size() {
        return map.size();
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
}

Un HashSet és un HashMap en què només importen les claus. Els elements del conjunt són les claus del mapa; tots els valors són el mateix objecte sentinella PRESENT, que no significa res i només existeix perquè HashMap necessita alguna cosa per guardar.

flowchart LR
    subgraph HS["HashSet"]
        M["map →"]
    end
    subgraph HM["HashMap intern"]
        E1["'978-0000000001' → PRESENT"]
        E2["'978-0000000002' → PRESENT"]
        E3["'REV-2024-03' → PRESENT"]
    end
    M --> HM
    P["PRESENT<br/>(un unic objecte compartit)"]
    E1 -.-> P
    E2 -.-> P
    E3 -.-> P

D'aquesta identitat es dedueix tot el que necessites saber sobre HashSet, sense aprendre res de nou:

Propietat del `HashSet`	Perquè el `HashMap` intern...
`add`, `contains`, `remove` són O(1)	...localitza el cubell calculant el hash
No admet duplicats	...no admet claus duplicades
No garanteix ordre	...no garanteix ordre de claus
Admet un sol `null`	...admet una sola clau `null`
Exigeix `equals` i `hashCode` correctes	...els exigeix a les seves claus
Els elements han de ser immutables	...les seves claus ho han de ser
Té factor de càrrega i rehash	...els té
Un cubell amb 8+ elements es converteix en arbre	...ho fa

I d'aquí surt l'avís central d'aquesta lliçó: tot el que trencava un HashMap a 05-05 trenca exactament igual un HashSet. Un element amb equals però sense hashCode entra al conjunt i no es troba mai, i s'hi poden posar dos "duplicats" en un conjunt que garanteix unicitat:

// ClauTrencada tenia equals pero NO hashCode (05-05)
Set<ClauTrencada> conjunt = new HashSet<>();
conjunt.add(new ClauTrencada("978-0000000001"));
conjunt.add(new ClauTrencada("978-0000000001"));    // "igual", pero amb un altre hash

System.out.println(conjunt.size());               // 2   <-- DUPLICATS en un Set
System.out.println(conjunt.contains(new ClauTrencada("978-0000000001")));   // false

La mateixa explicació de 05-05: contains calcula el hash, va a un cubell que és buit i retorna false sense arribar a cridar equals.

Un HashSet també té constructors amb capacitat, amb la mateixa semàntica i els mateixos comptes que un HashMap:

Set<String> isbn = new HashSet<>();                                  // per defecte
Set<String> gran = new HashSet<>((int)(50_000 / 0.75f) + 1);         // sense rehashes
Set<Material> copia = new HashSet<>(llistaDeMaterials);              // des d'una altra colleccio

Aquest últim constructor és un idioma molt útil: eliminar duplicats d'una llista en una línia.

List<String> ambRepetits = List.of("A", "B", "A", "C", "B");
Set<String> senseRepetits = new HashSet<>(ambRepetits);      // [A, B, C], ordre impredictible

// I si vols una llista sense duplicats conservant l'ordre original:
List<String> llista = new ArrayList<>(new LinkedHashSet<>(ambRepetits));   // [A, B, C]

`add` retorna `boolean`, i això ho canvia tot

Collection.add retorna boolean. En una List aquest valor sempre és true i ningú no se'l mira. En un Set és informació valuosa:

add retorna true si l'element s'ha afegit (era nou) i false si ja hi era.

Això resol el problema de "detectar duplicats" sense cap comprovació prèvia:

// SENSE aprofitar-ho: dues operacions, dues cerques
if (isbnCatalogats.contains(isbn)) {
    System.out.println("AVIS: ISBN duplicat");
} else {
    isbnCatalogats.add(isbn);
}

// APROFITANT-HO: una operacio, una cerca
if (!isbnCatalogats.add(isbn)) {
    System.out.println("AVIS: ISBN duplicat -> " + isbn);
}

La segona versió no només és més curta: fa la meitat de feina, perquè contains seguit d'add recorre el mateix cubell dues vegades.

Aplicacions típiques del patró:

// 1. Processar cada element NOMES la primera vegada que apareix
Set<String> jaProcessats = new HashSet<>();
for (Prestec p : prestecs) {
    if (jaProcessats.add(p.getEmpleat().getIdentificador())) {
        enviarResumMensual(p.getEmpleat());          // nomes una vegada per empleat
    }
}

// 2. Detectar el primer duplicat d'una llista
Set<String> vistos = new HashSet<>();
for (String isbn : isbnDelFitxer) {
    if (!vistos.add(isbn)) {
        System.out.println("Primera repeticio: " + isbn);
        break;
    }
}

// 3. Comptar quants elements diferents hi ha
Set<String> diferents = new HashSet<>(totsElsIsbn);
System.out.println("Materials diferents: " + diferents.size());

// 4. Evitar cicles infinits en recorrer relacions
Set<Material> visitats = new HashSet<>();
// ... if (!visitats.add(actual)) { return; }  // ja hem passat per aqui

Els mètodes germans segueixen la mateixa lògica:

Mètode	Retorna `true` quan...
`add(e)`	L'element no hi era i s'ha afegit
`remove(o)`	L'element hi era i s'ha eliminat
`addAll(c)`	Almenys un dels elements era nou
`removeAll(c)`	Almenys un s'ha eliminat
`retainAll(c)`	El conjunt ha canviat

Operacions de conjunt

Aquí Set demostra que no és una List retallada, sinó una estructura amb àlgebra pròpia. Les quatre operacions clàssiques de la teoria de conjunts tenen el seu mètode:

Set<String> ambPrestec = new HashSet<>(Set.of("EMP-001", "EMP-002", "EMP-003"));
Set<String> ambRetard  = new HashSet<>(Set.of("EMP-002", "EMP-003", "EMP-005"));

flowchart TB
    subgraph diagrama["Empleats"]
        A["ambPrestec<br/>EMP-001, EMP-002, EMP-003"]
        B["ambRetard<br/>EMP-002, EMP-003, EMP-005"]
        I["INTERSECCIO<br/>EMP-002, EMP-003<br/>(amb prestec I amb retard)"]
        A --- I
        B --- I
    end

Unió: `addAll`

Tots els elements de tots dos conjunts, sense repetir.

Set<String> unio = new HashSet<>(ambPrestec);   // copia, per no destruir l'original
unio.addAll(ambRetard);
System.out.println(unio);       // [EMP-001, EMP-002, EMP-003, EMP-005]

Intersecció: `retainAll`

Només els que són a tots dos.

Set<String> interseccio = new HashSet<>(ambPrestec);
interseccio.retainAll(ambRetard);
System.out.println(interseccio);    // [EMP-002, EMP-003]

Diferència: `removeAll`

Els que són al primer però no al segon.

Set<String> nomesAmbPrestec = new HashSet<>(ambPrestec);
nomesAmbPrestec.removeAll(ambRetard);
System.out.println(nomesAmbPrestec);    // [EMP-001]

// Compte: la diferencia NO es simetrica
Set<String> nomesAmbRetard = new HashSet<>(ambRetard);
nomesAmbRetard.removeAll(ambPrestec);
System.out.println(nomesAmbRetard);     // [EMP-005]

Subconjunt: `containsAll`

Hi són tots els del segon al primer?

Set<String> alguns = Set.of("EMP-002", "EMP-003");
System.out.println(ambPrestec.containsAll(alguns));     // true: es un subconjunt
System.out.println(ambPrestec.containsAll(ambRetard));  // false: falta EMP-005

Diferència simètrica

No té mètode propi, però es compon amb les anteriors: els que són en un o en l'altre, però no en tots dos.

Set<String> simetrica = new HashSet<>(ambPrestec);
simetrica.addAll(ambRetard);                          // unio

Set<String> comuns = new HashSet<>(ambPrestec);
comuns.retainAll(ambRetard);                          // interseccio

simetrica.removeAll(comuns);                          // unio menys interseccio
System.out.println(simetrica);      // [EMP-001, EMP-005]

Taula resum

Operació matemàtica	Mètode	Efecte
Unió (A ∪ B)	`a.addAll(b)`	A passa a contenir-ho tot
Intersecció (A ∩ B)	`a.retainAll(b)`	A conserva només el que és comú
Diferència (A − B)	`a.removeAll(b)`	A perd el que era a B
Subconjunt (B ⊆ A)	`a.containsAll(b)`	No modifica res, només consulta
Disjunts (A ∩ B = ∅)	`Collections.disjoint(a, b)`	`true` si no comparteixen res

Avís crític: les tres primeres modifiquen el conjunt sobre el qual s'invoquen. Si necessites conservar els originals —cosa que passa gairebé sempre—, treballa sobre una còpia:

Set<String> resultat = new HashSet<>(original);    // COPIA
resultat.retainAll(altre);                         // es modifica la copia

Oblidar la còpia i destruir el conjunt original és un dels errors més freqüents amb operacions de conjunt.

`HashSet`, `LinkedHashSet` i `TreeSet`

Aspecte	`HashSet`	`LinkedHashSet`	`TreeSet`
Estructura interna	`HashMap`	`LinkedHashMap`	`TreeMap` (arbre roig-negre)
Ordre de recorregut	Cap de garantit	Inserció	Ordenat
`add` / `contains` / `remove`	O(1)	O(1)	O(log n)
Memòria	Menor	+2 referències per element	Major
`null` permès	Un	Un	No: `NullPointerException`
Requisit de l'element	`equals` + `hashCode`	`equals` + `hashCode`	`Comparable` o `Comparator`
Operacions de rang	No	No	Sí: `headSet`, `ceiling`...
Quan fer-lo servir	Per defecte	Ordre reproduïble	Ordre permanent, rangs

Els tres en acció sobre les mateixes dades:

List<String> entrada = List.of("Revista", "Llibre", "DVD", "Llibre", "Audiollibre");

Set<String> hash   = new HashSet<>(entrada);
Set<String> linked = new LinkedHashSet<>(entrada);
Set<String> arbre  = new TreeSet<>(entrada);

System.out.println("HashSet:       " + hash);     // [DVD, Revista, Llibre, Audiollibre] (impredictible)
System.out.println("LinkedHashSet: " + linked);   // [Revista, Llibre, DVD, Audiollibre]  (insercio)
System.out.println("TreeSet:       " + arbre);    // [Audiollibre, DVD, Llibre, Revista]  (alfabetic)

Els tres tenen 4 elements: el "Llibre" repetit es va descartar en els tres casos.

Quan fer servir cadascun:

HashSet: per defecte. Si només t'importa "hi és o no hi és", és la resposta.
LinkedHashSet: quan la sortida hagi de ser reproduïble —informes, tests, fitxers generats— o quan vulguis eliminar duplicats conservant l'ordre original. El sobrecost és mínim.
TreeSet: quan necessitis recórrer sempre en ordre, o consultar rangs i veïns. Recorda que passes d'O(1) a O(log n): amb un milió d'elements són unes 20 comparacions per operació, generalment assumible.

`TreeSet`, `SortedSet` i `NavigableSet`

TreeSet implementa NavigableSet, que estén SortedSet, que estén Set. Cada nivell afegeix operacions que només tenen sentit si hi ha ordre.

TreeSet<String> referencies = new TreeSet<>(Set.of(
    "978-0000000001", "978-0000000002", "978-0000000003", "DVD-0007", "REV-2024-03"));

// SortedSet: extrems i rangs
System.out.println(referencies.first());       // 978-0000000001
System.out.println(referencies.last());        // REV-2024-03
System.out.println(referencies.headSet("DVD-0007"));   // els ESTRICTAMENT menors
System.out.println(referencies.tailSet("DVD-0007"));   // els majors O IGUALS
System.out.println(referencies.subSet("978-0000000002", "DVD-0007"));

// NavigableSet: veins
System.out.println(referencies.ceiling("978-0000000002x"));  // el menor >= donat
System.out.println(referencies.floor("978-0000000002x"));    // el major <= donat
System.out.println(referencies.higher("978-0000000002"));    // estrictament major
System.out.println(referencies.lower("978-0000000002"));     // estrictament menor

// NavigableSet: extreure extrems (util com a cua de prioritat)
System.out.println(referencies.pollFirst());   // retorna I ELIMINA el primer
System.out.println(referencies.pollLast());    // retorna I ELIMINA l'ultim

// Recorregut invers
System.out.println(referencies.descendingSet());

Mètode	Retorna
`first()` / `last()`	El menor / major. `NoSuchElementException` si és buit
`pollFirst()` / `pollLast()`	El menor / major, eliminant-lo. `null` si és buit
`headSet(e)`	Vista dels menors que `e`
`tailSet(e)`	Vista dels majors o iguals que `e`
`subSet(a, b)`	Vista del rang [a, b)
`ceiling(e)`	El menor element ≥ e, o `null`
`floor(e)`	El major element ≤ e, o `null`
`higher(e)` / `lower(e)`	Estrictament major / menor, o `null`
`descendingSet()`	Vista en ordre invers

Les vistes de rang són vives: eliminar d'un headSet elimina del TreeSet original.

Ordre natural o `Comparator`

TreeSet necessita saber com comparar els seus elements. Dues opcions:

// 1. Ordre natural: els elements implementen Comparable
TreeSet<Fitxa> perTitol = new TreeSet<>();           // Fitxa implementa Comparable (04-07)
perTitol.add(new Fitxa("Refactoritzacio",    "Martin Fowler", 1999));
perTitol.add(new Fitxa("Java Eficac",        "Joshua Bloch",  2018));
perTitol.add(new Fitxa("Patrons de Disseny", "Erich Gamma",   1994));
// recorregut: Java Eficac, Patrons de Disseny, Refactoritzacio

// 2. Comparator explicit, reprenent 04-06
TreeSet<Material> perTarifa = new TreeSet<>(
    Comparator.comparingDouble(Material::getTarifaDiaria)
              .thenComparing(Material::getReferencia));    // desempat: OBLIGATORI

Si l'element no implementa Comparable i no li dones cap Comparator, la primera inserció llança ClassCastException.

I aquí hi ha un parany que cal entendre bé. En un TreeSet, la unicitat no la decideix equals: la decideix el comparador. Dos elements són "el mateix" si compareTo (o compare) retorna 0.

TreeSet<Material> perTarifa = new TreeSet<>(
    Comparator.comparingDouble(Material::getTarifaDiaria));   // SENSE desempat

perTarifa.add(new Llibre("Java Eficac",        "Joshua Bloch", "978-0000000001", 2018));  // 0.25
perTarifa.add(new Llibre("Patrons de Disseny", "Erich Gamma",  "978-0000000002", 1994));  // 0.25

System.out.println(perTarifa.size());   // 1  <-- el segon s'ha descartat!

Els dos llibres són objectes diferents, amb equals diferent, però la seva tarifa és la mateixa, així que el comparador retorna 0 i el TreeSet els considera duplicats. És una font de pèrdues de dades silencioses.

Regla imprescindible: el Comparator d'un TreeSet ha de ser "total", és a dir, ha de retornar 0 només per a elements realment iguals. Afegeix sempre un criteri de desempat únic:

Comparator.comparingDouble(Material::getTarifaDiaria)
          .thenComparing(Material::getReferencia)    // la referencia es unica

A aquesta propietat se l'anomena coherència amb equals, i a 05-09 l'estudiaràs com a part del contracte de Comparable.

El perill de mutar un element desat

És el mateix problema de les claus mutables de 05-05, i per la mateixa raó: els elements del HashSet són les claus del HashMap intern.

package com.nexussoftware.bibliotech.domini;

/** Etiqueta mutable. Mala candidata a element d'un Set. */
public class Etiqueta {
    private String nom;                     // no final: el problema

    public Etiqueta(String nom) { this.nom = nom; }
    public void setNom(String nom) { this.nom = nom; }

    @Override public boolean equals(Object o) {
        return (o instanceof Etiqueta e) && nom.equals(e.nom);
    }
    @Override public int hashCode() { return nom.hashCode(); }
    @Override public String toString() { return nom; }
}

Etiqueta e = new Etiqueta("java");
Set<Etiqueta> etiquetes = new HashSet<>();
etiquetes.add(e);

System.out.println(etiquetes.contains(e));    // true

e.setNom("programacio");                      // MUTEM un element JA DESAT

System.out.println(etiquetes.contains(e));    // false  <-- perdut
System.out.println(etiquetes.size());         // 1      <-- continua a dins
System.out.println(etiquetes);                // [programacio]
System.out.println(etiquetes.remove(e));      // false  <-- ni tan sols es pot treure

etiquetes.add(e);                             // s'afegeix UNA ALTRA VEGADA el mateix objecte
System.out.println(etiquetes.size());         // 2      <-- el mateix objecte, dues vegades

L'element va quedar al cubell del hash antic. contains calcula el hash nou, mira en un altre cubell i no el troba. I com que no el troba, add el torna a inserir: ara el mateix objecte és dues vegades en un conjunt, cosa que se suposa impossible.

A TreeSet el problema és equivalent però amb l'ordre: si mutes el camp pel qual s'ordena, l'element queda en una branca de l'arbre on la cerca binària no l'anirà a buscar mai.

TreeSet<Etiqueta> ordenades = new TreeSet<>(Comparator.comparing(Etiqueta::toString));
Etiqueta z = new Etiqueta("zzz");
ordenades.add(new Etiqueta("aaa"));
ordenades.add(z);
z.setNom("aab");                              // ara hauria d'anar el segon... pero no es recolloca
System.out.println(ordenades.contains(z));    // impredictible

Regla: els elements d'un Set han de ser immutables, o com a mínim ho han de ser els camps que intervenen a equals/hashCode (o al comparador).

Si necessites canviar un element, l'única forma correcta és treure'l, modificar-lo i tornar-lo a posar:

etiquetes.remove(e);          // es treu mentre el seu hash continua sent el correcte
e.setNom("programacio");      // ara ja es pot mutar
etiquetes.add(e);             // es reinsereix al cubell correcte

Conjunts immutables

Com vas veure a 05-02, Set.of(...) crea un conjunt immutable:

Set<String> tipusPrestables = Set.of("Llibre", "Revista", "DVD");

Les seves propietats, amb una particularitat important:

Immutable: add, remove i clear llancen UnsupportedOperationException.
No admet null: NullPointerException en crear-lo.
Rebutja duplicats en construir-se amb IllegalArgumentException:

Set<String> malament = Set.of("Llibre", "Revista", "Llibre");
// IllegalArgumentException: duplicate element: Llibre

Aquest comportament sorprèn molta gent, perquè un HashSet normal ignora els duplicats en silenci. És intencionat: en un literal escrit a mà, un duplicat gairebé segur que és un error teu, i val més que salti en construir-lo que descobrir-ho més tard.

L'ordre de recorregut està deliberadament aleatoritzat entre execucions, perquè ningú no escrigui codi que en depengui.

Els conjunts immutables són ideals per a constants:

public static final Set<String> TIPUS_PRESTABLES = Set.of("Llibre", "Revista", "DVD");
public static final Set<String> ESTATS_FINALS    = Set.of("RETORNAT", "CANCELLAT", "PERDUT");

if (TIPUS_PRESTABLES.contains(m.getTipus())) { ... }   // O(1), i ningu no pot alterar la llista

I Set.copyOf(colleccio) crea una còpia immutable de qualsevol col·lecció, descartant duplicats sense protestar (a diferència de Set.of):

Set<String> instantania = Set.copyOf(llistaAmbPossiblesRepetits);   // sense excepcio

`contains` en un `Set` enfront d'una `List`

Aquesta és la comparació que més impressiona de tot el mòdul, i mereix números.

package com.nexussoftware.bibliotech.presentacio;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ComparativaCerca {

    public static void main(String[] args) {
        final int N = 100_000;
        final int CONSULTES = 10_000;

        List<String> llista = new ArrayList<>(N);
        Set<String>  conjunt = new HashSet<>((int)(N / 0.75f) + 1);
        for (int i = 0; i < N; i++) {
            String ref = "978-" + String.format("%010d", i);
            llista.add(ref);
            conjunt.add(ref);
        }

        // Escalfament
        for (int i = 0; i < 100; i++) { llista.contains("978-0000099999"); }

        long t1 = System.nanoTime();
        int trobatsLlista = 0;
        for (int i = 0; i < CONSULTES; i++) {
            if (llista.contains("978-" + String.format("%010d", N - 1))) { trobatsLlista++; }
        }
        long msLlista = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        int trobatsSet = 0;
        for (int i = 0; i < CONSULTES; i++) {
            if (conjunt.contains("978-" + String.format("%010d", N - 1))) { trobatsSet++; }
        }
        long msSet = (System.nanoTime() - t2) / 1_000_000;

        System.out.printf("List.contains  x%d: %6d ms  (%d trobats)%n",
                          CONSULTES, msLlista, trobatsLlista);
        System.out.printf("Set.contains   x%d: %6d ms  (%d trobats)%n",
                          CONSULTES, msSet, trobatsSet);
        System.out.printf("El Set es aproximadament %d vegades mes rapid%n",
                          msSet == 0 ? msLlista : msLlista / Math.max(msSet, 1));
    }
}

Resultat típic:

List.contains  x10000:   4180 ms  (10000 trobats)
Set.contains   x10000:      1 ms  (10000 trobats)
El Set es aproximadament 4180 vegades mes rapid

I en operacions per segon:

Mida	`List.contains` (pitjor cas)	`Set.contains`	Avantatge
100	~100 comparacions	1 operació	100×
10 000	~10 000	1	10 000×
1 000 000	~1 000 000	1	1 000 000×

D'aquí surt una de les optimitzacions més rendibles i senzilles que existeixen. Aquest patró, que apareix constantment en codi real, és O(n×m):

// LENT: per a cada material, recorrer tota la llista de referencies
List<String> referenciesVetades = carregarVetats();       // 10.000 elements
for (Material m : cataleg) {                              // 10.000 materials
    if (referenciesVetades.contains(m.getReferencia())) {   // O(n) cada vegada
        rebutjar(m);
    }
}
// Total: 100.000.000 de comparacions

I així queda amb una línia canviada:

// RAPID: O(n + m)
Set<String> vetades = new HashSet<>(carregarVetats());    // conversio O(m), una sola vegada
for (Material m : cataleg) {
    if (vetades.contains(m.getReferencia())) {            // O(1) cada vegada
        rebutjar(m);
    }
}
// Total: 20.000 operacions

Regla professional: si faràs contains sobre una col·lecció més d'unes poques vegades, converteix-la primer a Set. El cost de la conversió (O(m), una vegada) s'amortitza gairebé immediatament.

Aplicació a BiblioTech

Dues aplicacions que consoliden el que hem après.

`Set<String>` d'ISBN catalogats

Ja el vas fer servir a 05-02, però ara amb tota la seva lògica:

package com.nexussoftware.bibliotech.servei;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import com.nexussoftware.bibliotech.domini.Material;

/** Control d'altes duplicades al cataleg. */
public class ControlDuplicats {

    private final Set<String> referenciesCatalogades = new HashSet<>();
    private final Set<String> rebutjades = new LinkedHashSet<>();   // ordre d'aparicio

    /**
     * Intenta donar d'alta. El boolean d'add fa tota la feina:
     * true si era nova, false si ja hi era. Una sola cerca.
     */
    public boolean registrar(Material m) {
        if (m == null || m.getReferencia() == null) { return false; }
        if (referenciesCatalogades.add(m.getReferencia())) {
            return true;                                  // alta acceptada
        }
        rebutjades.add(m.getReferencia());                // alta rebutjada: l'anotem
        return false;
    }

    public boolean estaCatalogada(String referencia) {
        return referenciesCatalogades.contains(referencia);   // O(1)
    }

    public boolean donarDeBaixa(String referencia) {
        return referenciesCatalogades.remove(referencia);
    }

    /** Quines de les referencies rebudes NO estan catalogades: diferencia. */
    public Set<String> desconegudes(Set<String> referencies) {
        Set<String> resultat = new HashSet<>(referencies);   // COPIA: no destruim el parametre
        resultat.removeAll(referenciesCatalogades);
        return resultat;
    }

    /** Quines SI estan catalogades: interseccio. */
    public Set<String> conegudes(Set<String> referencies) {
        Set<String> resultat = new HashSet<>(referencies);
        resultat.retainAll(referenciesCatalogades);
        return resultat;
    }

    /** El fitxer rebut, cobreix el cataleg sencer? */
    public boolean cobreixTotElCataleg(Set<String> referencies) {
        return referencies.containsAll(referenciesCatalogades);
    }

    public Set<String> intentsRebutjats() { return Set.copyOf(rebutjades); }
    public int catalogades() { return referenciesCatalogades.size(); }
}

Creuament de conjunts: vençuts enfront d'avisats

Aquí les operacions de conjunt resolen en tres línies el que amb llistes serien bucles imbricats:

package com.nexussoftware.bibliotech.servei;

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
import com.nexussoftware.bibliotech.domini.Empleat;
import com.nexussoftware.bibliotech.domini.Prestec;

/** Gestiona a qui cal avisar per retards, sense repetir avisos. */
public class GestorAvisos {

    private final Set<Empleat> jaAvisats = new HashSet<>();

    /**
     * Empleats amb almenys un prestec vencut. Un empleat amb tres
     * prestecs vencuts hi apareix UNA vegada: aixo es exactament un Set.
     */
    public Set<Empleat> ambVencuts(List<Prestec> prestecs, int diaActual) {
        Set<Empleat> resultat = new HashSet<>();
        for (Prestec p : prestecs) {
            if (!p.estaRetornat() && p.estaVencut(diaActual)) {
                resultat.add(p.getEmpleat());       // els repetits es descarten sols
            }
        }
        return resultat;
    }

    /** DIFERENCIA: vencuts menys ja avisats = pendents d'avisar. */
    public Set<Empleat> pendentsDeAvisar(List<Prestec> prestecs, int diaActual) {
        Set<Empleat> pendents = new HashSet<>(ambVencuts(prestecs, diaActual));
        pendents.removeAll(jaAvisats);
        return pendents;
    }

    /** INTERSECCIO: avisats que continuen tenint retards = cal escalar. */
    public Set<Empleat> reincidents(List<Prestec> prestecs, int diaActual) {
        Set<Empleat> reincidents = new HashSet<>(ambVencuts(prestecs, diaActual));
        reincidents.retainAll(jaAvisats);
        return reincidents;
    }

    /** DIFERENCIA inversa: avisats que ja no deuen res = es pot netejar el seu avis. */
    public Set<Empleat> regularitzats(List<Prestec> prestecs, int diaActual) {
        Set<Empleat> regularitzats = new HashSet<>(jaAvisats);
        regularitzats.removeAll(ambVencuts(prestecs, diaActual));
        return regularitzats;
    }

    /** Envia avisos nomes a qui no l'hagi rebut. Retorna quants n'ha enviat. */
    public int avisar(List<Prestec> prestecs, int diaActual) {
        int enviats = 0;
        for (Empleat e : pendentsDeAvisar(prestecs, diaActual)) {
            System.out.printf("AVIS a %-16s (%s): te material vencut%n",
                              e.getNom(), e.getIdentificador());
            jaAvisats.add(e);
            enviats++;
        }
        return enviats;
    }

    /** Neteja els avisos de qui ja ho ha retornat tot. */
    public int netejarRegularitzats(List<Prestec> prestecs, int diaActual) {
        Set<Empleat> netejar = regularitzats(prestecs, diaActual);
        jaAvisats.removeAll(netejar);
        return netejar.size();
    }

    /** Els avisats, ordenats per nom: TreeSet amb Comparator. */
    public Set<Empleat> avisatsOrdenats() {
        Set<Empleat> ordenats = new TreeSet<>(
            Comparator.comparing(Empleat::getNom)
                      .thenComparing(Empleat::getIdentificador));   // desempat UNIC
        ordenats.addAll(jaAvisats);
        return ordenats;
    }
}

Ús:

Empleat marta = new Empleat("Marta Ruiz",   "EMP-001");
Empleat diego = new Empleat("Diego Alonso", "EMP-002");
Empleat nuria = new Empleat("Nuria Vidal",  "EMP-003");

List<Prestec> prestecs = List.of(
    new Prestec(new Llibre("Java Eficac",        "Joshua Bloch",  "978-0000000001", 2018), marta, 100),
    new Prestec(new Llibre("Refactoritzacio",    "Martin Fowler", "978-0000000003", 1999), marta, 101),
    new Prestec(new Llibre("Patrons de Disseny", "Erich Gamma",   "978-0000000002", 1994), diego, 105),
    new Prestec(new Revista("Java Magazine",     "REV-2024-03",   42, "Mensual"),          nuria, 140)
);

GestorAvisos gestor = new GestorAvisos();

System.out.println("Amb vencuts el dia 130: " + gestor.ambVencuts(prestecs, 130).size());
System.out.println("Avisos enviats: " + gestor.avisar(prestecs, 130));
System.out.println("Avisos en un segon pas: " + gestor.avisar(prestecs, 130));
System.out.println("Reincidents: " + gestor.reincidents(prestecs, 135).size());
System.out.print("Avisats (ordenats): ");
gestor.avisatsOrdenats().forEach(e -> System.out.print(e.getNom() + "  "));

Amb vencuts el dia 130: 2
AVIS a Marta Ruiz       (EMP-001): te material vencut
AVIS a Diego Alonso     (EMP-002): te material vencut
Avisos enviats: 2
Avisos en un segon pas: 0
Reincidents: 2
Avisats (ordenats): Diego Alonso  Marta Ruiz

Fixa't en el segon pas: zero avisos, perquè la diferència de conjunts ja exclou qui va ser avisat. Amb llistes, això requeriria un bucle imbricat per cada empleat. I observa que la Marta, amb dos préstecs vençuts, rep un avís: el Set deduplica tot sol.

Errors Habituals i Consells

Posar en un Set objectes sense equals/hashCode correctes. Hi entren i no es troben mai, i el conjunt accepta "duplicats". És la mateixa fallada de 05-05: hashCode tria el cubell, equals tria l'element. Si sobreescrius un, sobreescriu l'altre, sobre els mateixos camps.

Mutar un element ja desat. Queda al cubell del hash antic: inabastable, impossible d'eliminar i susceptible de duplicar-se. Fes servir elements immutables, o treu → modifica → torna a posar.

Oblidar copiar abans de retainAll o removeAll. Aquests mètodes modifiquen el conjunt sobre el qual es criden. new HashSet<>(original) abans d'operar, sempre que vulguis conservar l'original.

Dependre de l'ordre d'un HashSet. No n'hi ha cap de garantit i pot canviar entre execucions o en inserir. Fes servir LinkedHashSet per a ordre d'inserció o TreeSet per a ordre natural.

Fer servir un Comparator no total en un TreeSet. Si dos elements diferents comparen a 0, el segon es descarta en silenci. Afegeix sempre un criteri de desempat únic, com la referència o l'identificador.

Esperar que TreeSet faci servir equals. No el fa servir: fa servir compareTo/compare. Un element diferent segons equals pot ser "el mateix" per a l'arbre, i a l'inrevés.

Posar null en un TreeSet. NullPointerException: no es pot comparar null. HashSet sí que n'admet un, però evita'l igualment.

Set.of(...) amb duplicats. Llança IllegalArgumentException en construir-lo. Si esperes duplicats, fes servir new HashSet<>(colleccio) o Set.copyOf(colleccio).

Fer servir List.contains dins d'un bucle. És l'error de rendiment més rendible de corregir de tot el mòdul: converteix la llista a Set una sola vegada i passaràs d'O(n×m) a O(n+m).

Consell: tria Set per semàntica, no per velocitat. Un Set<String> d'ISBN documenta que els ISBN són únics millor que qualsevol comentari, i el compilador i l'estructura ho fan complir. La velocitat és un extra.

Consell: new LinkedHashSet<>(llista) elimina duplicats conservant l'ordre. I new ArrayList<>(new LinkedHashSet<>(llista)) retorna una llista neta, en ordre, en una línia.

Exercicis

Exercici 1: control de catàleg amb conjunts

Escriu AuditoriaCataleg que rebi dos conjunts de referències —les del catàleg intern i les d'un fitxer del proveïdor— i produeixi un informe amb:

Set<String> nomesAlCataleg(): les que tenim i el proveïdor no llista (candidates a baixa).
Set<String> nomesAlProveidor(): les que el proveïdor llista i no tenim (candidates a alta).
Set<String> enTotsDos(): les coincidents.
boolean catalegComplet(): si el catàleg cobreix tot el del proveïdor.
boolean senseRelacio(): si no comparteixen cap referència (fes servir Collections.disjoint).
Set<String> diferenciaSimetrica(): les que són en un o altre però no en tots dos.
String informe(): un resum formatat.

Cap mètode no ha de modificar els conjunts rebuts.

Exercici 2: les tres implementacions i els seus paranys

Escriu DemostracioConjunts amb un main que demostri, imprimint i explicant:

Que HashSet, LinkedHashSet i TreeSet donen ordres diferents amb les mateixes dades.
Que un element sense hashCode correcte permet duplicats en un HashSet.
Que mutar un element desat el fa inabastable i fins i tot duplicable.
Que un Comparator no total fa que un TreeSet descarti elements diferents.
Que Set.of amb duplicats llança IllegalArgumentException (comenta-ho, no ho executis) mentre que new HashSet<>(llista) els ignora.
La diferència de temps entre List.contains i Set.contains amb 100 000 elements.

Exercici 3: etiquetes de materials

Amplia BiblioTech amb un sistema d'etiquetes. Escriu GestorEtiquetes que mantingui un Map<String, Set<String>> (referència del material → conjunt d'etiquetes) i un Map<String, Set<String>> invers (etiqueta → conjunt de referències):

void etiquetar(String referencia, String... etiquetes): fes servir computeIfAbsent i mantén els dos mapes coherents.
Set<String> etiquetesDe(String referencia).
Set<String> materialsAmb(String etiqueta).
Set<String> materialsAmbTotes(String... etiquetes): intersecció.
Set<String> materialsAmbAlguna(String... etiquetes): unió.
Set<String> totesLesEtiquetes(), ordenades alfabèticament.
void desetiquetar(String referencia, String etiqueta), netejant les entrades que quedin buides.

Solucions

Solució 1

package com.nexussoftware.bibliotech.servei;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/** Compara el cataleg intern amb el llistat d'un proveidor. */
public class AuditoriaCataleg {

    private final Set<String> cataleg;
    private final Set<String> proveidor;

    public AuditoriaCataleg(Set<String> cataleg, Set<String> proveidor) {
        // Copies defensives (03-07): ningu no pot alterar les nostres dades des de fora,
        // i nosaltres no alterem les seves.
        this.cataleg   = (cataleg   == null) ? Set.of() : Set.copyOf(cataleg);
        this.proveidor = (proveidor == null) ? Set.of() : Set.copyOf(proveidor);
    }

    /** DIFERENCIA cataleg - proveidor. Treballem sobre una copia. */
    public Set<String> nomesAlCataleg() {
        Set<String> resultat = new HashSet<>(cataleg);
        resultat.removeAll(proveidor);
        return resultat;
    }

    /** DIFERENCIA proveidor - cataleg. Compte: la diferencia NO es simetrica. */
    public Set<String> nomesAlProveidor() {
        Set<String> resultat = new HashSet<>(proveidor);
        resultat.removeAll(cataleg);
        return resultat;
    }

    /** INTERSECCIO. */
    public Set<String> enTotsDos() {
        Set<String> resultat = new HashSet<>(cataleg);
        resultat.retainAll(proveidor);
        return resultat;
    }

    /** SUBCONJUNT: conte el cataleg tot el que ofereix el proveidor? */
    public boolean catalegComplet() {
        return cataleg.containsAll(proveidor);
    }

    /** DISJUNTS: no comparteixen ni una referencia. */
    public boolean senseRelacio() {
        return Collections.disjoint(cataleg, proveidor);
    }

    /** DIFERENCIA SIMETRICA: unio menys interseccio. */
    public Set<String> diferenciaSimetrica() {
        Set<String> unio = new HashSet<>(cataleg);
        unio.addAll(proveidor);
        unio.removeAll(enTotsDos());
        return unio;
    }

    public String informe() {
        StringBuilder sb = new StringBuilder();
        sb.append("=== Auditoria de cataleg ===\n");
        sb.append(String.format("Cataleg intern:     %d referencies%n", cataleg.size()));
        sb.append(String.format("Llistat proveidor:  %d referencies%n", proveidor.size()));
        // TreeSet nomes perque l'informe surti sempre en el mateix ordre
        sb.append(String.format("Coincidents:        %s%n", new TreeSet<>(enTotsDos())));
        sb.append(String.format("Candidates a baixa: %s%n", new TreeSet<>(nomesAlCataleg())));
        sb.append(String.format("Candidates a alta:  %s%n", new TreeSet<>(nomesAlProveidor())));
        sb.append(String.format("Cataleg complet:    %s%n", catalegComplet() ? "si" : "no"));
        sb.append(String.format("Sense relacio:      %s%n", senseRelacio() ? "si" : "no"));
        return sb.toString();
    }
}

Prova:

Set<String> nostre = Set.of("978-0000000001", "978-0000000002", "DVD-0007");
Set<String> seu    = Set.of("978-0000000002", "978-0000000003", "REV-2024-03");

System.out.print(new AuditoriaCataleg(nostre, seu).informe());

=== Auditoria de cataleg ===
Cataleg intern:     3 referencies
Llistat proveidor:  3 referencies
Coincidents:        [978-0000000002]
Candidates a baixa: [978-0000000001, DVD-0007]
Candidates a alta:  [978-0000000003, REV-2024-03]
Cataleg complet:    no
Sense relacio:      no

Dues idees de disseny que transcendeixen l'exercici. La primera: cada mètode copia abans d'operar, perquè removeAll i retainAll són destructius; oblidar-ho destruiria el catàleg a la primera consulta. La segona: el TreeSet d'informe() només serveix perquè la sortida sigui reproduïble; un HashSet donaria el mateix contingut en ordre arbitrari, cosa que fa impossible comparar informes o escriure tests.

I observa el poc que cal escriure. Sense conjunts, nomesAlCataleg seria un bucle imbricat O(n×m); aquí és una crida O(m).

Solució 2

package com.nexussoftware.bibliotech.presentacio;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class DemostracioConjunts {

    // Element SENSE hashCode
    static class EtiquetaTrencada {
        final String nom;
        EtiquetaTrencada(String n) { this.nom = n; }
        @Override public boolean equals(Object o) {
            return (o instanceof EtiquetaTrencada e) && Objects.equals(nom, e.nom);
        }
        @Override public String toString() { return nom; }
    }

    // Element MUTABLE
    static class EtiquetaMutable {
        String nom;
        EtiquetaMutable(String n) { this.nom = n; }
        @Override public boolean equals(Object o) {
            return (o instanceof EtiquetaMutable e) && Objects.equals(nom, e.nom);
        }
        @Override public int hashCode() { return Objects.hash(nom); }
        @Override public String toString() { return nom; }
    }

    record Tarifa(String referencia, double euros) { }

    public static void main(String[] args) {
        ordres();
        senseHashCode();
        mutacio();
        comparadorNoTotal();
        duplicatsEnConstruir();
        rendiment();
    }

    static void ordres() {
        System.out.println("=== 1. Tres implementacions, tres ordres ===");
        List<String> entrada = List.of("Revista", "Llibre", "DVD", "Llibre", "Audiollibre");
        System.out.println("Entrada:       " + entrada + "  (5 elements, un de repetit)");
        System.out.println("HashSet:       " + new HashSet<>(entrada)       + "  ordre impredictible");
        System.out.println("LinkedHashSet: " + new LinkedHashSet<>(entrada) + "  ordre d'insercio");
        System.out.println("TreeSet:       " + new TreeSet<>(entrada)       + "  ordre alfabetic");
        System.out.println("Els tres tenen 4 elements: 'Llibre' es va descartar en els tres.\n");
    }

    static void senseHashCode() {
        System.out.println("=== 2. Element sense hashCode ===");
        Set<EtiquetaTrencada> conjunt = new HashSet<>();
        conjunt.add(new EtiquetaTrencada("java"));
        conjunt.add(new EtiquetaTrencada("java"));   // "igual" segons equals

        System.out.println("size: " + conjunt.size() + "   <- DUPLICATS en un Set");
        System.out.println("contains(nova 'java'): "
                           + conjunt.contains(new EtiquetaTrencada("java")) + "   <- no la troba");
        System.out.println("Causa: hashCode heretat d'Object -> cada instancia va a un");
        System.out.println("cubell diferent i equals no arriba MAI a executar-se.\n");
    }

    static void mutacio() {
        System.out.println("=== 3. Mutar un element desat ===");
        EtiquetaMutable e = new EtiquetaMutable("java");
        Set<EtiquetaMutable> conjunt = new HashSet<>();
        conjunt.add(e);
        System.out.println("contains abans: " + conjunt.contains(e));

        e.nom = "programacio";                       // mutem el que ja hi ha desat

        System.out.println("contains despres: " + conjunt.contains(e) + "   <- perdut");
        System.out.println("remove: " + conjunt.remove(e) + "   <- ni tan sols es pot treure");
        conjunt.add(e);
        System.out.println("size despres de tornar-lo a afegir: " + conjunt.size()
                           + "   <- el MATEIX objecte, dues vegades");
        System.out.println("Correcte: remove -> mutar -> add.\n");
    }

    static void comparadorNoTotal() {
        System.out.println("=== 4. Comparator no total en TreeSet ===");
        // Comparator que nomes mira els euros: dues tarifes diferents amb la mateixa
        // quantitat comparen a 0, i el TreeSet les considera EL MATEIX element.
        Set<Tarifa> dolent = new TreeSet<>(Comparator.comparingDouble(Tarifa::euros));
        dolent.add(new Tarifa("978-0000000001", 0.25));
        dolent.add(new Tarifa("978-0000000002", 0.25));
        System.out.println("Amb comparador parcial: size = " + dolent.size()
                           + "   <- s'ha PERDUT un element");

        Set<Tarifa> bo = new TreeSet<>(
            Comparator.comparingDouble(Tarifa::euros)
                      .thenComparing(Tarifa::referencia));   // desempat UNIC
        bo.add(new Tarifa("978-0000000001", 0.25));
        bo.add(new Tarifa("978-0000000002", 0.25));
        System.out.println("Amb desempat:           size = " + bo.size() + "   <- correcte");
        System.out.println("En TreeSet la unicitat la decideix el COMPARADOR, no equals.\n");
    }

    static void duplicatsEnConstruir() {
        System.out.println("=== 5. Set.of enfront de new HashSet<>(llista) ===");
        List<String> ambRepetits = List.of("Llibre", "Revista", "Llibre");

        // Set.of("Llibre", "Revista", "Llibre");
        //   -> IllegalArgumentException: duplicate element: Llibre
        //   Es intencionat: en un literal escrit a ma, un duplicat es un error.
        System.out.println("Set.of amb duplicats llancaria IllegalArgumentException");

        System.out.println("new HashSet<>(llista): " + new HashSet<>(ambRepetits)
                           + "   <- els ignora en silenci");
        System.out.println("Set.copyOf(llista):    " + Set.copyOf(ambRepetits)
                           + "   <- tambe els ignora\n");
    }

    static void rendiment() {
        System.out.println("=== 6. contains: List enfront de Set ===");
        final int N = 100_000, CONSULTES = 5_000;

        List<String> llista = new ArrayList<>(N);
        Set<String>  conjunt = new HashSet<>((int)(N / 0.75f) + 1);
        for (int i = 0; i < N; i++) {
            String ref = "978-" + String.format("%010d", i);
            llista.add(ref);
            conjunt.add(ref);
        }
        String buscat = "978-" + String.format("%010d", N - 1);    // el pitjor cas: l'ultim

        for (int i = 0; i < 50; i++) { llista.contains(buscat); }  // escalfament

        long t1 = System.nanoTime();
        for (int i = 0; i < CONSULTES; i++) { llista.contains(buscat); }
        long msLlista = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        for (int i = 0; i < CONSULTES; i++) { conjunt.contains(buscat); }
        long msSet = (System.nanoTime() - t2) / 1_000_000;

        System.out.printf("List.contains x%d: %6d ms%n", CONSULTES, msLlista);
        System.out.printf("Set.contains  x%d: %6d ms%n", CONSULTES, msSet);
        System.out.println("La List compara fins a 100.000 vegades; el Set calcula UN cubell.");
    }
}

Els sis apartats expliquen la mateixa història des d'angles diferents: un Set només compleix la seva promesa si els seus elements respecten el contracte. hashCode absent, element mutable o comparador parcial són tres formes de trencar-lo, i totes tres fallen en silenci: no hi ha excepció, només dades duplicades o perdudes. I l'apartat 6 recorda per què val la pena fer-ho bé.

Solució 3

package com.nexussoftware.bibliotech.servei;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * Etiquetatge de materials amb doble index: material -> etiquetes i
 * etiqueta -> materials. Mantenir els dos coherents es el preu de
 * poder consultar en totes dues direccions en O(1).
 */
public class GestorEtiquetes {

    private final Map<String, Set<String>> etiquetesPerMaterial = new HashMap<>();
    private final Map<String, Set<String>> materialsPerEtiqueta = new HashMap<>();

    private static String normalitzar(String s) {
        return (s == null) ? null : s.trim().toLowerCase();
    }

    public void etiquetar(String referencia, String... etiquetes) {
        if (referencia == null || etiquetes == null) { return; }
        for (String bruta : etiquetes) {
            String etiqueta = normalitzar(bruta);
            if (etiqueta == null || etiqueta.isEmpty()) { continue; }

            // computeIfAbsent crea el Set nomes si cal i retorna sempre un de valid
            etiquetesPerMaterial.computeIfAbsent(referencia, r -> new HashSet<>()).add(etiqueta);
            materialsPerEtiqueta.computeIfAbsent(etiqueta, e -> new HashSet<>()).add(referencia);
            // Si l'etiqueta ja hi era, add retorna false i no passa res: la unicitat
            // la garanteix el mateix Set, sense comprovacions.
        }
    }

    public Set<String> etiquetesDe(String referencia) {
        return Set.copyOf(etiquetesPerMaterial.getOrDefault(referencia, Set.of()));
    }

    public Set<String> materialsAmb(String etiqueta) {
        return Set.copyOf(materialsPerEtiqueta.getOrDefault(normalitzar(etiqueta), Set.of()));
    }

    /** INTERSECCIO successiva: els materials que tenen TOTES les etiquetes. */
    public Set<String> materialsAmbTotes(String... etiquetes) {
        if (etiquetes == null || etiquetes.length == 0) { return Set.of(); }

        Set<String> resultat = new HashSet<>(materialsAmb(etiquetes[0]));
        for (int i = 1; i < etiquetes.length; i++) {
            resultat.retainAll(materialsAmb(etiquetes[i]));
            if (resultat.isEmpty()) { break; }         // drecera: ja no pot creixer
        }
        return resultat;
    }

    /** UNIO successiva: els materials que tenen ALGUNA de les etiquetes. */
    public Set<String> materialsAmbAlguna(String... etiquetes) {
        Set<String> resultat = new HashSet<>();
        if (etiquetes == null) { return resultat; }
        for (String e : etiquetes) {
            resultat.addAll(materialsAmb(e));
        }
        return resultat;
    }

    /** TreeSet: sempre en ordre alfabetic, sense ordenar a ma. */
    public Set<String> totesLesEtiquetes() {
        return new TreeSet<>(materialsPerEtiqueta.keySet());
    }

    /** Treu una etiqueta, netejant les entrades que quedin buides a TOTS DOS mapes. */
    public void desetiquetar(String referencia, String etiquetaBruta) {
        String etiqueta = normalitzar(etiquetaBruta);
        if (referencia == null || etiqueta == null) { return; }

        // Retornar null des de computeIfPresent elimina l'entrada del mapa (05-05)
        etiquetesPerMaterial.computeIfPresent(referencia, (r, set) -> {
            set.remove(etiqueta);
            return set.isEmpty() ? null : set;
        });
        materialsPerEtiqueta.computeIfPresent(etiqueta, (e, set) -> {
            set.remove(referencia);
            return set.isEmpty() ? null : set;
        });
    }

    public int materialsEtiquetats() { return etiquetesPerMaterial.size(); }
    public int etiquetesDiferents()  { return materialsPerEtiqueta.size(); }
}

Prova:

GestorEtiquetes g = new GestorEtiquetes();
g.etiquetar("978-0000000001", "java", "bones-practiques", "avancat");
g.etiquetar("978-0000000002", "java", "patrons", "disseny", "avancat");
g.etiquetar("978-0000000003", "refactoritzacio", "disseny", "java");
g.etiquetar("REV-2024-03",    "java", "actualitat");
g.etiquetar("DVD-0007",       "refactoritzacio", "video");

System.out.println("Etiquetes de 978-0000000002: " + new TreeSet<>(g.etiquetesDe("978-0000000002")));
System.out.println("Amb 'java':          " + new TreeSet<>(g.materialsAmb("java")));
System.out.println("Amb java I avancat:  " + new TreeSet<>(g.materialsAmbTotes("java", "avancat")));
System.out.println("Amb video O patrons:" + new TreeSet<>(g.materialsAmbAlguna("video", "patrons")));
System.out.println("Totes les etiquetes: " + g.totesLesEtiquetes());

g.desetiquetar("DVD-0007", "video");
System.out.println("Despres de treure 'video': " + g.totesLesEtiquetes());

Etiquetes de 978-0000000002: [avancat, disseny, java, patrons]
Amb 'java':          [978-0000000001, 978-0000000002, 978-0000000003, REV-2024-03]
Amb java I avancat:  [978-0000000001, 978-0000000002]
Amb video O patrons:[978-0000000002, DVD-0007]
Totes les etiquetes: [actualitat, avancat, bones-practiques, disseny, java, patrons, refactoritzacio, video]
Despres de treure 'video': [actualitat, avancat, bones-practiques, disseny, java, patrons, refactoritzacio]

Aquest exercici ajunta tot el mòdul fins aquí. computeIfAbsent de 05-05 construeix els mapes de conjunts sense ni una sola comprovació de null. El Set intern garanteix que etiquetar dues vegades amb el mateix no duplica res, sense que calgui comprovar-ho. retainAll i addAll implementen cerques "I" i "O" que amb llistes serien bucles imbricats. El TreeSet de totesLesEtiquetes manté l'ordre alfabètic sense ordenar res. I computeIfPresent retornant null neteja les entrades òrfenes, evitant que els mapes s'omplin de conjunts buits.

El preu de tenir dos índexs és mantenir-los coherents: cada etiquetar i cada desetiquetar toca els dos mapes. És un compromís deliberat —memòria i disciplina a canvi de consultes O(1) en totes dues direccions— i és exactament la mena de decisió que es pren diàriament en el disseny de sistemes reals.

Conclusió

Ja domines l'altra gran estructura basada en hash, i t'ha costat poc perquè HashSet és literalment un HashMap amb valors ficticis: ho has vist al seu codi font, amb el seu camp map i el seu sentinella PRESENT. D'aquesta identitat es dedueix tot sense aprendre res de nou: O(1) a add, contains i remove; sense ordre garantit; un sol null; factor de càrrega, rehash i conversió de cubell a arbre; i —crucialment— els mateixos requisits sobre equals i hashCode que les claus d'un mapa, amb les mateixes conseqüències quan s'incompleixen: elements que hi entren i no es troben, i "duplicats" en un conjunt que se suposa sense duplicats.

Saps que un Set no afegeix mètodes a Collection sinó contracte, i que l'absència de get(i) no és una mancança: un conjunt no té posicions. Has après a explotar el detall que gairebé ningú no mira: add retorna false si l'element ja hi era, cosa que resol en una línia, i amb la meitat de feina que contains + add, la detecció de duplicats, el processament únic per clau, el recompte d'elements diferents i la prevenció de cicles.

Manegues l'àlgebra de conjunts amb soltesa: addAll per a la unió, retainAll per a la intersecció, removeAll per a la diferència —que no és simètrica—, containsAll per al subconjunt i Collections.disjoint per comprovar que no comparteixen res; amb la diferència simètrica composta a partir de les anteriors. I tens gravat l'avís que evita l'error més freqüent: les tres primeres modifiquen el conjunt sobre el qual s'invoquen, així que sempre es treballa sobre una còpia.

Coneixes les tres implementacions i el seu criteri d'elecció: HashSet per defecte, LinkedHashSet per a ordre reproduïble —i per eliminar duplicats conservant l'ordre original en una línia—, i TreeSet quan necessitis ordre permanent o navegació, amb tot el seu arsenal de first, last, headSet, tailSet, subSet, ceiling, floor, higher, lower, pollFirst i descendingSet. I saps el que més s'oblida de TreeSet: la unicitat la decideix el comparador, no equals, de manera que un Comparator sense criteri de desempat únic descarta elements diferents en silenci.

Entens el perill de mutar un element ja desat —queda al cubell del hash antic, no es troba, no es pot eliminar i es pot duplicar— i la seva única solució correcta: treure, modificar, tornar a posar. Coneixes els conjunts immutables, amb la particularitat que Set.of rebutja duplicats amb IllegalArgumentException mentre que Set.copyOf els ignora. I has vist amb números l'optimització més rendible de tot el mòdul: si consultaràs pertinença més d'unes poques vegades, converteix la llista a Set i passaràs d'O(n×m) a O(n+m).

BiblioTech té ara un ControlDuplicats que rebutja altes repetides en O(1) recolzant-se únicament en el boolean d'add, i un GestorAvisos que resol amb tres operacions de conjunt —diferència, intersecció i diferència inversa— el que amb llistes serien bucles imbricats: a qui cal avisar, qui reincideix i a qui se li pot retirar l'avís. Un empleat amb tres préstecs vençuts rep exactament un avís, i un segon pas no n'envia cap.

A la lliçó següent, Cua i Deque, canvies de família. Fins ara les col·leccions responien a "hi és?" i "on és?"; ara respondran a "a qui li toca?". Veuràs la interfície Queue amb la seva semàntica FIFO i les seves dues famílies de mètodes —la que llança excepció i la que retorna un valor especial, i quan fer servir cadascuna—, el Deque com a cua de doble extrem, ArrayDeque amb la seva memòria intermèdia circular i per què és l'opció per defecte avui (i per què rebutja els null), la PriorityQueue amb el seu monticle binari i la sorpresa que el seu iterador no recorre en ordre de prioritat, el patró productor-consumidor i el recorregut en amplada. I a BiblioTech, la CuaReserves que vas escriure amb LinkedList es reescriurà amb Deque, i apareixerà una PriorityQueue<Prestec> que atén sempre primer el préstec amb més dies de retard.

HashSet

Contingut

Què és un conjunt

La interfície Set i la seva API

HashSet és un HashMap disfressat

add retorna boolean, i això ho canvia tot

Operacions de conjunt

Unió: addAll

Intersecció: retainAll

Diferència: removeAll

Subconjunt: containsAll

Diferència simètrica

Taula resum

HashSet, LinkedHashSet i TreeSet

TreeSet, SortedSet i NavigableSet

Ordre natural o Comparator

El perill de mutar un element desat

Conjunts immutables

contains en un Set enfront d'una List

Aplicació a BiblioTech

Set<String> d'ISBN catalogats

Creuament de conjunts: vençuts enfront d'avisats

Errors Habituals i Consells

Exercicis

Exercici 1: control de catàleg amb conjunts

Exercici 2: les tres implementacions i els seus paranys

Exercici 3: etiquetes de materials

Solucions

Solució 1

Solució 2

Solució 3

Conclusió

Curs de Programació en Java

Mòdul 1: Introducció a Java

Mòdul 2: Flux de control

Mòdul 3: Programació orientada a objectes

Mòdul 4: Programació orientada a objectes avançada

Mòdul 5: Estructures de dades i col·leccions

Mòdul 6: Gestió d'excepcions

Mòdul 7: Entrada/sortida de fitxers

Mòdul 8: Multifil i concurrència

Mòdul 9: Xarxes

Mòdul 10: Temes avançats

Mòdul 11: Frameworks i llibreries de Java

Mòdul 12: Construcció d'aplicacions del món real