El framework de colecciones de Java: listas, sets, mapas y colas

Todo programa Java que maneja más de una cosa a la vez usa java.util. El framework es lo bastante pequeño como para aprenderlo entero —un puñado de interfaces y una docena de implementaciones que de verdad vas a usar—, pero lo bastante detallado como para que elegir LinkedList donde tocaba ArrayList, o HashMap donde hacía falta TreeMap, te cueste rendimiento o corrección sin que lo notes. Esta guía te da la jerarquía, el modelo de costes, las reglas del hashing y del orden, y las operaciones a las que recurren los desarrolladores con experiencia. El código está pensado para Java 21.

La jerarquía de interfaces

El framework separa lo que promete una colección (las interfaces) de cómo guarda los datos (las implementaciones). Programa contra la interfaz y elige la implementación en el momento de construirla.

Iterable
└── Collection
    ├── List          ordered, indexed, duplicates allowed
    ├── Set           no duplicates
    │   └── SortedSet → NavigableSet   sorted by natural order or Comparator
    └── Queue         head-first access
        └── Deque     both ends

Map (not a Collection)   key → value, unique keys
└── SortedMap → NavigableMap

Map queda fuera de Collection a propósito: un mapa es un conjunto de asociaciones, no una bolsa de elementos, y sus métodos keySet(), values() y entrySet() son las vistas a través de las cuales lo tratas como una colección.

Java 21 añadió las colecciones secuenciadas (JEP 431): SequencedCollection, SequencedSet y SequencedMap dan a List, Deque, LinkedHashSet, LinkedHashMap y a los tipos ordenados unos métodos uniformes getFirst(), getLast(), addFirst(), removeLast() y reversed(). Antes de la 21 necesitabas list.get(list.size() - 1) o recorrer un ListIterator hacia atrás.

Listas

Una List es una secuencia ordenada con acceso por posición. Hay dos implementaciones que importan.

ArrayList guarda los elementos en un array que crece (alrededor de la mitad de su tamaño) cuando se llena. El acceso por índice es de tiempo constante, añadir al final es de tiempo constante amortizado, e insertar o eliminar en medio cuesta desplazar en memoria la parte final, algo rápido en la práctica porque System.arraycopy es un bucle nativo muy ajustado. La iteración aprovecha bien la caché. Es la lista por defecto.

LinkedList es una cadena de nodos doblemente enlazados. El acceso por posición recorre la lista desde un extremo, así que get(i) es lineal; cada nodo es un objeto aparte con dos punteros, de modo que la memoria es de tres a cuatro veces la de un ArrayList para elementos pequeños y la iteración va saltando por todo el heap. Solo gana al eliminar en un cursor ya posicionado por un ListIterator. También implementa Deque, pero ArrayDeque hace ese trabajo mejor.

List<String> hosts = new ArrayList<>(List.of("db1", "db2", "cache"));
hosts.add("queue");
hosts.set(0, "db-primary");
hosts.remove("cache");               // remove by value (first match)
hosts.remove(0);                      // remove by index — beware with List<Integer>
String last = hosts.getLast();        // Java 21
hosts.sort(Comparator.naturalOrder());

La trampa de la sobrecarga de remove es real: List<Integer> tiene tanto remove(int index) como remove(Object o), y list.remove(3) elige la versión por índice. Escribe list.remove(Integer.valueOf(3)) para eliminar por valor.

Sets y el contrato de hashing

Un Set rechaza los duplicados, entendiendo por «duplicado» que equals devuelve true. Cómo los detecta depende de la implementación.

HashSet guarda los elementos en una tabla hash. add, contains y remove son de tiempo constante en promedio; el orden de iteración no está especificado y puede cambiar cuando el set se redimensiona. Se apoya en el contrato de Object: los elementos que son iguales según equals deben tener el mismo hashCode. Si rompes ese contrato (sobrescribiendo uno sin el otro), el set guarda «duplicados» o no encuentra elementos que contiene. Desde Java 8, un bucket con muchas claves en colisión pasa a ser un árbol equilibrado en lugar de una lista enlazada, así que las funciones hash patológicas hacen menos daño, pero un buen hashCode sigue importando.

LinkedHashSet es un HashSet que además mantiene una lista enlazada con el orden de inserción. Mismo coste, iteración predecible y algo más de memoria. Úsalo cuando tests, logs o usuarios vayan a ver el orden.

TreeSet mantiene los elementos ordenados en un árbol rojo-negro según su orden natural (Comparable) o un Comparator que le pases. Las operaciones son logarítmicas y ganas consultas por rango: headSet, tailSet, subSet, ceiling, floor. Un TreeSet decide la igualdad con compareTo o compare, no con equals, así que un comparador que devuelva 0 para elementos distintos descartará uno de ellos.

EnumSet es un vector de bits especializado en elementos de un enum: diminuto, rapidísimo y la elección correcta siempre que el tipo de los elementos sea un enum.

record Tag(String name) implements Comparable<Tag> {
    @Override public int compareTo(Tag o) { return name.compareToIgnoreCase(o.name); }
}

Set<Tag> tags = new TreeSet<>();
tags.add(new Tag("Java"));
tags.add(new Tag("java"));           // compareTo says equal → not added
System.out.println(tags.size());     // 1, even though the records are not equals()

Mapas

Un Map asocia claves únicas con valores. Se aplican las mismas tres estrategias de almacenamiento.

La interfaz Map ganó en Java 8 una serie de métodos que sustituyen el clásico baile de «comprobar y luego hacer put»:

Map<String, List<String>> byDept = new HashMap<>();

// Before Java 8
List<String> names = byDept.get("eng");
if (names == null) { names = new ArrayList<>(); byDept.put("eng", names); }
names.add("Ada");

// Now
byDept.computeIfAbsent("eng", k -> new ArrayList<>()).add("Ada");

Map<String, Integer> counts = new HashMap<>();
counts.merge("java", 1, Integer::sum);            // increment or initialise
int hits = counts.getOrDefault("kotlin", 0);
counts.putIfAbsent("scala", 0);
counts.replaceAll((k, v) -> v * 2);

computeIfAbsent, merge y getOrDefault son los tres que debes memorizar. Recorre un mapa con entrySet() cuando necesites las dos mitades; recorrer keySet() y llamar a get por cada clave hace dos búsquedas por entrada.

LinkedHashMap tiene un flag en el constructor para el orden de acceso y un hook removeEldestEntry que, juntos, permiten montar una caché LRU acotada en unas diez líneas: una pregunta de entrevista habitual y, de vez en cuando, una herramienta útil en producción.

Las claves deben ser estables. Una clave cuyo hashCode cambia después de insertarla (un objeto mutable con un hash basado en sus campos) se pierde: el mapa la busca en el bucket del nuevo hash y nunca la encuentra. Usa claves inmutables: strings, números, enums, records.

Colas, deques y pilas

Queue ofrece acceso por la cabeza con dos familias de métodos: add/remove/element lanzan una excepción cuando no pueden completarse, mientras que offer/poll/peek devuelven false o null. Deque extiende esto a ambos extremos.

ArrayDeque es un array circular redimensionable y la implementación adecuada tanto para una cola FIFO como para una pila LIFO. Es más rápida que LinkedList en los dos casos y más rápida que la vieja clase Stack, que está sincronizada y extiende Vector; no uses Stack en código nuevo.

PriorityQueue es un heap binario que siempre devuelve el elemento más pequeño según el orden natural o el comparador. Insertar y extraer son operaciones logarítmicas; recorrerla no devuelve los elementos ordenados, solo poll() lo garantiza.

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop());   // second

Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.addAll(List.of(3, 9, 1));
System.out.println(pq.poll());     // 9

Las variantes bloqueantes —ArrayBlockingQueue, LinkedBlockingQueue— añaden put y take, que esperan, y forman parte de la caja de herramientas de la concurrencia.

Iteración, orden y modificación

El bucle for-each se compila a un Iterator: hasNext(), next(), y vuelta a empezar. La mayoría de las colecciones no concurrentes son fail-fast: si la colección sufre una modificación estructural durante la iteración por cualquier vía que no sea el propio remove del iterador, el siguiente next() lanza ConcurrentModificationException. Es una detección de bugs hecha en la medida de lo posible, no una garantía de thread-safety.

List<Order> orders = ...;

// Wrong: throws ConcurrentModificationException
for (Order o : orders) if (o.isCancelled()) orders.remove(o);

// Right, and shortest
orders.removeIf(Order::isCancelled);

// Also right, when you need the iterator anyway
for (Iterator<Order> it = orders.iterator(); it.hasNext(); ) {
    if (it.next().isCancelled()) it.remove();
}

Ordenar se hace o bien in situ —list.sort(comparator) o Collections.sort(list)— o bien en una colección nueva con un stream. Comparator se compone bien: Comparator.comparing(Person::lastName).thenComparing(Person::firstName).reversed(), con nullsFirst/nullsLast para los campos opcionales. La ordenación es un merge sort estable (TimSort), así que los elementos iguales conservan su orden relativo, lo que importa cuando ordenas por una clave y luego por otra.

Colecciones inmutables y vistas

Java 9 introdujo unas factorías cómodas: List.of(...), Set.of(...), Map.of(k1, v1, ...), Map.ofEntries(...), y Java 10 añadió List.copyOf, Set.copyOf y Map.copyOf. Devuelven colecciones no modificables: cualquier método mutador lanza UnsupportedOperationException, los elementos null se rechazan y Set.of/Map.of lanzan una excepción ante claves duplicadas. Su orden de iteración se aleatoriza a propósito en cada ejecución de la JVM para que nadie dependa de él por accidente.

Distingue tres cosas que se parecen:

• Colección inmutable (List.of): no puede cambiar nunca.
• Vista no modificable (Collections.unmodifiableList(inner)): no puedes cambiarla a través de la vista, pero si cambia la original, la vista lo refleja. Útil para exponer estado interno sin copiarlo.
• Copia defensiva (new ArrayList<>(inner) o List.copyOf(inner)): una instantánea que ninguna de las dos partes puede alterar.

Las vistas están por todo el framework: map.keySet(), list.subList(a, b) y Arrays.asList(array) son ventanas vivas a otros datos. Eliminar de keySet() elimina del mapa; vaciar una subList elimina ese rango de la lista. Potente cuando es intencionado, sorprendente cuando no lo es.

Collections ofrece también synchronizedList y compañía, que envuelven cada método en un lock. Hacen seguras las llamadas individuales, pero no las secuencias de llamadas (comprobar y luego actuar) ni la iteración, y en gran medida han quedado sustituidas por las colecciones de java.util.concurrent.

Elegir una implementación

Indica una capacidad inicial cuando conozcas el tamaño: new ArrayList<>(10_000) o HashMap.newHashMap(expected) (Java 19) evitan una serie de redimensionamientos. Y cuida la colección que devuelves: devolver List.of() o Collections.emptyList() no cuesta nada, mientras que crear un ArrayList vacío en cada llamada acaba sumando.

Errores comunes

Claves hash mutables. Un Set<Point> en el que Point tiene setters, o un mapa cuya clave es una lista a la que luego añades elementos, pierde elementos sin avisar. Las claves deben ser inmutables.

Depender del orden de HashMap. No está especificado y cambia con los redimensionamientos y la versión del JDK. Los tests que pasan por suerte fallan tras un refactor.

Arrays.asList sobre un array de primitivos. Arrays.asList(new int[]{1, 2}) da una List<int[]> con un solo elemento. Usa IntStream.of(...).boxed().toList() o un Integer[].

Tratar subList como una copia. Es una vista; los cambios estructurales en la lista padre la invalidan, y los cambios hechos a través de ella alteran esa lista padre.

Usar LinkedList como cola o Stack como pila. ArrayDeque es más rápida y más ligera en ambos casos.

Null en las colecciones modernas. List.of, Map.of y ConcurrentHashMap rechazan null. Decide de antemano si null tiene sentido en tus datos; normalmente no lo tiene, y Optional o un valor centinela explícito resultan más claros.

Recorrer keySet() y luego llamar a get. Dos búsquedas por entrada; recorre entrySet().

Un comparador de TreeSet incoherente con equals. Los elementos que el comparador considera iguales se deduplican aunque equals no esté de acuerdo. O los haces coherentes, o documentas la diferencia.

Puntos clave

• Declara las variables por su interfaz (List, Set, Map, Deque) y elige la implementación al construirlas.
• ArrayList, HashSet, HashMap y ArrayDeque son las opciones por defecto; recurre a Linked* cuando importe el orden de iteración y a Tree* cuando necesites ordenar o hacer consultas por rango.
• Las colecciones basadas en hash dependen de un par equals/hashCode coherente y de claves que nunca cambien; las basadas en árboles dependen solo del comparador.
• Modifica durante la iteración únicamente con removeIf o con el iterador; cualquier otra cosa lanza ConcurrentModificationException.
• List.of y compañía son inmutables y hostiles a null; Collections.unmodifiable* y subList son vistas vivas; copyOf y los constructores de copia son instantáneas.
• Usa computeIfAbsent, merge y getOrDefault en lugar de comprobar y luego hacer put, y entrySet() para iterar.