Introducción a las Colecciones en Java

Antes de adentrarnos en las colecciones, es útil entender la diferencia fundamental entre los arreglos (Arrays) y las colecciones en Java:

• Los arreglos tienen un tamaño fijo y solo pueden almacenar elementos del mismo tipo de dato (primitivos o de referencia).
• Las colecciones de Java permiten almacenar y manipular un número variable de objetos. Son ideales cuando no se conoce de antemano la cantidad de elementos o cuando se necesita que la capacidad se expanda automáticamente.

Java proporciona utilidades para la conversión mutua entre arreglos y colecciones mediante los métodos toArray() y Arrays.asList().

El Paquete java.util

Las clases de colecciones en Java se encuentran principalmente en el paquete java.util. Es importante recordar que las colecciones almacenan referencias a objetos, no los objetos en sí mismos. Para simplificar, nos referiremos a las referencias como los elementos de la colección.

Las estructuras de datos de colección principales son tres: Set (conjunto), List (lista) y Map (mapa).

Relación Jerárquica de las Interfaces

La jerarquía de las interfaces de colecciones en Java se organiza de la siguiente manera:

Collection
├── List
│   ├── LinkedList
│   ├── ArrayList
│   └── Vector (Clase legada)
│       └── Stack (Clase legada)
└── Set
Map (Interfaz independiente, no extiende Collection)
   ├── Hashtable (Clase legada)
   ├── HashMap
   └── WeakHashMap
   

1. La Interfaz Collection

---

Collection es la interfaz base que representa un grupo de objetos. Las implementaciones concretas no heredan directamente de Collection, sino de sus subinterfaces como List y Set.

Las clases que implementan Collection deben proporcionar dos constructores:

• Un constructor sin argumentos para crear una colección vacía.
• Un constructor que acepta otra Collection para crear una nueva colección con los mismos elementos que la colección proporcionada (útil para copias).

Para recorrer los elementos de cualquier Collection, se utiliza el método iterator(), que devuelve un objeto Iterator. Este iterador permite acceder a cada elemento secuencialmente:

Iterator it = collection.iterator(); // Obtiene el iterador
while(it.hasNext()) {
   Object obj = it.next(); // Obtiene el siguiente elemento
   // Procesar el objeto
}
   

2. La Interfaz Set

---

Set, una subinterfaz de Collection, representa un conjunto matemático. La característica principal de un Set es que no permite elementos duplicados. Es decir, para cualquier par de elementos e1 y e2 en el conjunto, e1.equals(e2) debe ser false.

Dado que Set se enfoca en la pertenencia de elementos y no en el acceso por índice, no introduce nuevos métodos además de los heredados de Collection.

Implementaciones Comunes de Set:

• HashSet: Utiliza una tabla hash internamente (basada en HashMap) para almacenar los elementos. Ofrece un rendimiento promedio constante (O(1)) para las operaciones de adición, eliminación y búsqueda. No garantiza ningún orden particular de los elementos.
• TreeSet: Implementa un árbol balanceado (basado en TreeMap) para almacenar los elementos. Mantiene los elementos ordenados según su orden natural o un Comparator proporcionado. Las operaciones de adición, eliminación y búsqueda tienen una complejidad logarítmica (O(log n)).

La optimización del espacio en HashSet se puede lograr ajustando la capacidad inicial y el factor de carga. TreeSet no tiene opciones de ajuste de rendimiento directo, ya que su estructura de árbol balanceado garantiza la complejidad O(log n).

Tanto HashSet como TreeSet implementan la interfaz Cloneable.

TreeSet es particularmente útil cuando se necesita recuperar los elementos de un conjunto en un orden específico. Para que esto funcione correctamente, los elementos añadidos a un TreeSet deben ser comparables (implementar Comparable o proporcionar un Comparator).

Ejemplo de Uso de Set:

import java.util.*;

public class SetExample {
   public static void main(String[] args) {
       // HashSet: No garantiza orden, no permite duplicados
       Set<string> stringSet = new HashSet<>();
       stringSet.add("Berna");
       stringSet.add("Elisabeth");
       stringSet.add("Gene");
       stringSet.add("Elisabeth"); // Este duplicado será ignorado
       stringSet.add("Clara");
       System.out.println("HashSet: " + stringSet);

       // TreeSet: Mantiene los elementos ordenados
       Set<string> sortedSet = new TreeSet<>(stringSet);
       System.out.println("TreeSet (ordenado): " + sortedSet);
   }
}
   </string></string>

La ejecución de este código producirá una salida similar a:

HashSet: [Gene, Clara, Berna, Elisabeth] // El orden puede variar
TreeSet (ordenado): [Berna, Clara, Elisabeth, Gene]
   

3. La Interfaz List

---

La interfaz List extiende a Collection y representa una secuencia ordenada de elementos. A diferencia de Set, List permite elementos duplicados y mantiene el orden en que se insertaron los elementos.

List introduce métodos orientados a la posición para añadir, eliminar, obtener y modificar elementos en índices específicos. También puede generar un ListIterator, que permite la navegación bidireccional y la modificación de la lista durante la iteración.

Implementaciones Comunes de List:

• ArrayList: Implementado sobre un arreglo dinámico. Ofrece acceso rápido a los elementos por índice (O(1)), pero las operaciones de inserción y eliminación en medio de la lista son lentas (O(n)) porque requieren desplazar los elementos posteriores.
• LinkedList: Implementado como una lista doblemente enlazada. Las operaciones de inserción y eliminación en cualquier posición son eficientes (O(1)), pero el acceso a elementos por índice es más lento (O(n)) ya que requiere recorrer la lista desde el principio o el final. LinkedList también proporciona métodos específicos para usarla como pila o cola (addFirst(), addLast(), removeFirst(), removeLast(), etc.).
• Vector: Una clase legada (anterior a la introducción del framework de colecciones moderno) que implementa un arreglo dinámico. Es sincronizado, lo que sginifica que es seguro para usar en entornos multihilo, pero esto introduce una sobrecarga de rendimiento. Generalmente, se prefiere ArrayList y se sincroniza explícitamente si es necesario.
• Stack: Una clase legada que hereda de Vector y proporciona la funcionalidad de una pila (LIFO - Last-In, First-Out) mediante métodos como push() y pop().

Operaciones Orientadas a la Posición en List:

Los métodos clave que diferencian a List de Collection incluyen:

void add(int index, E element);      // Inserta un elemento en una posición específica
boolean addAll(int index, Collection<? extends E> c); // Inserta todos los elementos de otra colección
E get(int index);                   // Obtiene el elemento en un índice
int indexOf(Object o);              // Devuelve el índice de la primera ocurrencia del elemento
int lastIndexOf(Object o);          // Devuelve el índice de la última ocurrencia del elemento
E remove(int index);                // Elimina el elemento en el índice especificado
E set(int index, E element);        // Reemplaza el elemento en el índice especificado y devuelve el anterior
   

Los métodos para sublistas y iteradores específicos:

ListIterator<E> listIterator(); // Devuelve un ListIterator
ListIterator<E> listIterator(int startIndex); // Devuelve un ListIterator a partir de un índice
List<E> subList(int fromIndex, int toIndex); // Devuelve una vista de la porción de la lista entre fromIndex (incluido) y toIndex (excluido)
   

Es importante notar que la subList() devuelve una vista, y las modificaciones a esta vista afectan a la lista original, y viceversa.

Comparación entre Set y List

• Orden: List mantiene el orden de inserción, mientras que HashSet no garantiza ningún orden, y TreeSet mantiene el orden natural o según un Comparator.
• Duplicados: List permite elementos duplicados, mientras que Set no los permite.
• Rendimiento:
  • HashSet: Rápido para inserción/eliminación (O(1) promedio). Búsqueda eficiente pero sin orden.
  • TreeSet: Ordenado, inserción/eliminación/búsqueda O(log n).
  • ArrayList: Acceso rápido por índice (O(1)). Inserción/eliminación lenta (O(n)).
  • LinkedList: Inserción/eliminación rápida (O(1)). Acceso por índice lento (O(n)).
• Uso: Use Set cuando necesite almacenar elementos únicos y no le importe el orden (HashSet) o necesite que estén ordenados (TreeSet). Use List cuando necesite mantener el orden de los elementos y permitir duplicados. Elija entre ArrayList y LinkedList según si prioriza el acceso aleatorio o las inserciones/eliminaciones eficientes.

4. La Interfaz Map

---

A diferencia de Set y List, la interfaz Map no extiende Collection. Map representa una colección de pares clave-valor, donde cada clave es única.

Las operaciones principales de Map se pueden agrupar en:

• Operaciones de Modificación: Añadir y eliminar pares clave-valor. Tanto las claves como los valores pueden ser null (excepto en Hashtable). ```java

  V put(K key, V value); // Asocia el valor especificado con la clave especificada, devuelve el valor anterior o null V remove(Object key); // Elimina el mapeo para una clave void putAll(Map<? extends K, ? extends V> m); // Copia todos los mapeos de otro Map void clear(); // Elimina todos los mapeos

• Operaciones de Consulta: Verificar el contenido del mapa. ```java

  V get(Object key); // Devuelve el valor asociado a la clave boolean containsKey(Object key); // Devuelve true si el mapa contiene una clave boolean containsValue(Object value); // Devuelve true si el mapa contiene un valor int size(); // Devuelve el número de pares clave-valor boolean isEmpty(); // Devuelve true si el mapa está vacío

• Vistas Opcionales: Proporcionan vistas de las claves, valores o entradas (pares clave-valor) como colecciones. ```java

  Set<K> keySet(); // Devuelve un Set con todas las claves Collection<V> values(); // Devuelve una Collection con todos los valores Set<Map.Entry<K, V>> entrySet(); // Devuelve un Set con las entradas (pares clave-valor)

La Interfaz Map.Entry

El método entrySet() de un Map devuelve un conjunto de objetos que implementan la interfaz Map.Entry. Cada Map.Entry representa un par clave-valor individual y permite acceder tanto a la clave como al valor, e incluso modificar el valor mediante setValue().

Implementaciones Comunes de Map:

• HashMap: Implementación basada en tabla hash. Ofrece un rendimiento promedio constante (O(1)) para las operaciones principales. No garantiza el orden de las entradas. Permite una clave y un valor null.
• TreeMap: Implementación basada en un árbol balanceado (Red-Black Tree). Mantiene las entradas ordenadas por clave según su orden natural o un Comparator. Las operaciones tienen una complejidad logarítmica (O(log n)). Las claves no pueden ser null si se usa el orden natural.
• Hashtable: Una clase legada (similar a HashMap pero sincronizada y no permite claves ni valores null). Generalmente se prefiere HashMap.
• WeakHashMap: Una implementación especializada donde las entradas pueden ser eliminadas automáticamente por el recolector de basura si la clave ya no es referenciada por ninguna otra parte del programa.

Para obtener el mejor rendimiento genarel en operaciones de inserción, eliminación y búsqueda, HashMap es la opción preferida. Si necesita iterar sobre las claves en orden, TreeMap es la elección adecuada. A veces, puede ser más eficiente poblar un HashMap y luego convertirlo a un TreeMap si se necesita ordenación posterior.

El uso de HashMap requiere que las claves implementen correctamente los métodos hashCode() y equals(). TreeMap requiere que las claves sean comparables.

Ejemplo de Uso de Map:

El siguiente programa cuenta la frecuencia de palabras en los argumentos de la línea de comandos.

import java.util.*;

public class MapExample {
   public static void main(String[] args) {
       Map<string integer=""> wordFrequencies = new HashMap<>();
       Integer countOne = Integer.valueOf(1); // Usar Integer.valueOf es más eficiente que new Integer(1)

       for (String word : args) {
           // Obtiene la frecuencia actual, o null si la palabra no está en el mapa
           Integer currentFrequency = wordFrequencies.get(word);

           if (currentFrequency == null) {
               // Si es la primera vez que vemos la palabra, la añadimos con frecuencia 1
               wordFrequencies.put(word, countOne);
           } else {
               // Si ya existe, incrementamos su frecuencia
               int frequencyValue = currentFrequency.intValue();
               wordFrequencies.put(word, Integer.valueOf(frequencyValue + 1));
           }
       }

       System.out.println("Frecuencias (HashMap - desordenado): " + wordFrequencies);

       // Crear un TreeMap a partir del HashMap para mostrar las claves ordenadas
       Map<string integer=""> sortedFrequencies = new TreeMap<>(wordFrequencies);
       System.out.println("Frecuencias (TreeMap - ordenado por clave): " + sortedFrequencies);
   }
}
   </string></string>

Ejecutando con argumentos como: "the quick brown fox jumps over the lazy dog" podría producir:

Frecuencias (HashMap - desordenado): {dog=1, lazy=1, fox=1, brown=1, jumps=1, over=1, quick=1, the=2}
Frecuencias (TreeMap - ordenado por clave): {brown=1, dog=1, fox=1, jumps=1, lazy=1, over=1, quick=1, the=2}
   

Conceptos Clave y Aclaraciones

1. ¿Qué es un Iterator?

Un Iterator es una interfaz que permite recorrer los elementos de una colección de manera uniforme, independientemente de la implementación subyacente. Proporciona métodos como hasNext() para verificar si hay más elementos y next() para obtener el siguiente elemento. Generalmente, no se recomienda modificar la colección mientras se itera con un Iterator, ya que puede lanzar una ConcurrentModificationException.

2. Diferencia entre Iterator y ListIterator

Iterator solo permite la iteración hacia adelante y la eliminación de elementos. ListIterator, que es una extensión de Iterator y solo se aplica a las List, permite la iteración bidireccional (adelante y atrás), la inserción de elementos y la modificación del elemento actual.

3. ¿Qué son HashMap y Map?

Map es una interfaz que define el contrato para almacenar pares clave-valor. HashMap es una clase concreta que implementa la interfaz Map utilizando una tabla hash.

4. Diferencias entre HashMap y Hashtable

• Sincronización: Hashtable es sincronizado (thread-safe), mientras que HashMap no lo es.
• Nulos: HashMap permite una clave null y múltiples valores null. Hashtable no permite claves ni valores null.
• Rendimiento: Dado que HashMap no está sincronizado, suele ser más rápido que Hashtable en entornos monohilo.
• Orden: HashMap no garantiza el orden de iteración. Hashtable tampoco. Si se necesita un orden predecible, se puede usar LinkedHashMap (que mantiene el orden de inserción) o TreeMap (que mantiene el orden de claves).
• Legado: Hashtable es una clase legada, mientras que HashMap es parte del framework de colecciones introducido en Java 2 (JDK 1.2).

5. ¿Qué significa "sincronizado" en el contexto de Hashtable?

Un objeto sincronizado garantiza que solo un hilo puede aceder y modificar sus datos en un momento dado. Cuando un hilo invoca un método en un objeto sincronizado (como Hashtable), adquiere un "bloqueo" sobre ese objeto. Otros hilos que intenten acceder al mismo objeto tendrán que esperar a que el bloqueo se libere.

6. ¿Qué es la característica "Fail-Fast"?

La característica "Fail-Fast" (fallo rápido) se aplica a los iteradores de ciertas colecciones (como HashMap y ArrayList). Si una colección es modificada estructuralmente (añadiendo o eliminando elementos) por un hilo después de que se ha creado un iterador para ella, y otro hilo intenta usar ese iterador, se lanzará una ConcurrentModificationException. Esto ayuda a detectar errores de concurrencia de manera temprana.

7. ¿Cómo hacer que un HashMap sea sincronizado?

Se puede obtener una versión sincronizada de un HashMap utilizando el método de utilidad Collections.synchronizedMap():

Map<K, V> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
   

Es importante notar que este método devuelve un "mapa envuelto" (wrapper) sincronizado. Si se necesita sincronizar operaciones de iteración complejas, se debe hacer manualmente bloqueando el mapa envuelto.

8. ¿Cuándo usar Hashtable y cuándo HashMap?

En la mayoría de los casos, se prefiere HashMap por su mayor rendimiento y flexibilidad (permitiendo nulos). Use HashMap a menos que necesite específicamente la sincronización inherente de Hashtable (lo cual es raro, ya que Collections.synchronizedMap() ofrece una forma más controlada de sincronizar). Si necesita un orden predecible, considere LinkedHashMap o TreeMap.

9. ¿Por qué Vector está en desuso y se prefiere ArrayList?

Vector es una clase legada y, al igual que Hashtable, tiene la desventaja de que todos sus métodos están sincronizados por defecto. Esto significa que incluso si no necesita sincronización, incurre en la sobrecarga de esta. ArrayList, en cambio, no está sincronizado, lo que lo hace más rápido. Si se necesita sincronización, es mejor usar ArrayList y envolverlo con Collections.synchronizedList(), lo que permite un control más fino sobre cuándo y cómo se aplican los bloqueos (por ejemplo, para operaciones complejas que involucran múltiples pasos).

Además, Vector tiene algunos métodos de enumeración legados (elements()) que no son tan robustos ni seguros como los iteradores modernos. Aunque Vector no ha sido formalmente declarado obsoleto por Oracle, las buenas prácticas de desarrollo recomiendan usar ArrayList.