Java Collections: Cuándo usar Set, Map, List o Queue

Aprovechar las interfaces que ofrece el Collections Framework evita que el desarrollador gaste energía creando sus propias estructuras, permitiéndole enfocar sus esfuerzos en las áreas cruciales del desarrollo. Estas estructuras de datos y algoritmos de alta calidad y rendimiento mejoran la excelencia y la eficiencia de las aplicaciones, a la vez que fomentan la reutilización de software y posibilitan la compatibilidad entre APIs que no están intrínsecamente relacionadas.

¿Qué es el Collections Framework?

El Collections Framework es una estructura bien definida compuesta por un conjunto de interfaces y clases que sirven para representar y tratar grupos de datos como una única entidad, comúnmente llamada colección. Dentro del Collections Framework encontramos los siguientes elementos:

• Interfaces: Permiten la manipulación de las colecciones siguiendo el principio de “programar para interfaces y no para implementaciones”, lo que significa que el acceso a los objetos debe hacerse únicamente a través de los métodos definidos en esas interfaces.
• Implementaciones: Se refieren a las implementaciones concretas de las interfaces. Son las clases que proporcionan una implementación real de las interfaces y se usan para crear instancias específicas de colecciones.
• Algoritmos: Son métodos que ejecutan diversas operaciones sobre los objetos contenidos en las colecciones, incluyendo operaciones como búsqueda y ordenación.

Interfaces

• Collection: Se encuentra en la cima de la jerarquía. No existen implementaciones directas de esta interfaz, pero define las operaciones fundamentales para las colecciones, como agregar, eliminar, vaciar, entre otras.
• Set: Esta interfaz define una colección que no permite la inclusión de elementos duplicados. La interfaz SortedSet, que hereda de Set, permite el ordenamiento natural de los elementos, por ejemplo, en orden alfabético.
• List: Define una colección ordenada, donde se permiten elementos duplicados. Esta interfaz es la más apropiada cuando se necesita acceso aleatorio a los elementos usando sus índices.
• Queue: Es un tipo de colección que mantiene una lista de prioridades, donde el orden de los elementos se determina mediante la implementación de Comparable o Comparator. A través de la interfaz Queue, es posible crear colas y pilas.
• Map: Cada elemento contiene, en realidad, dos objetos: una clave y un valor. Los valores pueden duplicarse, pero las claves no. La interfaz SortedMap extiende Map y permite la clasificación ascendente de las claves. Un ejemplo de aplicación de esta interfaz es la clase Properties, utilizada para almacenar configuraciones y propiedades de un sistema.

Implementaciones

• ArrayList: Funciona como un array que puede crecer en tamaño. La búsqueda de un elemento es rápida, pero la inserción y eliminación de elementos son más lentas y proporcionales al tamaño de la estructura. Es la opción ideal cuando el acceso rápido a los elementos es prioritario. Por ejemplo, al crear un catálogo de tu biblioteca personal, donde cada libro recibe un número secuencial para acceder a él.
• LinkedList: Implementa una lista enlazada, en la que cada nodo contiene datos y una referencia al siguiente nodo. A diferencia de ArrayList, la búsqueda es más lenta, pero las inserciones y eliminaciones son rápidas. Por eso, prefiere LinkedList cuando exista la necesidad frecuente de insertar y eliminar elementos, como al gestionar las compras mensuales del supermercado.
• HashSet: Ofrece acceso rápido a los datos, pero no garantiza que estén ordenados. Es la opción adecuada cuando la solución requiere elementos únicos y el orden no es relevante. Por ejemplo, al crear un catálogo de tu música.
• TreeSet: Los datos están ordenados, pero el acceso es más lento que en HashSet. Usa TreeSet cuando necesites un conjunto de elementos únicos en orden natural. Se recomienda para las mismas aplicaciones que HashSet, con la ventaja del ordenamiento natural.
• LinkedHashSet: Derivado de HashSet, mantiene una lista doblemente enlazada de sus elementos. Los elementos se iteran en el orden de inserción o en el orden en que fueron accedidos en la última iteración. Es útil para registrar la llegada de corredores en un maratón.
• HashMap: Basado en una tabla hash, permite claves y valores nulos. No garantiza el ordenamiento de los datos. Elígelo cuando el orden no sea relevante y se necesite un identificador, como el ISBN en un catálogo de biblioteca personal.
• TreeMap: Implementa SortedMap y garantiza el ordenamiento ascendente de las claves. Puede especificar un orden personalizado. Úsalo cuando necesites un mapa ordenado. Similar a HashMap, pero con menor rendimiento.
• LinkedHashMap: Mantiene una lista doblemente enlazada de elementos, con iteración en el orden de inserción de las claves. Útil cuando el orden de inserción es importante, como al registrar corredores en un maratón.

Todas estas implementaciones tienen los métodos definidos en sus interfaces, aceptan elementos nulos y, en los mapas, tanto las claves como los valores pueden ser nulos. No son seguras para uso concurrente y son serializables, lo que permite guardar su estado, y admiten el método clone(), que crea copias de objetos.

Las colas se usan cuando se necesita semántica LIFO, FIFO o de eliminación por prioridad, y, finalmente, los mapas se usan cuando se necesita asociar claves con valores.

Lists

Comencemos con una tabla comparativa de listas. Las operaciones comunes para listas son agregar y eliminar elementos, acceder a un elemento por índice, recorrer los elementos y encontrar un elemento:

Como podemos ver, ArrayList es bueno para agregar y eliminar elementos al final, así como para tener acceso aleatorio a los elementos. Por otro lado, es malo para agregar y eliminar elementos en posiciones arbitrarias. Mientras tanto, LinkedList es bueno para agregar y eliminar elementos en cualquier posición. Sin embargo, no soporta acceso aleatorio verdadero O(1). Por lo tanto, en cuanto a listas, la elección por defecto es ArrayList, hasta que necesitemos agregar y eliminar elementos rápidamente en cualquier posición.

Sets

Para conjuntos, nos interesa agregar y eliminar elementos, recorrer elementos y encontrar un elemento:

Como podemos ver, la elección por defecto es la colección HashSet, ya que es muy rápida para todas las operaciones que soporta. Además, si el orden de inserción de los elementos también importa, optamos por LinkedHashSet. Básicamente, es una extensión de HashSet que mantiene el control del orden de inserción de los elementos usando internamente una estructura de lista enlazada.

Si los elementos necesitan estar ordenados y ese orden debe preservarse al agregar y eliminar elementos, entonces optamos por TreeSet.

Si los elementos del conjunto son solo valores de enumeración de un único tipo enum, entonces la opción más sabia es EnumSet.

Queue

Las colas pueden dividirse en dos grupos:

1. LinkedList, ArrayDeque - Las implementaciones de la interfaz Queue pueden actuar como estructuras de datos de pila, cola y deque. Por lo general, ArrayDeque es más rápido que LinkedList. Por lo tanto, es la opción por defecto.
2. PriorityQueue - Implementación de cola respaldada por una estructura de datos de heap binario. Se usa para la recuperación rápida (O(1)) de los elementos de mayor prioridad. Agregar y eliminar funcionan en tiempo O(log(n)).

Maps

De la misma forma que para conjuntos, consideramos las operaciones de agregar y eliminar elementos, el recorrido de elementos y la búsqueda de un elemento para los mapas:

La lógica de selección para mapas es similar a la lógica de selección para conjuntos: usamos HashMap por defecto, LinkedHashMap si el orden de inserción también importa, TreeMap para clasificación, y EnumMap cuando las claves pertenecen a valores de un tipo de enumeración específico.

Por último, existen dos implementaciones de la interfaz Map con aplicaciones muy específicas: IdentityHashMap y WeakHashMap.