Héctor Luaces

Guía de colecciones en Java

Lo que me motivó a escribir esta guía de colecciones en java es el inmenso tamaño del framework de colecciones que puede echar para a atrás a cualquier programador que se ponga a investigar las APIs sin ordenar un poco las ideas. Hay tantas interfaces e implementaciones que es fácil perderse y no saber que usar en cada momento.

Esta pequeña guía de colecciones en Java pretende explicar, de manera sencilla, que las colecciones en Java y que implementación sería mejor que usases para cada caso.

Este va a ser un post extenso, así que voy a ser tan amable de proporcionaros una pequeña tabla de contenidos.

  1. Tipos de colecciones en java
    1. Listas
    2. Sets
    3. Maps
    4. Colas
  2. Listas
    1. ArrayList
    2. LinkedList
    3. Vector
    4. CopyOnWriteArrayList
  3. Sets
    1. HashSet
    2. LinkedHashSet
    3. TreeSet
    4. EnumSet
    5. CopyOnWriteArraySet
    6. ConcurrentSkipListSet
  4. Maps
    1. HashMap
    2. LinkedHashMap
    3. TreeMap
    4. EnumMap
    5. WeakHashMap
    6. HashTable
    7. ConcurrentHashMap
  5. Colas
    1. ArrayDeque
    2. LinkedBlockingDeque
    3. LinkedList
    4. PriorityQueue
    5. PriorityBlockingQueue
  6. Diagramas de clases
    1. Diagrama de clases: Listas
    2. Diagrama de clases: Sets
    3. Diagrama de clases: Maps
    4. Diagrama de clases: Colas
  7. Notas finales

Tipos de colecciones en Java

Los tipos de colecciones vienen representados por interfaces. Una serie de interfaces clasifica las colecciones de Java en los siguientes tipos:

  • Listas: Una lista ordenada, o secuencia. Normalmente permiten duplicados y tienen acceso aleatorio (es decir, puedes obtener elementos alojados en cualquier índice como si de un array se tratase).
  • Sets: Colecciones que no admiten dos elementos iguales. Es decir, colecciones que no admiten que un nuevo elemento B pueda añadirse a una colección que tenga un elemento A cuando A.equals(B).
  • Maps: Colecciones que asocian un valor a una clave. Parecido a la estructura de “array asociativo” que se encuentra en otros lenguajes. Un Map no puede tener dos claves iguales.
  • Colas: Colecciones que permiten crear colas LIFO o FIFO. No permiten acceso aleatorio, solo pueden tomarse objetos de su principio, final o ambos, dependiendo de la implementación.

Listas

La colección más básica de Java. También, es la más usada por los programadores que no han investigado el framework de colecciones a fondo por hacernos pensar que se trata de una especie de array hipervitaminado ya que hace su trabajo y es fácil de entender.

Sin embargo, por grande que sea la tentación de usar una lista (como un ArrayList) para todo, ¡has de resistir!

Sabiendo los requisitos de tu aplicación, seguramente encontrarás otra colección que haga el trabajo de una lista mejor. Procura asegurarte de que cuando vas a usar una lista es porque realmente te hace falta, no porque no conoces el resto. La diferencia de rendimiento puede ser enorme. Y cuando digo enorme, me refiero a superior a un 600% en según que operaciones.

¿Qué beneficios tienen las listas?

  • Acceso aleatorio.
  • Están ordenadas (Podemos usar Colections.sort() para ordenar los elementos siguiendo el criterio que queramos).
  • Podemos añadir / eliminar elementos sin ninguna restricción.
  • Tienen un iterador especial ListIterator que permite modificar la lista en cualquier dirección.
  • Siguen la notación de los arrays, por lo que son fáciles de comprender.

¿Qué problemas tienen las listas?

  • Bajo rendimiento en operaciones especialziadas respecto a otras colecciones.

A continuación voy a enumerar todas las listas de Java con sus características, además, daré una pequeña explicación de cuando deberíais usar esa lista.

Tipos de Lista

  • ArrayList: Muy rápida accediendo a elementos, relativamente rápida agregando elementos si su capacidad inicial y de crecimiento están bien configuradas. Es la lista que deberías usar casi siempre.
  • LinkedList: Una lista que también es una cola (hablaré de esto más tarde). Más rápida que ArrayList añadiendo elementos en su principio y eliminando elementos en general. Utilízala en lugar de ArrayList si realizas más operaciones de inserción (en posición 0) o de eliminación que de lectura. La diferencia de rendimiento es enorme.
  • Vector: Terreno peligroso. Vector es una colección deprecated (obsoleta)así que usadla únicamente si necesitáis un ArrayList concurrente. El rendimiento de Vector es superior al de Collections.syncronizedList(new ArrayList()).
  • CopyOnWriteArrayList: Colección concurrente que es muy poco eficiente en operaciones de escritura, pero muy rápida en operaciones de lectura. Usala sobre Vector (o synced ArrayList) cuando el número de lecturas concurrentes sea mucho mayor al número de escrituras.

Sets

Los sets, o conjuntos, son colecciones que por norma general no admiten elementos iguales en su interior. Como mencionaba antes, dos elementos A y B son iguales si A.equals(B).

Podemos añadir y eliminar elementos de un set, así como saber si determinado elemento está en un set, pero no tenemos acceso aleatorio, por lo que hay que tener muy claro cuando queremos usarlos.

Una colección normal, en apariencia, nos da todo lo anterior -excepto el hecho de eliminar duplicados-, así que, ¿por qué usar un Set y no una Lista?, el motivo es simple: eficiencia.

Supongamos este código:

List b = new ArrayList();

if (!b.contains(1))
    b.add(1);

La funcionalidad es la misma que la de set.add, pero el rendimiento es muchísimo peor, hasta el punto de que podemos tener problemas muy serios cuando añadamos muchos elementos y no queremos eso, ¿verdad?.

¿Qué beneficios tienen los sets?

  • No permiten elementos duplicados.
  • Implementación muy eficiente de .add para asegurarnos de que no hay duplicados.

¿Qué desventajas tienen?

  • No tienen acceso aleatorio.
  • Solo algunos tipos de set pueden ordenarse y lo hacen de forma poco eficiente.

¿Cuando deberíamos usar un set sobre una lista?, y ¿qué tipo de set?, veámoslo…

Tipos de Set

  • HashSet: La implementación más equilibrada de la interfaz Set. Es rápida y no permite duplicados, pero no tiene ningún tipo de ordenación. Utilízala si necesitas un control de duplicados pero no ningún tipo de ordenación o acceso aleatorio.
  • LinkedHashSet: Un HashSet que incluye ordenación de elementos por orden de entrada, una velocidad de iteración mucho mayor y un rendimiento mucho peor a la hora de añadir elementos. Utilizala si necesitas un Set ordenado por orden de inserción o si vas a usar un Set que vaya a realizar solamente operaciones de iteración.
  • TreeSet: Un set que incluye una implementación de un árbol rojo-negro. Este Set puede ser ordenado, pero su rendimiento es mucho peor en cualquier operación (menos iteración) respecto aun HashSet. Utilizalo solo si necesitas un Set con un criterio de ordenación específico y ten cuidado con las inserciones.
  • EnumSet: La mejor implementación de Set para tipos enumerados (Enum). Utilizala si quieres crear un Set de Enums.
  • CopyOnWriteArraySet: Set concurrente que tiene un gran rendimiento de lectura, pero pésimo de escritura, eliminado y contains. Úsalo solo en Sets concurrentes que apenas tengan estas operaciones.
  • ConcurrentSkipListSet: Set concurrente y ordenable. Utilizalo solo cuando requieras un Set ordenable (como TreeSet) en entornos de concurrencia. En Sets de tamaños muy grandes su rendimiento empeora notablemente.

Maps

Los maps son colecciones que asocian un valor con una clave. Tanto la clave como el valor pueden ser cualquier tipo de datos de Java: Objetos, primitivos, otras colecciones, etc.

Las implementaciones son muy parecidas a los Sets debido a que, internamente, utilizan un Set (la implementación varía según el tipo de Map) para garantizar que no hay elementos duplicados en las claves.

¿Que ventajas tienen los sets?

  • Asociación clave -> valor.
  • Gracias a que utilizan internamente un Set, garantizan que no habrá dos claves iguales.
  • Es fácil reconocer cuando necesitamos usar un Map.

¿Qué desventajas tienen los sets?

  • Rendimiento no muy elevado comparado con otras colecciones.

Tipos de Map

  • HashMap: La implementación más genérica de Map. Un array clave->valor que no garantiza el orden de las claves (de la misma forma que un HashSet). Si necesitas un Map no-concurrente que no requiera ordenación de claves, este es el tuyo. Si os fijais en el código de HashSet, veréis que curiosamente utiliza un HashMap internamente.
  • LinkedHashMap: Implementación de map que garantiza orden de claves por su tiempo de inserción; es decir, las claves que primero se creen serán las primeras. También puede configurarse para que la orden de claves sea por tiempo de acceso (las claves que sean accedidas precederán a las que no son usadas). Itera más rápido que un HashMap, pero inserta y elimina mucho peor. Utilizalo cuando necesites un HashMap ordenado por orden de inserción de clave.
  • TreeMap: Un Map que permite que sus claves puedan ser ordenadas, de la misma forma que TreeSet. Usalo en lugar de un HashMap solo si necesitas esta ordenación, ya que su rendimiento es mucho peor que el de HashMap en casi todas las operaciones (excepto iteración).
  • EnumMap: Un Map de alto rendimiento cuyas claves son Enumeraciones (Enum). Muy similar a EnumSet. Usadlo si vais a usar Enums como claves.
  • WeakHashMap: Un Map que solo guarda referencias blandas de sus claves y valores. Las referencias blandas hacen que cualquier clave o valor sea eligible por el recolector de basura si no hay ninguna otra referencia al mismo desde fuera del WeakHashMap. Usa este Map si quieres usar esta característica, ya que el resto de operaciones tienen un rendimiento pésimo. Comúnmente usado para crear registros que vayan borrando propiedades a medida que el sistema no las vaya necesitando y vaya borrando sus referencias.
  • HashTable: Map deprecated y concurrente. Básicamente, es un HashMap concurrente que no debes usar nunca. En su lugar, utiliza ConcurrentHashMap.
  • ConcurrentHashMap: Un Map concurrente que no permite valores nulos. Sustitución básica de HashTable. Usala si necesitas un HashMap concurrente.

Colas

Las colas son estructuras que ofrecen un gran rendimiento al obtener elementos de su principio o de su final, representando colas LIFO / FIFO, aunque también veremos colas ordenadas en función de otros criterios.

Deberás usar una cola cuando vayas a recuperar siempre el primer o último elemento de una serie. Se usan para implementar las mencionadas colas LIFO / FIFO, así como colas de prioridades (como puede ser un sistema de tareas o de procesos).

Cabe destacar que hay dos tipos de colas, QueuesDeques. Las primeras solo proporcionan métodos para acceder al último elemento de la cola, mientras que las Deques permiten acceder a cualquiera de los dos extremos.

¿Qué ventajas tienen las colas?

  • Ofrecen un gran rendimiento al recuperar el primer o último objeto de la cola.
  • Permiten crear estructuras LIFO / FIFO o colas de prioridades con muy buen rendimiento.

¿Qué desventajas tienen las colas?

  • La iteración por las colas suele ser muy lenta.
  • El acceso aleatorio, de la misma manera, es muy lento.

Tipos de colas

  • ArrayDeque: Una implementación de Deque de rendimiento excepcional. Implementa tanto cola LIFO como FIFO al ser una Deque y es la Cola que deberías usar si quieres implementar una de estas dos estructuras.
  • LinkedBlockingDeque: Una Deque concurrente que has de usar cuando quieras usar un ArrayDeque en entornos multihilo.
  • LinkedList: LinkedList, anteriormente mencionada en la sección de listas, también es una Deque, sin embargo, su rendimiento es muy inferior al de ArrayDeque. No deberías usar LinkedList cuando quieras usar una cola.
  • PriorityQueue: Una cola que se ordena mediante un Comparator, permitiendo crear una Cola donde el primer elemento no dependerá de su tiempo de inserción, sino de cualquier otro factor (tamaño, prioridad, etc). Deberemos usarlo cuando necesitemos este comparator, ya que ArrayDeque no lo permite.
  • PriorityBlockingQueue: La versión concurrente de PriorityQueue.

Diagramas de clases

Para entender mejor el framework de colecciones, nada como un diagrama de clases de todas los tipos de colección. He aquí dicho diagrama, por cortesía de karambelkar.info:

Diagrama de clases – List

Diagrama de clases – Set

Diagrama de clases – Maps

Diagrama de clases – Colas

Notas finales

A la hora de usar colecciones en Java, lo más importante es elegir el tipo de colección. Cuando trabajemos con colecciones, siempre declararemos las instancias con el nombre de su interfaz, aprovechando el enlace dinamico.

De esta forma, aunque la implementación cambie en el futuro, podemos tener claro que la aplicación no va a dar fallos (ya que estamos usando las interfaces y estas tienen los métodos que usan sus implementaciones).

A la hora de escoger la implementación de cada tipo de colección, debéis fijaros en dos cosas:

  1. Si estamos trabajando en un entorno concurrente o no.
  2. En el rendimiento de las operaciones que vamos a necesitar en las distintas implementaciones válidas para nuestro entornos (concurrentes o no).

Sabiendo eso ya podréis empezar a explotar a fondo el Framework de colecciones en Java y no limitaros a usar las colecciones Vanilla, mal de muchos programadores que empiezan en este lenguaje.

Confío en que la lectura haya sido interesante y fructífera, para mi lo ha sido, por lo menos.

14 Comentarios

  1. Muchas gracias,

  2. Gracias!!!! despues de tanto buscar, lo estoy comenzando a leer, y veo que está muy bien explicado, y me está poniendo las ideas mucho más ordenadas. Graciasssssssssss!!!!!!!!!

  3. Buenisimo Hector!! Gran aporte para hacerte una idea de las distintas colecciones que tenemos entre manos, y me ha encantado la explicación del enlace dinámico.

  4. Un Hoy bien vivido hace que cada Ayer sea un sueño de felicidad y cada Mañana una visión de esperanza. Te mereces toda una vida de mañanas preciosas. por el enorme aporte que has hecho para la sociedad estudiantil o investigadora ”. Gracias Me ayudo Excelentemente en mi proyecto!!!!!!!!!!!!!!!!

  5. Buen aporte, te agradezco por el aporte.

  6. Severo, me sirvió para entender y saber qué estudiar de las colecciones.

  7. Directo a mis favoritos, genial post 😉

  8. Vicente Martí

    Los enlaces de los diagramas de clases de MAP son los dos de pdf, no está el de html. De todas formas, muchas gracias por el trabajo, me estoy haciendo mi propio manual/resumen de colecciones y me ha venido de maravilla.

  9. De gran utilidad!! Muchas gracias

Deja un comentario