Genéricos y Colecciones. Parte 2: Colecciones

En este post se hablara del Java Collections Framework, el cual contiene interfaces y clases para manipular las estructuras de datos que hacen posibles las colecciones de objetos.

Con el framework de colecciones de Java los desarrolladores usamos estructuras de datos sin tener que enterarnos de cómo están implementadas. Lo cual ahorra mucho tiempo y nos da la seguridad de que tendremos un performance al menos aceptable.

¿Qué es una colección?

Una colección es un objeto que se utiliza para contener (hacer referencia) a un conjunto de objetos, usualmente del mismo tipo. Estos objetos son comúnmente conocidos como elementos.

Algunos ejemplos de colecciones son:

• Tu circulo de amigos del Google +

• Las cartas de un juego de baraja española

• La lista de empleados del área de sistemas

Qué se puede hacer con una colección

Estas son algunas funciones que se pueden realizar utilizando colecciones.

• Agregar objetos a una colección

• Quitar objetos de la colección

• Encontrar un objeto o un grupo de objetos en una colección

• Recuperar un objeto de una colección (sin quitarlo de la colección)

• Iterar a través de una colección, viendo cada elemento, uno después de otro. 

Clases e interfaces clave

Las interfaces del framework de colecciones declaran operaciones que pueden ser usadas genéricamente en varios tipos de colecciones. En el examen de certificación se necesitara saber en base a un requerimiento qué colección se debe usar. Por eso es importante conocer las principales clases e interfaces de este framework. Las interfaces mas importantes para el examen son:

Collection	Set	SortedSet
List	Map	SortedMap
Queue	NavigableSet	NavigableMap

Las clases mas importantes son:

Maps	Sets	Lists	Queues	Utilities
HashMap	HashSet	ArrayList	PriorityQueue	Collections
Hashtable	LinkedHashSet	Vector		Arrays
TreeMap	TreeSet	LinkedList
LinkedHashMap

No todas las colecciones del Collection Framework implementan la interfaz Collection. Ninguna de las clases e interfaces relacionadas con Map derivan de Collection, aunque pueden ser vistas como colecciones.

Nota. Los elementos subrayados no implementan ni derivan de la interfaz Collection.

En la siguiente imagen se muestra la herencia de clases para las colecciones.



Tip. Los términos Collection y Collections podrían ser confundidos a la hora del examen. Collections (en plural) es una clase con métodos estáticos, mientras que Collection (en singular) es la interfaz donde se declaran los métodos comunes las colecciones.

Sabores de las colecciones

Las colecciones vienen en 4 sabores:

• List ---> Listas de Objetos.

• Sets ---> Objetos únicos.

• Maps ---> Objetos con un único Id.

• Queues ---> Objetos acomodados según la forma en como serán procesados.

Aunque hay 4 sub-sabores más.

• Sorted ---> El acomodo de la colección se da según ciertas reglas (basado en las propiedades de los objetos).

• Unsorted

• Ordered ---> El orden de los elementos es independiente de los valores (orden establecido cuando se inserta un elemento, de acuerdo a la ultima vez que se acceso a ese elemento o en la posición en la que fue agregado).

• Unordered

Una colección puede ser ordered sin ser sorted. Pero una colección no puede ser sorted sin ser ordered, ya que el sorted es una forma especifica de ordered.

A continuación se listan las interfaces del Framework Collections:

Interfaz List

La interfaz List está implementada por las clases ArrayList, Vector y LinkedList. Ocurre un autoboxing cuando se agregan tipos primitivos a objetos de esas clases, porque ellos solo almacenan referencias a objetos.

Características:

• Se basa en los índices. Es el máximo diferencial respecto a otras colecciones.

• Están permitidos los elementos duplicados en las listas.

• Contienen un conjunto de métodos que nos permiten:

  • Acceso posicional

  • Búsqueda

  • Iteración

  • Manipular un especifico rango de elementos

Implementaciones:

1. ArrayList

• No sincronizado

• Rápida iteración sobre sus elementos

• Bueno para el acceso posicional

2. Vector

• Sincronizado

• Implementa un acceso aleatorio a los elementos del vector

3. LinkedList

• Es parecido al ArrayList, solo que este liga sus elementos 2 veces

• Es bueno para implementar colas y pilas

• Es mas rápido para quitar y agregar elementos.

Hay 3 implementaciones de List, ArrayList, Vector y LinkedList. La mayoría de las veces usaremos ArrayList, el cual ofrece acceso posicional de tiempo constante, lo cual es bueno. Esto lo hace porque no tiene que localizar el nodo de cada elemento en la lista. Además de que puede tomar ventaja de System.arraycopy cuando necesita mover múltiples elementos al mismo tiempo. Si frecuentemente agregas elementos al inicio de la lista o haces iteraciones a través de la lista para borrar o agregar elementos, deberías considerar usar LinkedList. Esas operaciones requieren un tiempo constante en una LinkedList y tiempo lineal en un ArrayList. De igual manera, el acceso posicional requiere tiempo lineal en una LinkedList y tiempo constante en un ArrayList.

Nota. Siempre es conveniente manejar algoritmos cuya ejecución nos ofrezca un tiempo constante en vez de un tiempo lineal. Esto cuando nos sea posible.

Interfaz Set

Un Set se ocupa de que los elementos en la colección sean únicos (no permite duplicados). El método equals es el que determina si dos objetos son idénticos (en tal caso solo se podrá agregar uno a la colección). Esta interfaz tiene 3 implementaciones.

1. HashSet

• Unsorted y unordered
• Usal el hash code para insertar y recuperar elementos

2. LinkedHashSet

• Es una version ordenada de HashSet
• Es buena cuando importa el orden de iteración

3. TreeSet

•  Es sorted
• almacena elementos en un arbol de tipo red-black

La implementacion de HashSet es mucho mas rápida que la de TreeSet (tiempo constante vs tiempo logarítmico para la mayoría de las operaciones), pero no nos da un orden en los elementos. Si necesitas usar las operaciones de la interfaz SortedSet, o es requerida una iteración con los valores ordenados, usa la implementación de TreeSet. De otro modo usa HashSet.

El LinkedHashSet esta en medio del HashSet y del TreeSet. Esta implementado como un hashtable con una lista ligada y nos provee de una iteración en el orden de inserción de los elementos.

Ojo: Cuando uses HashSet o LinkedHashSet, los objetos que agregues a ellos deben sobreescribir el método hashCode(). Si ellos no lo sobreescriben, el metodo hashCode() por default de Object permitirá que se agreguen a una colección que no permite elementos duplicados elementos que tu podrías considerar que son iguales.

Interfaz Map

A los Map le interesan y se fijan en los identificadores únicos. Lo que haces cuando utilizas alguna implementación de Map es mapear una clave única (Id) a un valor especifico, por supuesto de objetos. Es una estructura de datos que utiliza el par clave/valor. Las implementaciones de esta interfaz te permiten realizar búsquedas basadas en un Id o buscar en base a los valores. Los Map confían en el método equals() para determinar si dos objetos son diferentes uno de otro, es decir, si generan el mismo hash code.

Esta interfaz tiene 4 implementaciones:

1.HashMap

• Es unsorted y unordered
• Permite agregar a una colección claves y valores nulos

2. Hashtable

• Es sincronizado
• No permite nulos en las claves ni en los valores

3. LinkedHashMap

• Mantiene el orden de inserción (ordered)
• Itera mas rapido que el HashMap
• Es más lento para agregar y quitar elementos que el HashMap

4. TreeMap

• Es sorted

Si necesitas las operaciones de SortedMap o una iteración ordenada de la colección según las claves , usa TreeMap. Si tu quieres velocidad y no te importa el orden de iteración, usa HashMap. Si tu quieres el performance de HashMap y una iteración en el orden de inserción usa LinkedHashMap. En lo que respecta a esto, la situación de Map es análoga a Set.

Interfaz Queue

Esta interfaz esta diseñada para contener una lista de objetos que serán procesados en alguna forma especifica (una estructura de datos tipo cola). Aunque otros ordenes son posibles, las colas son usualmente pensadas como un FIFO ( primeras entradas, primeras salidas). Las colas soportan todos los métodos estándar de Collection, y agregan métodos para obtener y ver elementos de una cola. Esta interfaz tiene una implementación, que es la PriorityQueue.

PriorityQueue

Clase agregada en Java 5. El propósito de la clase PriorityQueue es crear una cola “priority-in, priority-out”. En este tipo de colas los elementos son ordenados de acuerdo a su orden natural (en el cual los elementos que sean ordenados primero, serán accesados primero) o según lo especificado con un comparador (Comparator).

Tip. Puedes fácilmente obtener algunas respuestas correctas en el examen si reconoces que, por ejemplo un Map no puede ser una clase que escojas cuando necesitas una colección de pares de clave/valor, ya que Map es una interfaz y no una implementación concreta de una clase. En el examen, si te preguntan sobre una interfaz, piensa en una interfaz y no en una clase que implemente esa interfaz. Y al revés también, si te preguntan por una clase, no respondas escogiendo una interfaz. Pasa mas bien por un tema de concentración y de leer bien la pregunta.

La siguiente tabla resume las clases orientadas a colecciones que necesitas entender para el examen.



Conclusión

El Framework Collection de Java nos proporciona un conjunto de interfaces y clases para poder hacer agrupaciones de objetos. Hay en este conjunto de clases e interfaces, lo necesario para cumplir con prácticamente todos los requerimientos del día a día de un desarrollador. Un punto clave para las colecciones es identificar que clase o que interfacse podemos utilizar dado un requerimiento. Esto lo podemos hacer conociendo la funcionalidad y opciones que ofrecen cada una de las implementaciones de este framework.

Guía de secuencia de estudio recomendada sobre este tema

Al tener este tema gran cantidad de información, se recomienda estudiar de manera secuencial siguiendo los siguientes pasos.

1) Conocer qué es la interfaz Colection y qué es la clase Collections.

2) Conocer qué métodos proporciona la clase Colection (obtener un elemento, insertar o eliminar un elemento, recorrelo mediante un iterador).

3) Conocer qué clases extienden de este objeto Colecction: Set, List, Map, Queue, y cuáles son las primeras características de los mismos (Set -> elementos ordenados, List -> elementos secuenciales, Map -> clave par / valor, Queue -> objetos de cola de prioridad, primero que entra, primero que sale).

4) Conocer que, de manera transversal, aparece el concepto de tree  (permite ordenación con estructura de árbol), linked (permite potenciar la vinculación entre elementos) y hash (permite la inserción de elementos siguiendo una estructura de Hash). También aparece el concepto de sincronización. Es bueno conocer que, desde mi punto de vista, las colecciones nacieron con las listas, por lo cual este concepto quedo en tres clases: ArrayList, Vector, y LinkedList, y después las interfaces de árbol, hash y linked se aplicaron con más vehemencia sobre los elementos Set y Map. En última instancia tenemos las colas con la implementación de PriorityQueue, que es una parte poco evolucionada además de ciertamente engañosa, en el sentido de que no es una relación FIFO como tal, si no que en este tipo de colas, existe un algoritmo de ordenación donde se da prioridad a los elementos, no existiendo una inserción meramente secuencial en la relación First Input First Output.

5) Conocer las clases que implementan las interfaces anteriores, y conocer las diferencias sutiles existentes entre ellas:

• Set + Hash = HashSet, Set + Linked = LinkedSet, Set + Tree = Tree Set.
• List + Linked = LinkedList, List + Array = ArrayList, ArrayList con métodos sincronizados = Vector.
• Tree + Map = TreeMap, Hash + Map = HashMap, Linked + HashMap = LinkedHashMap.
• Queue -> Priority Queu  

6) No asustarse sobre este tema y hacer bastantes ejercicios, y jugar mucho con ejemplos básicos ;)

Comments

[davidgzazg]

Muy buen aporte, todo muy claro.
Gracias!

[Jaime]

Este tema está realmente bien explicado. Clarísimo.

[goodwilltwo]

Te fusilaste lo del libro, lo cual agradezco con honores!! :D mi ingles es bastante pesimo y con tu explicacion ahora si ya va todo claro!!

Muy buen aporte

[diegoR]

Mil gracias por el aporte! Muy claro y de gran ayuda