Introducción a Colecciones en Java

En este tutorial vamos a ver qué son las colecciones de Java, los tipos más usados que hay y sus principales características.

Índice de contenidos

• 1. Introducción
• 2. Entorno
• 3. Qué son las colecciones?
• 4. Tipos de colecciones
  • 4.1. Set
  • 4.2. List
  • 4.3. Map
• 5. Stream API
• 6. Conclusiones
• 7. Referencias

1. Introducción

En este tutorial vamos a profundizar en las colecciones en Java. Vamos a ver qué son y los distintos tipos de colecciones más usados que existen (Set, List y Map). También, vamos a ver que cada uno de los distintos tipos de colecciones puede tener, además, distintas implementaciones, lo que ofrece funcionalidad distinta. Por último, veremos por encima una de las novedades de Java 8 en las colecciones como son los streams lo que nos permite trabajar con las colecciones de una forma mucho más óptima y eficiente.

2. Entorno

El tutorial se ha realizado usando el siguiente entorno:

• Hardware: Portátil MacBook Pro Retina 15′ (2.5 Ghz Intel Core I7, 16GB DDR3).
• Sistema Operativo: Mac OS Yosemite 10.10
• Entorno de desarrollo: IntelliJ IDEA
• Versión de Java: 1.8
• Versión de Maven: 3.1

3. ¿Qué son las colecciones?

Una colección representa un grupo de objetos. Esto objetos son conocidos como elementos. Cuando queremos trabajar con un conjunto de elementos, necesitamos un almacén donde poder guardarlos. En Java, se emplea la interfaz genérica Collection para este propósito. Gracias a esta interfaz, podemos almacenar cualquier tipo de objeto y podemos usar una serie de métodos comunes, como pueden ser: añadir, eliminar, obtener el tamaño de la colección… Partiendo de la interfaz genérica Collection extienden otra serie de interfaces genéricas. Estas subinterfaces aportan distintas funcionalidades sobre la interfaz anterior.

4. Tipos de colecciones

En este apartado, vamos a analizar los principales tipos de colecciones que se encuentran, por defecto, en la plataforma de Java.

4.1. Set

La interfaz Set define una colección que no puede contener elementos duplicados. Esta interfaz contiene, únicamente, los métodos heredados de Collection añadiendo la restricción de que los elementos duplicados están prohibidos. Es importante destacar que, para comprobar si los elementos son elementos duplicados o no lo son, es necesario que dichos elementos tengan implementada, de forma correcta, los métodos equals y hashCode. Para comprobar si dos Set son iguales, se comprobarán si todos los elementos que los componen son iguales sin importar en el orden que ocupen dichos elementos.

Dentro de la interfaz Set existen varios tipos de implementaciones realizadas dentro de la plataforma Java. Vamos a analizar cada una de ellas:

• HashSet: este implementación almacena los elementos en una tabla hash. Es la implementación con mejor rendimiento de todas pero no garantiza ningún orden a la hora de realizar iteraciones. Es la implementación más empleada debido a su rendimiento y a que, generalmente, no nos importa el orden que ocupen los elementos. Esta implementación proporciona tiempos constantes en las operaciones básicas siempre y cuando la función hash disperse de forma correcta los elementos dentro de la tabla hash. Es importante definir el tamaño inicial de la tabla ya que este tamaño marcará el rendimiento de esta implementación.
• TreeSet: esta implementación almacena los elementos ordenándolos en función de sus valores. Es bastante más lento que HashSet. Los elementos almacenados deben implementar la interfaz Comparable. Esta implementación garantiza, siempre, un rendimiento de log(N) en las operaciones básicas, debido a la estructura de árbol empleada para almacenar los elementos.
• LinkedHashSet: esta implementación almacena los elementos en función del orden de inserción. Es, simplemente, un poco más costosa que HashSet.

Ninguna de estas implementaciones son sincronizadas; es decir, no se garantiza el estado del Set si dos o más hilos acceden de forma concurrente al mismo. Esto se puede solucionar empleando una serie de métodos que actúan de wrapper para dotar a estas colecciones de esta falta de sincronización:

Set set = Collections.synchronizedSet(new HashSet());
SortedSet sortedSet = Collections.synchronizedSortedSet(new TreeSet());
Set set = Collections.synchronizedSet(new LinkedHashSet());

Una vez explicados los distintos tipos de Set, veremos cómo se crean y mostraremos sus diferencias en los tiempos de inserción. Como hemos visto anteriormente, el más rápido debería ser HashSet mientras que, por otro lado, el más lento debería ser TreeSet. Vamos a comprobarlo con el siguiente código:

final Set hashSet = new HashSet(1_000_000);
final Long startHashSetTime = System.currentTimeMillis();
for (int i = 0; i < 1_000_000; i++) {
    hashSet.add(i);
}
final Long endHashSetTime = System.currentTimeMillis();
System.out.println("Time spent by HashSet: " + (endHashSetTime - startHashSetTime));

final Set treeSet = new TreeSet();
final Long startTreeSetTime = System.currentTimeMillis();
for (int i = 0; i < 1_000_000; i++) {
    treeSet.add(i);
}
final Long endTreeSetTime = System.currentTimeMillis();
System.out.println("Time spent by TreeSet: " + (endTreeSetTime - startTreeSetTime));

final Set linkedHashSet = new LinkedHashSet(1_000_000);
final Long startLinkedHashSetTime = System.currentTimeMillis();
for (int i = 0; i < 1_000_000; i++) {
    linkedHashSet.add(i);
}
final Long endLinkedHashSetTime = System.currentTimeMillis();
System.out.println("Time spent by LinkedHashSet: " + (endLinkedHashSetTime - startLinkedHashSetTime));

A continuación, el resultado de los tiempos obtenidos:

Time spent by HashSet: 46
Time spent by TreeSet: 194
Time spent by LinkedHashSet: 74

Los tiempos obtenidos demuestran que, efectivamente, el tiempo de inserción es menor en HashSet y mayor en TreeSet. Es importante destacar que la inicialización del tamaño inicial del Set a la hora de su creación es importante ya que, en caso de insertar un gran número de elementos, podrían aumentar el número de colisiones y; con ello, el tiempo de inserción.

4.2. List

La interfaz List define una sucesión de elementos. A diferencia de la interfaz Set, la interfaz List sí admite elementos duplicados. A parte de los métodos heredados de Collection, añade métodos que permiten mejorar los siguientes puntos:

• Acceso posicional a elementos: manipula elementos en función de su posición en la lista.
• Búsqueda de elementos: busca un elemento concreto de la lista y devuelve su posición.
• Iteración sobre elementos: mejora el Iterator por defecto.
• Rango de operación: permite realizar ciertas operaciones sobre ragos de elementos dentro de la propia lista.

Dentro de la interfaz List existen varios tipos de implementaciones realizadas dentro de la plataforma Java. Vamos a analizar cada una de ellas:

• ArrayList: esta es la implementación típica. Se basa en un array redimensionable que aumenta su tamaño según crece la colección de elementos. Es la que mejor rendimiento tiene sobre la mayoría de situaciones.
• LinkedList: esta implementación permite que mejore el rendimiento en ciertas ocasiones. Esta implementación se basa en una lista doblemente enlazada de los elementos, teniendo cada uno de los elementos un puntero al anterior y al siguiente elemento.

Ninguna de estas implementaciones son sincronizadas; es decir, no se garantiza el estado del List si dos o más hilos acceden de forma concurrente al mismo. Esto se puede solucionar empleando una serie de métodos que actúan de wrapper para dotar a estas colecciones de esta falta de sincronización:

List list = Collections.synchronizedList(new ArrayList());
List list = Collections.synchronizedList(new LinkedList());

A continuación, vamos a ver cómo se crean los distintos tipos de interfaces:

final List arrayList = new ArrayList();
final List linkedList = new LinkedList();

El cuándo usar una implementación u otra de List variará en función de la situación en la que nos encontremos. Generalmente, ArrayList será la implementación que usemos en la mayoría de situaciones. Sobretodo, varían los tiempos de inserción, búsqueda y eliminación de elementos, siendo en unos casos una solución más óptima que la otra.

4.3. Map

La interfaz Map asocia claves a valores. Esta interfaz no puede contener claves duplicadas y; cada una de dichas claves, sólo puede tener asociado un valor como máximo.

Dentro de la interfaz Map existen varios tipos de implementaciones realizadas dentro de la plataforma Java. Vamos a analizar cada una de ellas:

• HashMap: este implementación almacena las claves en una tabla hash. Es la implementación con mejor rendimiento de todas pero no garantiza ningún orden a la hora de realizar iteraciones. Esta implementación proporciona tiempos constantes en las operaciones básicas siempre y cuando la función hash disperse de forma correcta los elementos dentro de la tabla hash. Es importante definir el tamaño inicial de la tabla ya que este tamaño marcará el rendimiento de esta implementación.
• TreeMap: esta implementación almacena las claves ordenándolas en función de sus valores. Es bastante más lento que HashMap. Las claves almacenadas deben implementar la interfaz Comparable. Esta implementación garantiza, siempre, un rendimiento de log(N) en las operaciones básicas, debido a la estructura de árbol empleada para almacenar los elementos.
• LinkedHashMap: esta implementación almacena las claves en función del orden de inserción. Es, simplemente, un poco más costosa que HashMap.

Ninguna de estas implementaciones son sincronizadas; es decir, no se garantiza el estado del Map si dos o más hilos acceden de forma concurrente al mismo. Esto se puede solucionar empleando una serie de métodos que actúan de wrapper para dotar a estas colecciones de esta falta de sincronización:

Map map = Collections.synchronizedMap(new HashMap());
SortedMap mortedMap = Collections.synchronizedSortedMap(new TreeMap());
Map map = Collections.synchronizedMap(new LinkedHashMap());

A continuación, vamos a ver cómo se crean los distintos tipos de interfaces:

final Map<Integer, List> hashMap = new HashMap<Integer, List>();
final Map<Integer, List> treeMap = new TreeMap<Integer, List>();
final Map<Integer, List> linkedHashMap = new LinkedHashMap<Integer, List>();

El cuándo usar una implementación u otra de Map variará en función de la situación en la que nos encontremos. Generalmente, HashMap será la implementación que usemos en la mayoría de situaciones. HashMap es la implementación con mejor rendimiento (como se ha podido comprobar en el análisis de Set), pero en algunas ocasiones podemos decidir renunciar a este rendimiento a favor de cierta funcionalidad como la ordenación de sus elementos.

5. Stream API

Gracias a la llegada de Java 8, las colecciones han aumentado su funcionalidad con la llegada de los streams. Los streams permiten realizar operaciones funcionales sobre los elementos de las colecciones.

A continuación, mostramos un ejemplo de las bondades de los streams donde, a partir de una lista de personas (donde cada una de ellas tiene un nombre), obtenemos una lista con todos los nombres:

List people = new ArrayList();
List names = people.stream().map(Person::getName).collect(Collectors.toList());

Como hemos visto en el ejemplo, de una forma muy fácil hemos obtenido todos los nombres. Para más detalles de este tipo de novedades, tenemos un Curso de Java 8 con el que se podrán ahondar en este tipo de conocimientos.

6. Conclusiones

Como hemos visto a lo largo de este tutorial, Java proporciona una serie de esturctura muy variadas para almacenar datos. Estas estructuras, ofrecen diversas funcionalidades: ordenación de elementos, mejora de rendimiento, rango de operaciones… Es importante conocer cada una de ellas para saber cuál es la mejor situación para utilizarlas. Un buen uso de estas estructuras mejorará el rendimiento de nuestra aplicación.

Para conocer qué tipo de colección usar, podemos emplear el siguiente diagrama:

Además, gracias a Java 8 y sus streams, las operaciones con las colecciones pueden ser mucho más óptimas.

7. Referencias

• Documentación de Java sobre colecciones