El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

Llegas al cierre del módulo con todas las piezas sobre la mesa. Sabes guardar elementos en listas, garantizar unicidad con conjuntos, indexar por clave con mapas y modelar políticas de proceso con colas y pilas. Falta la operación que atraviesa todas ellas y que aparece en prácticamente cualquier programa: poner las cosas en orden y encontrarlas.

Ordenar y buscar no son temas menores. La ordenación es probablemente la operación algorítmica más estudiada de la historia de la informática, y la elección entre búsqueda lineal, búsqueda binaria y acceso por clave es una de las decisiones que más impacto tiene en el rendimiento de un sistema real. En esta lección verás el contrato completo de Comparable —incluido el error de restar enteros que desborda silenciosamente—, todo el arsenal de Comparator retomado desde 04-06, las cuatro estrategias de ordenación con su criterio de elección, qué significa que una ordenación sea estable y por qué eso es lo que permite ordenar por criterios sucesivos, y qué algoritmos usa Java realmente por debajo.

Después, la búsqueda: lineal, binaria y por clave, con la tabla de complejidades que decide entre ellas y la interpretación exacta del valor negativo que devuelve binarySearch. Y al final, el balance del módulo: BiblioTech con catálogo indexado y ordenable, informes, cola de reservas y pila de deshacer... y la lista honesta de lo que sigue siendo frágil, que es exactamente el temario del módulo 6.

Contenido

Orden natural con Comparable
El contrato de compareTo
El error de restar enteros
Coherencia con equals y qué se rompe sin ella
Comparator: orden externo y múltiple
El catálogo de métodos de Comparator
Las cuatro estrategias de ordenación
Estabilidad y ordenación por criterios sucesivos
Qué algoritmo usa Java realmente
Búsqueda: lineal, binaria y por clave
binarySearch y su valor negativo
Utilidades de Collections
Rendimiento: ordenar una vez, buscar muchas
Cierre del módulo: el estado de BiblioTech
Errores Comunes y Consejos
Ejercicios

Orden natural con `Comparable`

Una clase declara su orden natural implementando la interfaz Comparable:

public interface Comparable<T> {
    int compareTo(T otro);
}

Un solo método, que devuelve un int cuyo signo —no su valor— es lo que importa:

Resultado	Significado
Negativo	`this` va antes que `otro`
Cero	Son equivalentes en cuanto al orden
Positivo	`this` va después que `otro`

Ya usaste Comparable en 04-07 al hacer que Ficha se ordenara por título. Aquí está la implementación completa y correcta:

package com.nexussoftware.bibliotech.dominio;

/** Ficha bibliografica con orden natural por titulo. */
public record Ficha(String titulo, String autor, int anio) implements Comparable<Ficha> {

    public Ficha {
        if (titulo == null || titulo.isBlank()) { titulo = "Sin titulo"; }
        if (autor  == null || autor.isBlank())  { autor  = "Desconocido"; }
        if (anio < 1450 || anio > 2100)         { anio   = 0; }
    }

    /** Orden natural: por titulo alfabetico. */
    @Override
    public int compareTo(Ficha otra) {
        return this.titulo.compareTo(otra.titulo);   // String ya implementa Comparable
    }
}

Y así se usa, sin decirle a nadie cómo ordenar:

List<Ficha> fichas = new ArrayList<>(List.of(
    new Ficha("Refactorizacion",    "Martin Fowler", 1999),
    new Ficha("Java Efectivo",      "Joshua Bloch",  2018),
    new Ficha("Patrones de Diseno", "Erich Gamma",   1994)));

fichas.sort(null);                         // null = orden natural
Collections.sort(fichas);                  // equivalente
System.out.println(fichas.get(0).titulo()); // Java Efectivo

TreeSet<Ficha> ordenadas = new TreeSet<>(fichas);        // el TreeSet usa compareTo
Ficha minima = Collections.min(fichas);                  // tambien

Muchas clases del JDK ya lo implementan: String (orden lexicográfico), todos los envoltorios numéricos, Character, Boolean, los enum (por su ordinal, es decir, por el orden de declaración) y las clases de java.time (10-05).

Un Comparable bien implementado abre las puertas a todo el Framework: sort sin argumentos, TreeSet, TreeMap, PriorityQueue, Collections.max, Collections.min y binarySearch.

Ahora bien, Comparable tiene una limitación importante: solo puedes definir un orden natural por clase. Si necesitas ordenar materiales por título, por tarifa y por tipo, necesitas Comparator. Y hay una pregunta que conviene hacerse antes de implementar Comparable: ¿existe realmente un orden que sea el natural para este tipo? Para un String o un número, sí. Para un Material, discutible. Para un Prestamo, probablemente no. Si dudas, no implementes Comparable: usa comparadores.

El contrato de `compareTo`

compareTo tiene un contrato tan estricto como el de equals de 03-09, y romperlo produce comportamientos impredecibles en las colecciones ordenadas.

1. Antisimetría. sgn(a.compareTo(b)) == -sgn(b.compareTo(a)) para todos los a y b. Si A va antes que B, B va después que A. Y si a.compareTo(b) lanza una excepción, b.compareTo(a) también debe lanzarla.

2. Transitividad. Si a.compareTo(b) > 0 y b.compareTo(c) > 0, entonces a.compareTo(c) > 0. Si A va después de B, y B después de C, A va después de C. Sin esta propiedad, la ordenación puede entrar en bucle o lanzar IllegalArgumentException: Comparison method violates its general contract!, un error que sale de TimSort al detectar la incoherencia.

3. Consistencia con la igualdad de orden. Si a.compareTo(b) == 0, entonces sgn(a.compareTo(c)) == sgn(b.compareTo(c)) para todo c. Los elementos "empatados" deben comportarse igual frente a terceros.

4. Coherencia con equals (recomendada, no obligatoria). a.compareTo(b) == 0 debería implicar a.equals(b). Es la única que no exige el compilador, y la que más problemas causa cuando se ignora. Tiene su apartado propio.

5. null no participa. a.compareTo(null) debe lanzar NullPointerException, no devolver un valor. null no tiene posición en un orden.

Ejemplos de violaciones que compilan perfectamente:

// VIOLA la antisimetria: siempre dice "voy antes"
@Override public int compareTo(Ficha otra) { return -1; }

// VIOLA la transitividad: el orden depende de algo que cambia
@Override public int compareTo(Ficha otra) {
    return Double.compare(Math.random(), 0.5);
}

// VIOLA la consistencia: compara campos distintos segun el caso
@Override public int compareTo(Ficha otra) {
    if (this.anio > 2000) { return this.titulo.compareTo(otra.titulo); }
    return Integer.compare(this.anio, otra.anio);
}

La tercera es la más peligrosa porque parece razonable. Al ordenar una lista con TimSort, el algoritmo asume transitividad para descartar comparaciones; si el criterio cambia según el elemento, el resultado puede ser un orden incorrecto o directamente una excepción en medio del sort.

El error de restar enteros

Este es el error clásico de compareTo, y aparece en muchísimo código en producción:

// MAL: parece correcto y funciona... hasta que no
@Override
public int compareTo(Ficha otra) {
    return this.anio - otra.anio;
}

El razonamiento es tentador: si this.anio es mayor, la resta es positiva; si es menor, negativa; si son iguales, cero. Y funciona con años entre 1450 y 2100.

El problema es el desbordamiento (overflow). Un int va de −2 147 483 648 a 2 147 483 647. Si la resta se sale de ese rango, el resultado da la vuelta y cambia de signo:

int a = 2_000_000_000;
int b = -2_000_000_000;

System.out.println(a - b);                // -294967296   <- NEGATIVO, y a > b !
System.out.println(Integer.compare(a, b)); // 1            <- correcto

a es claramente mayor que b, pero la resta desborda y devuelve un negativo, así que compareTo afirma lo contrario. El resultado es una ordenación silenciosamente incorrecta, un TreeSet que pierde elementos y un binarySearch que no encuentra lo que hay.

La solución es no restar nunca. Usa los métodos estáticos de comparación, que están escritos precisamente para esto:

Integer.compare(a, b)      // para int
Long.compare(a, b)         // para long
Double.compare(a, b)       // para double: ademas trata bien NaN y -0.0
Boolean.compare(a, b)      // false < true
Character.compare(a, b)

// BIEN
@Override
public int compareTo(Ficha otra) {
    return Integer.compare(this.anio, otra.anio);
}

El caso de Double merece mención aparte. Restar dobles tiene un problema adicional al desbordamiento: la resta de dos dobles muy cercanos puede dar 0.0 sin que sean iguales, y además Double.compare maneja correctamente NaN y la distinción entre 0.0 y -0.0, cosa que una resta no hace.

// MAL
return (int) (this.tarifa - otra.tarifa);    // 0.25 - 0.10 = 0.15 -> (int) 0 -> "iguales"!

// BIEN
return Double.compare(this.tarifa, otra.tarifa);

Ese ejemplo es especialmente insidioso: el casting a int trunca cualquier diferencia menor que 1, así que todas las tarifas de BiblioTech se considerarían iguales.

Regla sin excepciones: nunca restes para comparar. Usa siempre Tipo.compare(a, b).

Coherencia con `equals` y qué se rompe sin ella

Ya lo viste de pasada en 05-06 con TreeSet; aquí está el problema completo.

Se dice que un orden es coherente con equals cuando a.compareTo(b) == 0 si y solo si a.equals(b). Es decir: dos elementos empatan en el orden exactamente cuando son iguales.

Cuando esa coherencia se rompe, las colecciones ordenadas se comportan de forma inesperada, porque TreeSet y TreeMap usan compareTo, no equals, para decidir la unicidad.

package com.nexussoftware.bibliotech.dominio;

/** Ficha con orden natural por ANIO: incoherente con equals. */
record FichaPorAnio(String titulo, String autor, int anio)
        implements Comparable<FichaPorAnio> {

    @Override
    public int compareTo(FichaPorAnio otra) {
        return Integer.compare(this.anio, otra.anio);   // solo el anio
    }
}

FichaPorAnio a = new FichaPorAnio("Java Efectivo",      "Joshua Bloch", 2018);
FichaPorAnio b = new FichaPorAnio("Patrones de Diseno", "Erich Gamma",  2018);

System.out.println(a.equals(b));        // false: son fichas DISTINTAS
System.out.println(a.compareTo(b));     // 0:     pero EMPATAN en el orden

// En una List no pasa nada
List<FichaPorAnio> lista = new ArrayList<>(List.of(a, b));
System.out.println(lista.size());       // 2   correcto

// En un TreeSet, si
TreeSet<FichaPorAnio> conjunto = new TreeSet<>(List.of(a, b));
System.out.println(conjunto.size());    // 1   <-- SE PERDIO UNA FICHA

// Y contains miente
System.out.println(conjunto.contains(b));   // true, aunque b no este dentro

Se ha perdido un elemento en silencio. El TreeSet preguntó compareTo, obtuvo 0 y concluyó que b ya estaba.

Lo mismo con TreeMap:

TreeMap<FichaPorAnio, String> mapa = new TreeMap<>();
mapa.put(a, "Estanteria A-3");
mapa.put(b, "Estanteria B-1");
System.out.println(mapa.size());      // 1: b SUSTITUYO a a
System.out.println(mapa.get(a));      // Estanteria B-1  <-- valor equivocado

Compara con lo que pasa en las estructuras basadas en hash:

Colección	Decide la unicidad con	Ficha por año incoherente
`List`	Nada: admite duplicados	2 elementos, correcto
`HashSet` / `HashMap`	`equals` + `hashCode`	2 elementos, correcto
`TreeSet` / `TreeMap`	`compareTo` / `compare`	1 elemento: se pierde
`PriorityQueue`	Nada: admite duplicados	2 elementos, pero orden arbitrario entre ellos

La solución es siempre la misma: añadir criterios de desempate hasta que el orden sea total, es decir, hasta que solo empaten los elementos realmente iguales.

@Override
public int compareTo(FichaPorAnio otra) {
    int porAnio = Integer.compare(this.anio, otra.anio);
    if (porAnio != 0) { return porAnio; }
    int porTitulo = this.titulo.compareTo(otra.titulo);
    if (porTitulo != 0) { return porTitulo; }
    return this.autor.compareTo(otra.autor);    // los tres campos: coherente con equals
}

O, mucho más legible, con Comparator (apartado siguiente):

private static final Comparator<FichaPorAnio> ORDEN =
    Comparator.comparingInt(FichaPorAnio::anio)
              .thenComparing(FichaPorAnio::titulo)
              .thenComparing(FichaPorAnio::autor);

@Override
public int compareTo(FichaPorAnio otra) { return ORDEN.compare(this, otra); }

Y el consejo de documentación: si tu orden natural no es coherente con equals a propósito, dilo en el Javadoc. BigDecimal es el ejemplo canónico del JDK: new BigDecimal("1.0").equals(new BigDecimal("1.00")) es false pero compareTo devuelve 0, y por eso un TreeSet<BigDecimal> se comporta distinto de un HashSet<BigDecimal>.

`Comparator`: orden externo y múltiple

Comparator define un orden desde fuera de la clase, y resuelve las dos limitaciones de Comparable: puedes tener tantos como quieras, y funcionan con clases que no controlas.

public interface Comparator<T> {
    int compare(T a, T b);
}

Es una interfaz funcional (04-06), así que admite las tres formas que ya conoces:

// 1. Clase anonima: la forma clasica (04-04)
Comparator<Material> porTitulo = new Comparator<Material>() {
    @Override public int compare(Material a, Material b) {
        return a.getTitulo().compareTo(b.getTitulo());
    }
};

// 2. Lambda (04-05)
Comparator<Material> porTitulo2 = (a, b) -> a.getTitulo().compareTo(b.getTitulo());

// 3. Comparator.comparing con referencia a metodo: la forma moderna (04-06)
Comparator<Material> porTitulo3 = Comparator.comparing(Material::getTitulo);

Las tres hacen lo mismo. Usa siempre la tercera: es más corta, más legible y menos propensa a errores, porque no escribes la comparación a mano.

El catálogo de métodos de `Comparator`

Retomamos y completamos lo de 04-06.

Construcción

Comparator.comparing(Material::getTitulo)                    // por una clave Comparable
Comparator.comparingInt(Prestamo::getDiaPrestamo)            // clave int: SIN autoboxing
Comparator.comparingLong(Registro::getMarcaTiempo)           // clave long
Comparator.comparingDouble(Material::getTarifaDiaria)        // clave double
Comparator.naturalOrder()                                    // el orden natural del tipo
Comparator.reverseOrder()                                    // el orden natural invertido

Por qué comparingInt y no comparing. Comparator.comparing(Material::getDiasPrestamo) funciona, pero el extractor devuelve int y la firma espera un Comparable, así que cada llamada hace autoboxing: crea un Integer por comparación. Ordenar un millón de elementos implica del orden de veinte millones de comparaciones, y por tanto cuarenta millones de objetos temporales. comparingInt acepta un ToIntFunction y compara primitivos directamente.

Regla: si la clave es int, long o double, usa la variante especializada.

Composición

Comparator<Material> criterio =
    Comparator.comparing(Material::getTipo)                  // primero por tipo
              .thenComparing(Material::getTitulo)            // a igualdad, por titulo
              .thenComparingDouble(Material::getTarifaDiaria); // y luego por tarifa

thenComparing solo se consulta cuando el anterior devuelve 0. Es exactamente el mecanismo del desempate del apartado 4, escrito de forma declarativa.

Y tiene variantes especializadas por la misma razón que comparing: thenComparingInt, thenComparingLong, thenComparingDouble.

Inversión

Comparator<Material> caroPrimero = Comparator.comparingDouble(Material::getTarifaDiaria)
                                             .reversed();

Cuidado con dónde colocas reversed(): invierte todo lo compuesto hasta ese punto, no solo lo último.

// Invierte AMBOS criterios: tipo descendente y, a igualdad, titulo descendente
Comparator.comparing(Material::getTipo)
          .thenComparing(Material::getTitulo)
          .reversed();

// Invierte SOLO el titulo: tipo ascendente, titulo descendente
Comparator.comparing(Material::getTipo)
          .thenComparing(Material::getTitulo, Comparator.reverseOrder());

La segunda forma —thenComparing(extractor, comparadorDeLaClave)— es la que necesitas cuando cada criterio lleva su propia dirección. Es un error muy frecuente y silencioso.

Nulos

Comparator<Material> seguro = Comparator.nullsFirst(Comparator.comparing(Material::getTitulo));
Comparator<Material> alFinal = Comparator.nullsLast(Comparator.comparing(Material::getTitulo));

nullsFirst y nullsLast envuelven un comparador para que acepte elementos null, colocándolos al principio o al final. Sin ellos, un solo null en la lista lanza NullPointerException en mitad del sort.

Y si lo que puede ser null es la clave, no el elemento:

Comparator<Material> porAutor = Comparator.comparing(
    m -> ((Libro) m).getAutor(),
    Comparator.nullsLast(Comparator.naturalOrder()));

Tabla resumen

Método	Qué hace
`comparing(f)`	Ordena por la clave que extrae `f`
`comparingInt/Long/Double(f)`	Igual, sin autoboxing. Úsalos si la clave es primitiva
`thenComparing(f)`	Desempate por otra clave
`thenComparing(f, cmp)`	Desempate con su propia dirección
`reversed()`	Invierte todo lo acumulado hasta ahí
`naturalOrder()` / `reverseOrder()`	El orden natural del tipo, directo o invertido
`nullsFirst(cmp)` / `nullsLast(cmp)`	Tolera elementos `null`

Los comparadores de uso frecuente conviene declararlos como constantes:

public final class OrdenesMaterial {
    public static final Comparator<Material> POR_TITULO =
        Comparator.comparing(Material::getTitulo);
    public static final Comparator<Material> POR_TIPO_Y_TITULO =
        Comparator.comparing(Material::getTipo).thenComparing(Material::getTitulo);
    public static final Comparator<Material> POR_TARIFA_DESC =
        Comparator.comparingDouble(Material::getTarifaDiaria).reversed()
                  .thenComparing(Material::getReferencia);   // desempate para orden total
    private OrdenesMaterial() { }
}

catalogo.ordenar(OrdenesMaterial.POR_TIPO_Y_TITULO);

Además de legible, evita crear un comparador nuevo en cada llamada.

Las cuatro estrategias de ordenación

Estrategia	Cómo	Coste	Cuándo
`List.sort(cmp)`	En el sitio, sobre la lista	O(n log n)	Por defecto con listas
`Collections.sort(lista)`	En el sitio, orden natural	O(n log n)	Compatibilidad; prefiere `List.sort`
`Arrays.sort(array)`	En el sitio, sobre un array	O(n log n)	Cuando trabajas con arrays
Colección ordenada	Se mantiene sola	O(log n) por inserción	Cuando el orden debe estar siempre

// 1. List.sort: el metodo propio de la interfaz. LA OPCION POR DEFECTO
catalogo.sort(Comparator.comparing(Material::getTitulo));
catalogo.sort(null);                                    // orden natural

// 2. Collections.sort: anterior a Java 8, hace lo mismo
Collections.sort(fichas);                               // orden natural
Collections.sort(catalogo, Comparator.comparing(Material::getTitulo));

// 3. Arrays.sort
Material[] array = catalogo.toArray(new Material[0]);
Arrays.sort(array, Comparator.comparing(Material::getTitulo));
Arrays.sort(array, 0, 10, comparador);                  // solo un rango

// 4. Colecciones que se mantienen ordenadas
TreeSet<Ficha> siempreOrdenadas = new TreeSet<>();       // por compareTo
TreeMap<String, Material> porClave = new TreeMap<>();    // claves ordenadas
PriorityQueue<Prestamo> porUrgencia = new PriorityQueue<>(comparador);  // solo la cabeza

El criterio de elección

La pregunta decisiva es cuántas veces vas a necesitar el orden:

Situación	Estrategia
Ordenar una vez para mostrar	`List.sort`
Ordenar por criterios distintos según el momento	`List.sort` con varios comparadores
Los datos deben estar siempre ordenados y se consultan a menudo	`TreeSet` / `TreeMap`
Consultas por rango (`headSet`, `subMap`, `floorKey`)	`TreeSet` / `TreeMap`
Solo necesitas "el siguiente más prioritario", nunca la lista completa	`PriorityQueue`
Insertas muchas veces y ordenas pocas	`ArrayList` + `sort` al final
Insertas pocas veces y consultas ordenado muchas	`TreeSet`

Un análisis de costes para n inserciones:

ArrayList + sort al final: n inserciones O(1) + una ordenación O(n log n) = O(n log n) total.
TreeSet: n inserciones O(log n) = O(n log n) total.

Son la misma complejidad, pero las constantes favorecen claramente al ArrayList: un sort sobre memoria contigua es mucho más rápido que n inserciones en un árbol con nodos dispersos. Si solo necesitas el orden al final, ArrayList + sort gana. El TreeSet gana cuando el orden debe estar disponible entre inserciones, o cuando necesitas sus operaciones de rango.

Estabilidad y ordenación por criterios sucesivos

Una ordenación es estable si los elementos que empatan conservan su orden relativo original.

List<Ficha> fichas = new ArrayList<>(List.of(
    new Ficha("Refactorizacion",    "Martin Fowler", 1999),
    new Ficha("Java Efectivo",      "Joshua Bloch",  2018),
    new Ficha("Patrones de Diseno", "Erich Gamma",   1994),
    new Ficha("Codigo Limpio",      "Robert Martin", 2008)));

// Primero por autor
fichas.sort(Comparator.comparing(Ficha::autor));
// Luego por anio
fichas.sort(Comparator.comparingInt(Ficha::anio));

Con una ordenación estable, tras el segundo sort las fichas del mismo año siguen ordenadas por autor. Con una inestable, ese orden se habría perdido.

Java garantiza que Collections.sort, List.sort y Arrays.sort sobre objetos son estables. Sobre primitivos (int[], double[]) no, y no importa: dos int iguales son indistinguibles, así que la estabilidad carece de sentido.

Esa garantía permite la técnica de ordenación por pasadas sucesivas: ordenar por el criterio menos importante primero y por el más importante al final.

// Estrategia A: pasadas sucesivas (del criterio MENOS importante al MAS importante)
catalogo.sort(Comparator.comparing(Material::getTitulo));      // secundario
catalogo.sort(Comparator.comparing(Material::getTipo));        // primario

// Estrategia B: un comparador compuesto
catalogo.sort(Comparator.comparing(Material::getTipo)
                        .thenComparing(Material::getTitulo));

Ambas dan el mismo resultado, pero prefiere siempre la B: hace una sola pasada en lugar de dos, expresa la intención de forma directa y no depende de que el lector recuerde que el orden de las pasadas es inverso a la prioridad.

La estrategia A sigue siendo útil en un caso: interfaces interactivas. Cuando el usuario pulsa "ordenar por tipo" sobre una tabla ya ordenada por título, la estabilidad hace que el resultado sea "por tipo y, dentro de cada tipo, por título" —justo lo que espera— sin que el programa tenga que recordar el criterio anterior.

Qué algoritmo usa Java realmente

Java usa dos algoritmos distintos, y la elección revela una decisión de diseño interesante.

TimSort, para objetos

Collections.sort, List.sort y Arrays.sort(Object[]) usan TimSort, un algoritmo híbrido creado por Tim Peters para Python y adoptado por Java 7.

Su idea central: los datos reales rara vez están completamente desordenados. Suelen contener tramos ya ordenados —listas parcialmente actualizadas, datos que llegan casi en orden, resultados de una ordenación previa—. TimSort detecta esos tramos, llamados runs, los extiende y los fusiona.

Recorre el array buscando tramos ya ordenados (ascendentes o descendentes; los descendentes los invierte).
Si un tramo es corto, lo extiende con ordenación por inserción, que es muy rápida en tramos pequeños.
Fusiona los tramos por parejas, como en la ordenación por mezcla (merge sort).

Caso	Complejidad
Mejor caso (ya ordenado)	O(n)
Caso medio	O(n log n)
Peor caso	O(n log n)
Memoria adicional	O(n)
Estable	Sí

Ese O(n) en el mejor caso es su gran virtud: reordenar una lista casi ordenada es prácticamente gratis.

TimSort es también quien lanza el famoso IllegalArgumentException: Comparison method violates its general contract!. No es un capricho: al fusionar tramos, el algoritmo detecta que las comparaciones son incoherentes y prefiere fallar a producir un resultado incorrecto. Si ves ese error, tu comparador viola el contrato del apartado 2.

Quicksort de doble pivote, para primitivos

Arrays.sort(int[]), Arrays.sort(double[]) y demás usan dual-pivot quicksort, una variante de quicksort con dos pivotes que divide el array en tres partes en lugar de dos.

Caso	Complejidad
Mejor y medio	O(n log n)
Peor caso	O(n²) (con entradas adversas, muy improbable)
Memoria adicional	O(log n)
Estable	No

Por qué dos algoritmos

	Objetos (TimSort)	Primitivos (quicksort)
Coste de comparar	Alto: llamada a `compareTo`/`compare`	Bajo: una instrucción de CPU
Coste de mover	Alto: mover referencias, tocar caché	Bajo: mover un valor
¿Importa la estabilidad?	Sí: dos objetos "iguales" son distinguibles	No: dos `int` iguales son idénticos
Memoria adicional	Aceptable	Se prefiere mínima
Elección	TimSort: minimiza comparaciones, estable	Quicksort: en el sitio, mínima memoria

Con objetos, cada comparación puede ser cara y la estabilidad importa: TimSort minimiza comparaciones aprovechando el orden preexistente. Con primitivos, comparar es trivial, la estabilidad no significa nada y lo que interesa es no gastar memoria: quicksort ordena en el sitio.

En la práctica no necesitas elegir: Java lo hace por ti. Pero conocerlo explica dos cosas que sí verás: por qué reordenar una lista casi ordenada es tan rápido, y de dónde sale esa IllegalArgumentException.

Búsqueda: lineal, binaria y por clave

Tres estrategias, tres complejidades y un criterio claro.

Búsqueda lineal

Recorrer comparando hasta encontrar. Es lo que hacen contains, indexOf y cualquier bucle propio.

boolean hay = catalogo.contains(material);           // O(n), usa equals
int posicion = catalogo.indexOf(material);           // O(n)

Material encontrado = null;                          // busqueda por criterio
for (Material m : catalogo) {
    if (m.getReferencia().equals("978-0000000001")) { encontrado = m; break; }
}

Ventajas	Inconvenientes
No requiere orden previo	O(n)
Funciona con cualquier criterio	Se degrada con el tamaño
Sin memoria adicional

Búsqueda binaria

Sobre una colección ordenada: mirar el elemento central, descartar la mitad que no puede contenerlo y repetir.

List<Ficha> fichas = new ArrayList<>(...);
fichas.sort(null);                                   // OBLIGATORIO ordenar primero

int pos = Collections.binarySearch(fichas, buscada);
int pos2 = Collections.binarySearch(catalogo, sonda,
                                    Comparator.comparing(Material::getReferencia));

int pos3 = Arrays.binarySearch(array, buscado);

Con un millón de elementos, unas 20 comparaciones en lugar de un millón.

Ventajas	Inconvenientes
O(log n)	Exige orden previo por el mismo criterio
Devuelve el punto de inserción si no está	Ordenar cuesta O(n log n)
Sin memoria adicional	Sobre `LinkedList` es O(n) por el acceso indexado

Ese último punto merece atención: Collections.binarySearch comprueba si la lista implementa RandomAccess (05-03). Si no —caso de LinkedList—, cambia a una estrategia con iterador, y el resultado es peor que una búsqueda lineal. Búsqueda binaria solo sobre ArrayList o arrays.

Búsqueda por clave

Un Map o un Set basado en hash, como viste en 05-05 y 05-06.

Map<String, Material> indice = new HashMap<>();
Material m = indice.get("978-0000000001");           // O(1)
boolean existe = referencias.contains("978-0000000001");  // O(1)

Ventajas	Inconvenientes
O(1)	Memoria adicional para el índice
No requiere orden	Requiere `equals`/`hashCode` correctos
Escala perfectamente	Solo sirve para la clave indexada

Tabla de decisión

Situación	Estrategia	Coste
Buscas una vez, colección pequeña	Lineal	O(n)
Buscas por un criterio arbitrario y cambiante	Lineal	O(n)
Buscas muchas veces por la misma clave	`Map`/`Set`	O(1)
Necesitas orden y búsquedas	`TreeMap`/`TreeSet`	O(log n)
La lista ya está ordenada por ese criterio	`binarySearch`	O(log n)
Buscas rangos ("todos entre A y B")	`TreeSet.subSet`	O(log n) + tamaño del rango

Y la regla práctica: si vas a buscar más de unas pocas veces por la misma clave, construye un índice. El coste de crear el HashMap (O(n), una vez) se amortiza casi de inmediato, como viste en 05-06.

`binarySearch` y su valor negativo

Collections.binarySearch y Arrays.binarySearch devuelven:

Si lo encuentran: el índice del elemento, un valor ≥ 0.
Si no lo encuentran: -(punto de inserción) - 1, un valor negativo.

El punto de inserción es la posición donde habría que insertar el elemento para mantener el orden.

List<Integer> ordenada = new ArrayList<>(List.of(10, 20, 30, 40, 50));

System.out.println(Collections.binarySearch(ordenada, 30));   //  2  (esta en el indice 2)
System.out.println(Collections.binarySearch(ordenada, 35));   // -4  (iria en el indice 3)
System.out.println(Collections.binarySearch(ordenada, 5));    // -1  (iria en el indice 0)
System.out.println(Collections.binarySearch(ordenada, 99));   // -6  (iria en el indice 5)

Por qué esa fórmula tan rara

Porque el índice 0 es un resultado válido de "encontrado", y -0 es 0: no habría forma de distinguir "está en la posición 0" de "iría en la posición 0". Restar uno desplaza todos los negativos y elimina la ambigüedad.

Para recuperar el punto de inserción:

int resultado = Collections.binarySearch(ordenada, 35);
if (resultado >= 0) {
    System.out.println("Encontrado en la posicion " + resultado);
} else {
    int puntoInsercion = -resultado - 1;                 // -(-4) - 1 = 3
    System.out.println("No esta; iria en la posicion " + puntoInsercion);
    ordenada.add(puntoInsercion, 35);                    // insercion ordenada
}

Este idioma —buscar, y si no está insertar en el punto devuelto— es la forma estándar de mantener una lista ordenada sin reordenarla cada vez.

Las dos condiciones imprescindibles

1. La colección debe estar ordenada. Sobre una desordenada, el resultado es basura, sin ningún aviso.

List<Integer> desordenada = new ArrayList<>(List.of(30, 10, 50, 20, 40));
System.out.println(Collections.binarySearch(desordenada, 50));   // -3, y el 50 esta ahi

2. Debe estar ordenada por el MISMO criterio con el que buscas. Si ordenas por título y buscas con un comparador por referencia, el resultado no tiene sentido.

catalogo.sort(Comparator.comparing(Material::getTitulo));

// MAL: ordenado por titulo, buscado por referencia
Collections.binarySearch(catalogo, sonda, Comparator.comparing(Material::getReferencia));

// BIEN: el mismo comparador en ambos
Comparator<Material> porTitulo = Comparator.comparing(Material::getTitulo);
catalogo.sort(porTitulo);
Collections.binarySearch(catalogo, sonda, porTitulo);

Un detalle práctico: binarySearch necesita un elemento con el que comparar, no un valor de clave suelto. Para buscar "el material con referencia X" hace falta un elemento sonda, una instancia ficticia con esa referencia. Es incómodo, y es una razón más para preferir un Map cuando buscas por clave.

Y una advertencia final: si hay elementos duplicados según el criterio, binarySearch devuelve uno cualquiera de ellos, no necesariamente el primero.

Utilidades de `Collections`

java.util.Collections es la clase de utilidades del Framework, hermana de Arrays. Estas son las que quedan por conocer:

List<Ficha> fichas = new ArrayList<>(...);

// Extremos, con orden natural o con Comparator
Ficha primera = Collections.min(fichas);
Ficha ultima  = Collections.max(fichas);
Material caro = Collections.max(catalogo, Comparator.comparingDouble(Material::getTarifaDiaria));

// Contar apariciones (usa equals)
int cuantos = Collections.frequency(catalogo, javaEfectivo);

// Modificar la lista en el sitio
Collections.reverse(fichas);           // invierte el orden. O(n)
Collections.shuffle(fichas);           // baraja aleatoriamente. O(n)
Collections.swap(fichas, 0, 3);        // intercambia dos posiciones. O(1)
Collections.rotate(fichas, 2);         // desplaza 2 posiciones circularmente
Collections.fill(fichas, plantilla);   // rellena todo con el mismo elemento

// Crear
List<String> repes = Collections.nCopies(3, "pendiente");   // lista INMUTABLE de 3 iguales
Collections.addAll(catalogo, m1, m2, m3);                   // anadir varios de golpe

// Consultar
boolean sinRelacion = Collections.disjoint(conPrestamo, conRetraso);  // sin elementos comunes

// Vistas y colecciones especiales (05-02)
List<Material> soloLectura = Collections.unmodifiableList(catalogo);
List<Material> vacia = Collections.emptyList();
List<Material> uno = Collections.singletonList(javaEfectivo);

Método	Qué hace	Coste
`min(c)` / `max(c)`	Extremos según orden natural o `Comparator`	O(n)
`frequency(c, o)`	Cuántas veces aparece, usando `equals`	O(n)
`reverse(l)`	Invierte la lista en el sitio	O(n)
`shuffle(l)`	Baraja aleatoriamente	O(n)
`swap(l, i, j)`	Intercambia dos posiciones	O(1)
`rotate(l, d)`	Desplaza circularmente	O(n)
`nCopies(n, o)`	Lista inmutable de n copias	O(1)
`disjoint(a, b)`	¿No comparten ningún elemento?	O(n)
`addAll(c, e...)`	Añade varios elementos sueltos	O(n)

Dos observaciones útiles. min y max son O(n) y no requieren orden previo: para encontrar el máximo una sola vez, son mejores que ordenar. Y shuffle acepta un Random con semilla (Collections.shuffle(lista, new Random(42))), lo que hace el barajado reproducible, imprescindible para tests.

Rendimiento: ordenar una vez, buscar muchas

El compromiso central de esta lección, con números.

Supongamos un catálogo de 100 000 materiales sobre el que hacemos 10 000 búsquedas por referencia.

Estrategia	Coste de preparación	Coste por búsqueda	Total (operaciones)
Lineal, sin preparar	0	50 000 de media	500 000 000
Ordenar + binaria	~1 700 000 (n log n)	~17 (log n)	~1 870 000
Índice `HashMap`	100 000 (n)	1	110 000

La lección es doble. Preparar los datos compensa muchísimo en cuanto haya varias búsquedas: ordenar cuesta lo mismo que 1,7 búsquedas lineales y ahorra el resto. Y el índice hash gana a la búsqueda binaria cuando buscas por igualdad exacta.

¿Cuándo elegir entonces la búsqueda binaria sobre un HashMap?

Cuando necesitas el orden además de la búsqueda.
Cuando buscas por rango, no por valor exacto ("todos los publicados entre 1990 y 2000").
Cuando la memoria es crítica: un ArrayList ordenado ocupa mucho menos que un HashMap.
Cuando la clave no tiene un buen hashCode.

Y el punto de equilibrio, para orientarse:

Búsquedas previstas	Estrategia recomendada
1-2	Lineal: preparar no compensa
3-100	Ordenar + binaria, o índice
Más de 100	Índice `HashMap`
Cualquier número, pero también necesitas orden	`TreeMap`

Y la advertencia de siempre: estas cifras son de operaciones, no de tiempo. Para 200 elementos, todas las estrategias son instantáneas y debes elegir por claridad. La optimización empieza a importar a partir de decenas de miles.

Cierre del módulo: el estado de BiblioTech

Reunamos el proyecto completo con todo lo aprendido en el módulo.

package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.Predicate;
import com.nexussoftware.bibliotech.dominio.*;

/** BiblioTech al cierre del modulo 5: todas las estructuras en su sitio. */
public class BiblioTech {

    // --- Catalogo: lista para el orden, mapas para los indices ---
    private final List<Material>             catalogo      = new ArrayList<>();
    private final Map<String, Material>       porReferencia = new HashMap<>();
    private final Map<String, List<Material>> porTipo       = new HashMap<>();
    private final Set<String>                 isbnVistos    = new HashSet<>();

    // --- Prestamos ---
    private final Map<String, Prestamo>            prestamos   = new HashMap<>();
    private final Map<Empleado, List<Prestamo>>    porEmpleado = new HashMap<>();

    // --- Reservas: una cola FIFO por material ---
    private final Map<String, Deque<Reserva>> reservas = new HashMap<>();

    // --- Historial reversible ---
    private final Deque<OperacionCatalogo> deshacer = new ArrayDeque<>();

    // --- Comparadores reutilizables ---
    public static final Comparator<Material> POR_TITULO =
        Comparator.comparing(Material::getTitulo);
    public static final Comparator<Material> POR_TIPO_Y_TITULO =
        Comparator.comparing(Material::getTipo).thenComparing(Material::getTitulo);
    public static final Comparator<Material> POR_TARIFA_DESC =
        Comparator.comparingDouble(Material::getTarifaDiaria).reversed()
                  .thenComparing(Material::getReferencia);      // desempate: orden TOTAL

    // ---------- Catalogo ----------

    public boolean darDeAlta(Material m, int dia) {
        if (m == null || !isbnVistos.add(m.getReferencia())) { return false; }
        catalogo.add(m);
        porReferencia.put(m.getReferencia(), m);
        porTipo.computeIfAbsent(m.getTipo(), t -> new ArrayList<>()).add(m);
        deshacer.push(new OperacionCatalogo(OperacionCatalogo.Tipo.ALTA, m, dia));
        return true;
    }

    public boolean darDeBaja(String referencia, int dia) {
        Material m = porReferencia.remove(referencia);
        if (m == null) { return false; }
        isbnVistos.remove(referencia);
        catalogo.remove(m);
        porTipo.computeIfPresent(m.getTipo(),
                (t, lista) -> { lista.remove(m); return lista.isEmpty() ? null : lista; });
        deshacer.push(new OperacionCatalogo(OperacionCatalogo.Tipo.BAJA, m, dia));
        return true;
    }

    /** Busqueda por clave: O(1). */
    public Material buscar(String referencia) { return porReferencia.get(referencia); }

    /** Busqueda por criterio arbitrario: O(n), inevitable. */
    public List<Material> buscar(Predicate<Material> criterio) {
        List<Material> resultado = new ArrayList<>();
        for (Material m : catalogo) {
            if (criterio.test(m)) { resultado.add(m); }
        }
        return resultado;
    }

    public List<Material> listar(Comparator<Material> criterio) {
        List<Material> copia = new ArrayList<>(catalogo);
        copia.sort(criterio);                       // TimSort, O(n log n), estable
        return copia;
    }

    // ---------- Prestamos ----------

    public boolean prestar(String referencia, Empleado empleado, int dia) {
        Material m = porReferencia.get(referencia);
        if (m == null || !m.estaDisponible() || !empleado.puedeTomarPrestado()) {
            return false;
        }
        Prestamo p = new Prestamo(m, empleado, dia);
        prestamos.put(p.getReferencia(), p);
        porEmpleado.computeIfAbsent(empleado, e -> new ArrayList<>()).add(p);
        m.prestar();
        empleado.registrarPrestamo();
        return true;
    }

    public boolean devolver(String referenciaPrestamo, int dia) {
        Prestamo p = prestamos.get(referenciaPrestamo);       // O(1)
        if (p == null || p.estaDevuelto()) { return false; }
        p.registrarDevolucion(dia);
        p.getEmpleado().registrarDevolucion();

        // Atender la primera reserva del material, si la hay
        Deque<Reserva> cola = reservas.get(p.getMaterial().getReferencia());
        if (cola != null) {
            Reserva siguiente = cola.pollFirst();
            if (siguiente != null) {
                siguiente.marcarAtendida();
                System.out.printf("AVISO: %s puede recoger '%s'%n",
                        siguiente.getEmpleado().getNombre(), p.getMaterial().getTitulo());
            }
        }
        return true;
    }

    public void reservar(String referencia, Empleado empleado, int dia) {
        Material m = porReferencia.get(referencia);
        if (m == null) { return; }
        reservas.computeIfAbsent(referencia, r -> new ArrayDeque<>())
                .offerLast(new Reserva(empleado, m, dia));
    }

    // ---------- Informes ----------

    /** Contadores por tipo, en un TreeMap para que salgan siempre ordenados. */
    public Map<String, Integer> informePorTipo() {
        Map<String, Integer> resumen = new TreeMap<>();
        for (Material m : catalogo) { resumen.merge(m.getTipo(), 1, Integer::sum); }
        return resumen;
    }

    /** Ranking de empleados por multa acumulada, de mayor a menor. */
    public Map<Empleado, Double> rankingMultas(int diaActual) {
        Map<Empleado, Double> multas = new HashMap<>();
        for (List<Prestamo> lista : porEmpleado.values()) {
            for (Prestamo p : lista) {
                double multa = p.calcularMulta(diaActual);
                if (multa > 0) { multas.merge(p.getEmpleado(), multa, Double::sum); }
            }
        }
        // Un mapa NO se ordena por valor: hay que volcar, ordenar y reconstruir
        List<Map.Entry<Empleado, Double>> entradas = new ArrayList<>(multas.entrySet());
        entradas.sort(Map.Entry.<Empleado, Double>comparingByValue().reversed());

        Map<Empleado, Double> ordenado = new LinkedHashMap<>();   // conserva el orden
        for (Map.Entry<Empleado, Double> e : entradas) {
            ordenado.put(e.getKey(), e.getValue());
        }
        return ordenado;
    }

    /** Los N prestamos mas urgentes, con PriorityQueue. */
    public List<Prestamo> masUrgentes(int cuantos, int diaActual) {
        Queue<Prestamo> cola = new PriorityQueue<>(
            Comparator.comparingDouble((Prestamo p) -> p.calcularMulta(diaActual)).reversed()
                      .thenComparing(Prestamo::getReferencia));
        for (Prestamo p : prestamos.values()) {
            if (!p.estaDevuelto() && p.estaVencido(diaActual)) { cola.offer(p); }
        }
        List<Prestamo> resultado = new ArrayList<>();
        for (int i = 0; i < cuantos && !cola.isEmpty(); i++) {
            resultado.add(cola.poll());              // poll: el UNICO orden garantizado
        }
        return resultado;
    }

    /** El material mas caro: min/max son O(n), no hace falta ordenar. */
    public Material masCaro() {
        return catalogo.isEmpty() ? null
             : Collections.max(catalogo, Comparator.comparingDouble(Material::getTarifaDiaria));
    }

    public OperacionCatalogo ultimaOperacion() { return deshacer.peek(); }
    public int tamanoCatalogo() { return catalogo.size(); }
}

Y una sesión completa:

BiblioTech app = new BiblioTech();

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

app.darDeAlta(new Libro("Java Efectivo",      "Joshua Bloch",  "978-0000000001", 2018), 100);
app.darDeAlta(new Libro("Patrones de Diseno", "Erich Gamma",   "978-0000000002", 1994), 100);
app.darDeAlta(new Libro("Refactorizacion",    "Martin Fowler", "978-0000000003", 1999), 100);
app.darDeAlta(new Revista("Java Magazine",    "REV-2024-03",   42, "Mensual"),          101);
app.darDeAlta(new Dvd("Refactorizacion en vivo", "DVD-0007",   95),                     101);

System.out.println("=== Catalogo por tipo y titulo ===");
app.listar(BiblioTech.POR_TIPO_Y_TITULO)
   .forEach(m -> System.out.printf("  %-8s %-26s %.2f EUR/dia%n",
           m.getTipo(), m.getTitulo(), m.getTarifaDiaria()));

app.prestar("978-0000000001", marta, 100);
app.prestar("978-0000000003", marta, 102);
app.prestar("DVD-0007",       diego, 105);
app.reservar("978-0000000001", nuria, 106);       // Java Efectivo esta prestado

System.out.println("\n=== Informe por tipo ===");
app.informePorTipo().forEach((t, n) -> System.out.printf("  %-8s %d%n", t, n));

System.out.println("\n=== Prestamos mas urgentes (dia 140) ===");
app.masUrgentes(3, 140).forEach(p -> System.out.printf("  %-16s %-26s %6.2f EUR%n",
        p.getEmpleado().getNombre(), p.getMaterial().getTitulo(), p.calcularMulta(140)));

System.out.println("\n=== Ranking de multas (dia 140) ===");
app.rankingMultas(140).forEach((e, multa) ->
        System.out.printf("  %-16s %6.2f EUR%n", e.getNombre(), multa));

System.out.println("\n=== Devolucion con reserva pendiente ===");
app.devolver("PR-0001", 140);

System.out.println("\nMaterial mas caro: " + app.masCaro().getTitulo());
System.out.println("Ultima operacion:  " + app.ultimaOperacion());

=== Catalogo por tipo y titulo ===
  DVD      Refactorizacion en vivo    0,50 EUR/dia
  Libro    Java Efectivo              0,25 EUR/dia
  Libro    Patrones de Diseno         0,25 EUR/dia
  Libro    Refactorizacion            0,25 EUR/dia
  Revista  Java Magazine              0,10 EUR/dia

=== Informe por tipo ===
  DVD      1
  Libro    3
  Revista  1

=== Prestamos mas urgentes (dia 140) ===
  Diego Alonso     Refactorizacion en vivo  16,00 EUR
  Marta Ruiz       Java Efectivo             6,25 EUR
  Marta Ruiz       Refactorizacion           5,75 EUR

=== Ranking de multas (dia 140) ===
  Diego Alonso      16,00 EUR
  Marta Ruiz        12,00 EUR

=== Devolucion con reserva pendiente ===
AVISO: Nuria Vidal puede recoger 'Java Efectivo'

Material mas caro: Refactorizacion en vivo
Ultima operacion: Alta de material de 'Refactorizacion en vivo' (DVD-0007) el dia 101

El balance: qué sabe hacer BiblioTech

Necesidad	Estructura	Coste
Catálogo ordenable y recorrible	`List<Material>` (`ArrayList`)	Recorrido O(n), acceso O(1)
Búsqueda por referencia	`Map<String, Material>`	O(1)
Agrupación por tipo	`Map<String, List<Material>>` con `computeIfAbsent`	O(1)
Rechazo de ISBN duplicados	`Set<String>` con el `boolean` de `add`	O(1)
Préstamos por referencia	`Map<String, Prestamo>`	O(1)
Préstamos por empleado	`Map<Empleado, List<Prestamo>>`	O(1)
Cola de reservas por material	`Map<String, Deque<Reserva>>` (`ArrayDeque`)	O(1) en extremos
Avisos por urgencia	`PriorityQueue<Prestamo>`	O(log n)
Historial de deshacer	`Deque<OperacionCatalogo>` (`ArrayDeque`)	O(1)
Informes ordenados	`TreeMap` / `LinkedHashMap`	O(log n) / O(1)
Ordenación por cualquier criterio	`Comparator` compuestos	O(n log n)

Y aquel informePorTipo de veinte líneas con bucles anidados del módulo 4 se ha quedado, literalmente, en tres.

Qué sigue siendo frágil

Y ahora la parte honesta. Mira cualquier método del proyecto con ojo crítico y verás la misma debilidad:

1. Cualquier dato inválido rompe el programa. Integer.parseInt("abc") lanza NumberFormatException y la aplicación termina. porReferencia.get(null) puede dar NullPointerException. catalogo.get(99) da IndexOutOfBoundsException. pila.pop() sobre una pila vacía, NoSuchElementException. 1 / 0, ArithmeticException. En todo el módulo hemos evitado cuidadosamente esas situaciones comprobando antes, pero comprobar antes no siempre es posible ni suficiente.

2. Los errores se comunican devolviendo null o false. buscar(referencia) devuelve null si no está: ¿es que no existe, o es que la referencia era inválida? darDeAlta devuelve false: ¿por duplicado, por material nulo, por referencia vacía? El valor de retorno no puede transportar el motivo del fallo, así que quien llama no puede reaccionar de forma distinta según el caso.

3. Los avisos se imprimen por consola. Todo el proyecto está lleno de System.out.println("AVISO: ..."). Eso no es gestión de errores: es un mensaje que nadie puede capturar, registrar ni tratar. Un servicio que se ejecute sin consola pierde toda la información.

4. Un fallo a medias deja el sistema incoherente. Si darDeAlta añade al Set de ISBN y falla antes de añadir a la lista, el ISBN queda marcado como catalogado sin que exista el material. No hay forma de deshacer parcialmente una operación.

5. Nada se guarda al salir. Todo vive en memoria. Cerrar el programa borra el catálogo, los préstamos, las reservas y el historial. La próxima ejecución empieza de cero.

Los cuatro primeros puntos son exactamente el temario del módulo 6. El quinto, el del módulo 7.

Errores Comunes y Consejos

Restar para comparar. a - b desborda con enteros grandes y trunca con dobles. Usa Integer.compare, Double.compare, etc. Sin excepciones.

(int) (dobleA - dobleB). Todas las diferencias menores que 1 se truncan a 0: elementos distintos se declaran iguales. Double.compare siempre.

Orden no coherente con equals en un TreeSet o TreeMap. Los elementos que empatan según el comparador se consideran el mismo, y el segundo se descarta en silencio. Añade criterios de desempate hasta que el orden sea total.

Colocar mal reversed(). Invierte todo lo compuesto hasta ese punto, no solo el último criterio. Si cada criterio lleva su dirección, usa thenComparing(extractor, Comparator.reverseOrder()).

Usar comparing con claves primitivas. Provoca autoboxing en cada comparación. comparingInt, comparingLong y comparingDouble existen precisamente para eso.

binarySearch sobre una colección desordenada. Devuelve resultados sin sentido, sin ningún aviso. Y debe estar ordenada por el mismo criterio con el que buscas.

Interpretar el negativo de binarySearch como "-1, no está". Es -(punto de inserción) - 1. Para obtener el punto: -resultado - 1.

binarySearch sobre una LinkedList. El acceso indexado es O(n), así que la búsqueda "binaria" acaba siendo peor que la lineal. Solo sobre ArrayList o arrays.

Ordenar para encontrar el máximo. Collections.max es O(n); ordenar es O(n log n). Si solo necesitas el extremo, no ordenes.

Ordenar una lista dentro de un bucle. Es el error de rendimiento clásico: ordena una vez fuera, o usa un TreeSet si el orden debe estar siempre.

Ignorar IllegalArgumentException: Comparison method violates its general contract! No es un fallo de Java: es TimSort avisándote de que tu comparador es incoherente. Revisa la transitividad y la antisimetría.

Consejo: declara los comparadores frecuentes como constantes. Son inmutables y reutilizables; crear uno nuevo en cada llamada es ruido.

Consejo: para el "top N", vuelca entrySet(), ordena y reconstruye en un LinkedHashMap. Un mapa nunca se ordena por valor, y solo LinkedHashMap conserva el orden en que insertas.

Consejo: si buscas más de unas pocas veces por la misma clave, construye un índice. El HashMap se amortiza casi de inmediato.

Ejercicios

Ejercicio 1: catálogo ordenable con múltiples criterios

Escribe CatalogoOrdenable con un List<Material> interno y:

Una clase anidada Ordenes con constantes Comparator<Material> para: por título, por tipo y título, por tarifa descendente, por disponibilidad y luego título, y por tipo y tarifa descendente.
List<Material> ordenadoPor(Comparator<Material>): devuelve una copia ordenada, sin tocar el original.
void ordenarEnElSitio(Comparator<Material>).
Material maximo(Comparator<Material>) y Material minimo(Comparator<Material>) con Collections.
List<Material> topN(int n, Comparator<Material>).
int buscarBinario(String titulo): ordena por título si hace falta e interpreta correctamente el valor negativo, informando del punto de inserción.

Todos los comparadores deben producir un orden total (con desempate por referencia).

Ejercicio 2: demostración de los contratos rotos

Escribe DemostracionOrden con un main que demuestre, imprimiendo y explicando:

Que restar enteros desborda: compara a - b con Integer.compare(a, b) para valores extremos.
Que (int)(dobleA - dobleB) trunca las tarifas de BiblioTech y las declara todas iguales.
Que un orden incoherente con equals hace que un TreeSet pierda elementos, mientras que un HashSet no.
Que la ordenación de Java es estable: ordena por autor, luego por año, y comprueba que dentro de cada año se conserva el orden por autor.
Que reversed() invierte todo lo acumulado, con la forma correcta de invertir un solo criterio.
Que binarySearch sobre una lista desordenada devuelve basura.

Ejercicio 3: comparativa de estrategias de búsqueda

Escribe ComparativaBusquedas que, con 100 000 materiales y 10 000 búsquedas por referencia, mida:

Búsqueda lineal con for sobre un ArrayList.
Ordenar una vez + Collections.binarySearch con elemento sonda.
Construir un HashMap una vez + get.
Construir un TreeMap una vez + get.

Imprime una tabla con el tiempo de preparación, el de las búsquedas y el total, e incluye la advertencia sobre JMH. Escribe una conclusión razonada indicando cuándo elegirías cada estrategia.

Soluciones

Solución 1

package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import com.nexussoftware.bibliotech.dominio.Libro;
import com.nexussoftware.bibliotech.dominio.Material;

public class CatalogoOrdenable {

    private final List<Material> materiales = new ArrayList<>();
    private Comparator<Material> ordenActual = null;   // recuerda como esta ordenado

    /** Comparadores reutilizables. TODOS terminan con un desempate por referencia. */
    public static final class Ordenes {
        private Ordenes() { }

        public static final Comparator<Material> POR_TITULO =
            Comparator.comparing(Material::getTitulo)
                      .thenComparing(Material::getReferencia);

        public static final Comparator<Material> POR_TIPO_Y_TITULO =
            Comparator.comparing(Material::getTipo)
                      .thenComparing(Material::getTitulo)
                      .thenComparing(Material::getReferencia);

        // comparingDouble: sin autoboxing. reversed() antes del desempate,
        // para que la referencia siga ordenandose ASCENDENTE.
        public static final Comparator<Material> POR_TARIFA_DESC =
            Comparator.comparingDouble(Material::getTarifaDiaria).reversed()
                      .thenComparing(Material::getReferencia);

        // Los disponibles primero: false < true, asi que hay que invertir el booleano
        public static final Comparator<Material> POR_DISPONIBILIDAD =
            Comparator.comparing((Material m) -> !m.estaDisponible())
                      .thenComparing(Material::getTitulo)
                      .thenComparing(Material::getReferencia);

        // Tipo ASCENDENTE, tarifa DESCENDENTE: cada criterio con su direccion.
        // Un .reversed() al final invertiria TAMBIEN el tipo: error clasico.
        public static final Comparator<Material> POR_TIPO_Y_TARIFA_DESC =
            Comparator.comparing(Material::getTipo)
                      .thenComparing(Material::getTarifaDiaria, Comparator.reverseOrder())
                      .thenComparing(Material::getReferencia);
    }

    public void anadir(Material m) {
        if (m != null) { materiales.add(m); ordenActual = null; }   // se pierde el orden
    }

    /** Copia ordenada: el catalogo original conserva su orden. */
    public List<Material> ordenadoPor(Comparator<Material> criterio) {
        List<Material> copia = new ArrayList<>(materiales);
        copia.sort(criterio);
        return copia;
    }

    public void ordenarEnElSitio(Comparator<Material> criterio) {
        materiales.sort(criterio);
        ordenActual = criterio;
    }

    /** max/min son O(n): mucho mejor que ordenar (O(n log n)) para un solo extremo. */
    public Material maximo(Comparator<Material> criterio) {
        return materiales.isEmpty() ? null : Collections.max(materiales, criterio);
    }

    public Material minimo(Comparator<Material> criterio) {
        return materiales.isEmpty() ? null : Collections.min(materiales, criterio);
    }

    public List<Material> topN(int n, Comparator<Material> criterio) {
        List<Material> ordenado = ordenadoPor(criterio);
        return new ArrayList<>(ordenado.subList(0, Math.min(n, ordenado.size())));
    }

    /**
     * Busqueda binaria por titulo. Ordena solo si hace falta y usa
     * el MISMO comparador para ordenar y para buscar: requisito imprescindible.
     */
    public int buscarBinario(String titulo) {
        if (titulo == null) { return -1; }

        Comparator<Material> criterio = Ordenes.POR_TITULO;
        if (ordenActual != criterio) {
            ordenarEnElSitio(criterio);       // O(n log n), pero solo la primera vez
        }

        // binarySearch necesita un ELEMENTO, no una clave suelta: hace falta una sonda.
        // Es un inconveniente real, y una razon mas para preferir un Map (05-05).
        Material sonda = new Libro(titulo, "", "", 2000);
        int resultado = Collections.binarySearch(materiales, sonda,
                Comparator.comparing(Material::getTitulo));   // solo el titulo: la sonda
                                                              // no tiene referencia valida

        if (resultado >= 0) {
            System.out.printf("'%s' encontrado en la posicion %d%n", titulo, resultado);
        } else {
            int puntoInsercion = -resultado - 1;      // la formula: -(pos) - 1
            System.out.printf("'%s' no esta; iria en la posicion %d%n", titulo, puntoInsercion);
        }
        return resultado;
    }

    public int tamano() { return materiales.size(); }
}

Prueba:

CatalogoOrdenable c = new CatalogoOrdenable();
c.anadir(new Libro("Refactorizacion",    "Martin Fowler", "978-0000000003", 1999));
c.anadir(new Libro("Java Efectivo",      "Joshua Bloch",  "978-0000000001", 2018));
c.anadir(new Revista("Java Magazine",    "REV-2024-03",   42, "Mensual"));
c.anadir(new Dvd("Refactorizacion en vivo", "DVD-0007",   95));
c.anadir(new Libro("Patrones de Diseno", "Erich Gamma",   "978-0000000002", 1994));

System.out.println("--- Por tipo y tarifa descendente ---");
c.ordenadoPor(CatalogoOrdenable.Ordenes.POR_TIPO_Y_TARIFA_DESC)
 .forEach(m -> System.out.printf("  %-8s %-26s %.2f%n",
         m.getTipo(), m.getTitulo(), m.getTarifaDiaria()));

System.out.println("Mas caro: " + c.maximo(
        Comparator.comparingDouble(Material::getTarifaDiaria)).getTitulo());

System.out.println("--- Top 2 por tarifa ---");
c.topN(2, CatalogoOrdenable.Ordenes.POR_TARIFA_DESC)
 .forEach(m -> System.out.println("  " + m.getTitulo()));

c.buscarBinario("Java Efectivo");
c.buscarBinario("Codigo Limpio");

Tres decisiones importantes. Todos los comparadores acaban en thenComparing(Material::getReferencia), que es única, de modo que el orden es total y estos comparadores se pueden usar sin riesgo en un TreeSet. En POR_TIPO_Y_TARIFA_DESC la dirección se aplica a cada criterio por separado con thenComparing(extractor, reverseOrder()), porque un .reversed() al final habría invertido también el tipo. Y buscarBinario recuerda el orden actual para no reordenar en cada llamada, aunque el detalle de la sonda deja claro por qué, para buscar por clave, un Map es casi siempre mejor.

Solución 2

package com.nexussoftware.bibliotech.presentacion;

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

public class DemostracionOrden {

    record FichaSimple(String titulo, String autor, int anio) { }

    /** Orden natural INCOHERENTE con equals: solo mira el anio. */
    record FichaPorAnio(String titulo, String autor, int anio)
            implements Comparable<FichaPorAnio> {
        @Override public int compareTo(FichaPorAnio o) { return Integer.compare(anio, o.anio); }
    }

    public static void main(String[] args) {
        desbordamiento();
        truncamiento();
        incoherencia();
        estabilidad();
        reversedMalColocado();
        binarySearchDesordenado();
    }

    static void desbordamiento() {
        System.out.println("=== 1. Restar enteros DESBORDA ===");
        int a = 2_000_000_000, b = -2_000_000_000;

        System.out.println("a = " + a + ", b = " + b + "  -> a es claramente MAYOR");
        System.out.println("a - b               = " + (a - b) + "   <- NEGATIVO: dice a < b");
        System.out.println("Integer.compare(a,b)= " + Integer.compare(a, b) + "   <- correcto");
        System.out.println("Causa: 4.000.000.000 no cabe en un int (max 2.147.483.647),");
        System.out.println("el valor da la vuelta y cambia de signo. Nunca restes.\n");
    }

    static void truncamiento() {
        System.out.println("=== 2. Restar dobles y castear TRUNCA ===");
        double libro = 0.25, revista = 0.10, dvd = 0.50;

        System.out.println("(int)(dvd - revista)      = " + (int)(dvd - revista)
                           + "   <- 0.40 truncado a 0: 'son iguales'");
        System.out.println("(int)(libro - revista)    = " + (int)(libro - revista) + "   <- idem");
        System.out.println("Double.compare(dvd,revista)= " + Double.compare(dvd, revista));
        System.out.println("Con este bug, TODAS las tarifas de BiblioTech serian iguales");
        System.out.println("y el catalogo no se ordenaria en absoluto.\n");
    }

    static void incoherencia() {
        System.out.println("=== 3. Orden incoherente con equals ===");
        FichaPorAnio a = new FichaPorAnio("Java Efectivo",      "Joshua Bloch", 2018);
        FichaPorAnio b = new FichaPorAnio("Patrones de Diseno", "Erich Gamma",  2018);

        System.out.println("a.equals(b):    " + a.equals(b)    + "   <- son DISTINTAS");
        System.out.println("a.compareTo(b): " + a.compareTo(b) + "   <- pero EMPATAN");

        System.out.println("En List:     " + new ArrayList<>(List.of(a, b)).size() + " elementos");
        System.out.println("En HashSet:  " + new HashSet<>(List.of(a, b)).size()
                           + " elementos   <- usa equals/hashCode: correcto");
        System.out.println("En TreeSet:  " + new TreeSet<>(List.of(a, b)).size()
                           + " elementos   <- usa compareTo: SE PIERDE UNA");

        Set<FichaPorAnio> arreglado = new TreeSet<>(
            Comparator.comparingInt(FichaPorAnio::anio)
                      .thenComparing(FichaPorAnio::titulo));    // desempate
        arreglado.addAll(List.of(a, b));
        System.out.println("Con desempate: " + arreglado.size() + " elementos   <- arreglado\n");
    }

    static void estabilidad() {
        System.out.println("=== 4. La ordenacion de Java es ESTABLE ===");
        List<FichaSimple> fichas = new ArrayList<>(List.of(
            new FichaSimple("Refactorizacion",    "Martin Fowler", 1999),
            new FichaSimple("Codigo Limpio",      "Robert Martin", 2008),
            new FichaSimple("Java Efectivo",      "Joshua Bloch",  2018),
            new FichaSimple("Java Concurrente",   "Brian Goetz",   2018),
            new FichaSimple("Patrones de Diseno", "Erich Gamma",   1999)));

        fichas.sort(Comparator.comparing(FichaSimple::autor));      // criterio SECUNDARIO
        System.out.println("Tras ordenar por autor:");
        fichas.forEach(f -> System.out.printf("  %-16s %d  %s%n", f.autor(), f.anio(), f.titulo()));

        fichas.sort(Comparator.comparingInt(FichaSimple::anio));    // criterio PRIMARIO
        System.out.println("Tras ordenar por anio (dentro de cada anio, sigue por autor):");
        fichas.forEach(f -> System.out.printf("  %-16s %d  %s%n", f.autor(), f.anio(), f.titulo()));

        System.out.println("Prefiere el comparador compuesto: UNA pasada y mas claro:");
        fichas.sort(Comparator.comparingInt(FichaSimple::anio)
                              .thenComparing(FichaSimple::autor));
        System.out.println();
    }

    static void reversedMalColocado() {
        System.out.println("=== 5. Donde colocar reversed() ===");
        List<FichaSimple> fichas = new ArrayList<>(List.of(
            new FichaSimple("Java Efectivo",    "Joshua Bloch", 2018),
            new FichaSimple("Java Concurrente", "Brian Goetz",  2018),
            new FichaSimple("Refactorizacion",  "Martin Fowler", 1999)));

        List<FichaSimple> mal = new ArrayList<>(fichas);
        mal.sort(Comparator.comparingInt(FichaSimple::anio)
                           .thenComparing(FichaSimple::autor)
                           .reversed());          // invierte ANIO Y AUTOR
        System.out.println("Con .reversed() al final (invierte AMBOS):");
        mal.forEach(f -> System.out.printf("  %d %s%n", f.anio(), f.autor()));

        List<FichaSimple> bien = new ArrayList<>(fichas);
        bien.sort(Comparator.comparingInt(FichaSimple::anio).reversed()
                            .thenComparing(FichaSimple::autor));   // solo el anio
        System.out.println("Con .reversed() tras el anio (solo invierte el anio):");
        bien.forEach(f -> System.out.printf("  %d %s%n", f.anio(), f.autor()));
        System.out.println();
    }

    static void binarySearchDesordenado() {
        System.out.println("=== 6. binarySearch sobre lista DESORDENADA ===");
        List<Integer> desordenada = new ArrayList<>(List.of(30, 10, 50, 20, 40));
        System.out.println("Lista: " + desordenada);
        System.out.println("binarySearch(50): " + java.util.Collections.binarySearch(desordenada, 50)
                           + "   <- el 50 ESTA en el indice 2, pero devuelve un negativo");

        List<Integer> ordenada = new ArrayList<>(desordenada);
        java.util.Collections.sort(ordenada);
        System.out.println("Ordenada: " + ordenada);
        System.out.println("binarySearch(50): " + java.util.Collections.binarySearch(ordenada, 50)
                           + "   <- correcto");
        System.out.println("binarySearch(35): " + java.util.Collections.binarySearch(ordenada, 35)
                           + "   <- -(punto de insercion) - 1 = -(3) - 1");
        System.out.println("Punto de insercion: "
                           + (-java.util.Collections.binarySearch(ordenada, 35) - 1));
    }
}

Los seis apartados comparten un rasgo: ninguno lanza una excepción. El desbordamiento devuelve un número, el truncamiento devuelve cero, el TreeSet pierde un elemento sin protestar, el reversed() mal colocado ordena "algo" y binarySearch devuelve un negativo plausible. Los errores de ordenación y comparación son silenciosos, y por eso conviene conocer los contratos: no hay compilador ni excepción que te avise.

Solución 3

package com.nexussoftware.bibliotech.presentacion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import com.nexussoftware.bibliotech.dominio.Libro;
import com.nexussoftware.bibliotech.dominio.Material;

/**
 * Compara cuatro estrategias de busqueda por referencia.
 *
 * ADVERTENCIA: no es un benchmark riguroso. El JIT compila sobre la marcha,
 * el recolector puede intervenir y el compilador puede eliminar codigo cuyo
 * resultado no se use. Para medir en serio, JMH (05-04). Estas cifras solo
 * sirven para ver ORDENES DE MAGNITUD.
 */
public class ComparativaBusquedas {

    private static final int N         = 100_000;
    private static final int BUSQUEDAS = 10_000;
    private static long escudo = 0;      // evita que el JIT elimine los bucles

    public static void main(String[] args) {
        List<Material> catalogo = generar(N);
        List<String>   claves   = clavesAleatorias(BUSQUEDAS);

        System.out.println("Calentando la JVM...");
        for (int i = 0; i < 3; i++) {
            lineal(catalogo.subList(0, 1000), claves.subList(0, 100));
            conHashMap(catalogo.subList(0, 1000), claves.subList(0, 100));
        }

        System.out.printf("%n=== %d materiales, %d busquedas ===%n", N, BUSQUEDAS);
        System.out.printf("%-24s %12s %12s %12s%n",
                          "Estrategia", "Preparar", "Buscar", "TOTAL");
        System.out.println("-".repeat(64));

        long[] r1 = lineal(catalogo, claves);
        long[] r2 = conBinaria(catalogo, claves);
        long[] r3 = conHashMap(catalogo, claves);
        long[] r4 = conTreeMap(catalogo, claves);

        fila("1. Lineal (for + equals)",  r1);
        fila("2. Ordenar + binarySearch", r2);
        fila("3. HashMap",                r3);
        fila("4. TreeMap",                r4);

        System.out.println("\n(escudo = " + escudo + ", ignoralo)");
        conclusion();
    }

    private static void fila(String etiqueta, long[] t) {
        System.out.printf("%-24s %9d ms %9d ms %9d ms%n", etiqueta, t[0], t[1], t[0] + t[1]);
    }

    /** 1. Lineal: sin preparacion, O(n) por busqueda. */
    private static long[] lineal(List<Material> catalogo, List<String> claves) {
        long t = System.nanoTime();
        int encontrados = 0;
        for (String clave : claves) {
            for (Material m : catalogo) {
                if (m.getReferencia().equals(clave)) { encontrados++; break; }
            }
        }
        escudo += encontrados;
        return new long[]{ 0, ms(t) };
    }

    /** 2. Ordenar una vez O(n log n), luego O(log n) por busqueda. */
    private static long[] conBinaria(List<Material> catalogo, List<String> claves) {
        Comparator<Material> porReferencia = Comparator.comparing(Material::getReferencia);

        long t1 = System.nanoTime();
        List<Material> ordenado = new ArrayList<>(catalogo);
        ordenado.sort(porReferencia);
        long preparar = ms(t1);

        long t2 = System.nanoTime();
        int encontrados = 0;
        for (String clave : claves) {
            // binarySearch necesita un ELEMENTO: hay que fabricar una sonda por busqueda.
            // Ese coste extra es real y penaliza esta estrategia.
            Material sonda = new Libro("", "", clave, 2000);
            if (Collections.binarySearch(ordenado, sonda, porReferencia) >= 0) { encontrados++; }
        }
        escudo += encontrados;
        return new long[]{ preparar, ms(t2) };
    }

    /** 3. Indice hash: O(n) al construir, O(1) por busqueda. */
    private static long[] conHashMap(List<Material> catalogo, List<String> claves) {
        long t1 = System.nanoTime();
        Map<String, Material> indice = new HashMap<>((int)(catalogo.size() / 0.75f) + 1);
        for (Material m : catalogo) { indice.put(m.getReferencia(), m); }
        long preparar = ms(t1);

        long t2 = System.nanoTime();
        int encontrados = 0;
        for (String clave : claves) {
            if (indice.get(clave) != null) { encontrados++; }
        }
        escudo += encontrados;
        return new long[]{ preparar, ms(t2) };
    }

    /** 4. Arbol: O(n log n) al construir, O(log n) por busqueda, pero ORDENADO. */
    private static long[] conTreeMap(List<Material> catalogo, List<String> claves) {
        long t1 = System.nanoTime();
        Map<String, Material> indice = new TreeMap<>();
        for (Material m : catalogo) { indice.put(m.getReferencia(), m); }
        long preparar = ms(t1);

        long t2 = System.nanoTime();
        int encontrados = 0;
        for (String clave : claves) {
            if (indice.get(clave) != null) { encontrados++; }
        }
        escudo += encontrados;
        return new long[]{ preparar, ms(t2) };
    }

    private static List<Material> generar(int n) {
        List<Material> lista = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            lista.add(new Libro("Titulo " + i, "Autor " + (i % 500),
                                String.format("978-%010d", i), 1990 + (i % 35)));
        }
        return lista;
    }

    private static List<String> clavesAleatorias(int cuantas) {
        List<String> claves = new ArrayList<>(cuantas);
        java.util.Random azar = new java.util.Random(42);    // semilla fija: reproducible
        for (int i = 0; i < cuantas; i++) {
            claves.add(String.format("978-%010d", azar.nextInt(N)));
        }
        return claves;
    }

    private static long ms(long inicioNano) {
        return (System.nanoTime() - inicioNano) / 1_000_000;
    }

    private static void conclusion() {
        System.out.println("""

            === Conclusion ===
            1. LINEAL: cero preparacion, pero cada busqueda recorre media lista.
               Con 10.000 busquedas sobre 100.000 elementos son unos 500 millones
               de comparaciones. Solo vale para 1-2 busquedas o listas pequenas.

            2. ORDENAR + BINARIA: la preparacion es la mas cara (O(n log n)) y cada
               busqueda es O(log n), unas 17 comparaciones. Ademas hay que fabricar
               un elemento SONDA por busqueda, lo que penaliza bastante.
               Merece la pena cuando ademas necesitas la lista ordenada.

            3. HASHMAP: preparacion O(n) y busqueda O(1). Es la mas rapida con
               diferencia y la respuesta por defecto para buscar por clave exacta.
               Precio: memoria extra y necesitar equals/hashCode correctos.

            4. TREEMAP: preparacion O(n log n) y busqueda O(log n). Mas lento que
               el HashMap, pero a cambio mantiene las claves ORDENADAS y ofrece
               firstKey, headMap, floorKey y consultas por rango.

            CRITERIO:
              - Buscas 1-2 veces  ................ lineal
              - Buscas por clave exacta, muchas .. HashMap
              - Necesitas orden o rangos ......... TreeMap
              - La lista ya esta ordenada ........ binarySearch
            """);
    }
}

Salida típica:

=== 100000 materiales, 10000 busquedas ===
Estrategia                   Preparar       Buscar        TOTAL
----------------------------------------------------------------
1. Lineal (for + equals)          0 ms      2840 ms      2840 ms
2. Ordenar + binarySearch        95 ms        42 ms       137 ms
3. HashMap                       18 ms         2 ms        20 ms
4. TreeMap                       78 ms         9 ms        87 ms

Los números confirman el análisis del apartado 13, con una lección adicional: la preparación es casi siempre rentable. La lineal tarda 2840 ms sin preparar nada; el HashMap tarda 20 ms incluyendo la construcción del índice. Preparar cuesta 18 ms y ahorra 2820.

Y hay un matiz que las tablas teóricas no muestran: la estrategia 2 sale peor de lo que su O(log n) sugeriría, porque fabrica un objeto sonda en cada búsqueda. Ese coste no aparece en el análisis asintótico y sin embargo domina el tiempo real. Es un recordatorio de que la O() describe cómo escala una operación, no cuánto cuesta ejecutarla: para decidir de verdad, hay que medir.

Conclusión

Has cerrado el módulo con las operaciones que atraviesan todas las colecciones. Sabes que Comparable define el orden natural de una clase mediante compareTo, cuyo signo —negativo, cero, positivo— es lo único que importa, y conoces su contrato completo: antisimetría, transitividad, consistencia, coherencia con equals y el rechazo de null. Sabes que romperlo produce ordenaciones incorrectas o el IllegalArgumentException: Comparison method violates its general contract! que TimSort lanza al detectar la incoherencia.

Tienes grabado el error que más código en producción contiene: nunca restes para comparar. a - b desborda con enteros grandes y devuelve el signo contrario; (int)(dobleA - dobleB) trunca cualquier diferencia menor que 1 y declara iguales elementos distintos. La respuesta es siempre Integer.compare, Double.compare y sus hermanos. Y entiendes por qué la coherencia con equals importa tanto: TreeSet y TreeMap deciden la unicidad con compareTo, no con equals, así que un orden parcial pierde elementos en silencio. La solución es añadir desempates hasta que el orden sea total.

Dominas Comparator en su forma moderna: comparing, las variantes comparingInt/Long/Double que evitan el autoboxing, thenComparing para los desempates, reversed() —con la advertencia de que invierte todo lo acumulado, y thenComparing(extractor, reverseOrder()) cuando cada criterio necesita su dirección— y nullsFirst/nullsLast para tolerar elementos ausentes. Y sabes declararlos como constantes reutilizables.

Conoces las cuatro estrategias de ordenación y el criterio que decide entre ellas —cuántas veces necesitas el orden—, con la conclusión práctica de que ArrayList + sort gana cuando el orden solo hace falta al final y TreeSet/TreeMap ganan cuando debe estar disponible entre inserciones o hay consultas por rango. Entiendes la estabilidad y por qué permite ordenar por criterios sucesivos —aunque un comparador compuesto sea preferible—, y sabes qué hay debajo: TimSort para objetos, híbrido, estable y O(n) cuando los datos ya están casi ordenados; quicksort de doble pivote para primitivos, en el sitio y con memoria mínima. Y sabes por qué son dos algoritmos distintos.

En búsqueda, tienes las tres estrategias con sus complejidades y su criterio: lineal cuando buscas poco o por criterios cambiantes; binaria cuando la colección ya está ordenada por el mismo criterio —con la interpretación exacta del negativo como -(punto de inserción) - 1 y la advertencia de no usarla sobre LinkedList—; y por clave en un Map o Set cuando buscas muchas veces por lo mismo. Has visto con números que preparar los datos casi siempre compensa: construir un HashMap cuesta lo mismo que unas pocas búsquedas lineales y ahorra todas las demás. Y conoces las utilidades de Collections que quedaban: max, min, frequency, reverse, shuffle, swap, rotate, nCopies, disjoint y addAll.

BiblioTech, al cerrar el módulo 5, es un sistema de gestión de verdad. Su catálogo es una List<Material> ordenable por cualquier Comparator, respaldada por un Map<String, Material> que encuentra cualquier material por su referencia en tiempo constante, un Map<String, List<Material>> que agrupa por tipo construido con computeIfAbsent, y un Set<String> que rechaza ISBN duplicados apoyándose solo en el boolean que devuelve add. Los préstamos están indexados por referencia y por empleado, las multas se acumulan con merge, las reservas de cada material esperan en un ArrayDeque FIFO que se atiende sola al devolver, los avisos salen de una PriorityQueue que sirve primero al más urgente, y una Deque<OperacionCatalogo> permite anular la última alta o baja. Los informes por tipo y el ranking de multas se generan en una pasada. Y aquel informePorTipo de veinte líneas con bucles anidados que se prometió reducir a tres, se ha quedado en tres. No queda una sola línea de gestión manual de memoria en todo el proyecto.

Y sin embargo, el proyecto es frágil de una manera que ya no se puede seguir ignorando. Todo el módulo ha esquivado cuidadosamente el problema: cada método comprueba antes de actuar, devuelve null o false cuando algo va mal e imprime System.out.println("AVISO: ...") para lo demás. Pero comprobar antes no siempre es posible. Un Integer.parseInt("veinte") lanza NumberFormatException y la aplicación termina. Un índice fuera de rango, un pop() sobre una pila vacía, una división por cero, un fichero que no existe: cualquiera de ellos detiene el programa en seco. Un false devuelto no dice por qué falló, así que quien llama no puede reaccionar de forma distinta según el motivo. Un mensaje impreso por consola no se puede capturar, registrar ni tratar. Y si una operación falla a medias —el ISBN ya está en el Set pero el material aún no está en la lista—, el sistema queda incoherente sin forma de volver atrás. Además, nada de esto sobrevive al cierre del programa: todo vive en memoria y la próxima ejecución empieza de cero.

En el módulo 6, Manejo de Excepciones, se resuelve lo primero. Verás qué es realmente una excepción y cómo viaja por la pila de llamadas que conociste en 05-08; la jerarquía Throwable → Error/Exception → RuntimeException y la distinción entre comprobadas y no comprobadas; el bloque try-catch con múltiples capturas y su orden obligatorio; throw para señalar un fallo y throws para declararlo; excepciones personalizadas que digan exactamente qué salió mal —MaterialNoEncontradoException, ReferenciaDuplicadaException, LimitePrestamosExcedidoException— y transporten los datos del error en lugar de un false mudo; el bloque finally y el try-with-resources que libera recursos por ti; y las estrategias profesionales de manejo de errores y logging, para que los avisos de BiblioTech dejen de ser System.out.println y pasen a ser registros que se puedan filtrar, archivar y analizar. Al terminarlo, BiblioTech dejará de caerse ante el primer dato inesperado y empezará a comportarse como el software que se pone en producción.

Ordenación y Búsqueda en Colecciones

Contenido

Orden natural con Comparable

El contrato de compareTo

El error de restar enteros

Coherencia con equals y qué se rompe sin ella

Comparator: orden externo y múltiple

El catálogo de métodos de Comparator