Colecciones en Java

Para trabajar con colecciones en Java podemos hacer uso del framework Collections. Las clases e interfaces que componen este framework se encuentran en los paquetes java.util y java.util.concurrent. Todas hacen uso del polimorfismo paramétrico que proporciona generics; concepto que tratamos ampliamente en la entrada Generics en Java.

La raíz de la jerarquía de colecciones es la interfaz Collection<E>. De entre las interfaces que extienden Collection<E> las más interesantes son List<E>, Set<E> y Queue<E> que definen, respectivamente, listas, conjuntos y colas.

La lista es una de las colecciones más básicas, se trata de una estructura de datos secuencial, en la que cada elemento tiene una posición o índice, y que permite elementos duplicados. Set<E> es la interfaz utilizada para modelar los conjuntos matemáticos; como en estos, los elementos no tienen un orden, y no se permiten elementos duplicados. Una cola o Queue<E>, por último, es una estructura de datos de tipo FIFO (First in first out) lo que significa que el primer elemento en introducirse en la cola será el elemento que se devolverá al extraer por primera vez de la cola, y así sucesivamente (en realidad existen implementaciones de Queue<E> que no son FIFO, pero eso queda fuera del enfoque de esta entrada).

Otra estructura de datos que forma parte del framework, aunque no deriva de Collection<E>, dado que no se trata de una colección per se sino de un mapeo, es la que define la interfaz Map<K,V>, el conocido diccionario o matriz asociativa, en el que cada valor tiene asociado una clave que usaremos para recuperar el elemento, en lugar de un índice como el caso de las listas. Por ejemplo podríamos tener un mapeo en el que las claves fueran los días de la semana y los valores, el número de líneas de código que escribimos.

Para cada una de las interfaces que definen los tipos de colección disponibles tenemos una clase abstracta que contiene la funcionalidad común a varias implementaciones de la interfaz. Estas son AbstractList<E>, AbstractSet<E>, AbstractQueue<E> y AbstractMap<K,V>.

En esta entrada trataremos las listas y los mapeos, por ser las estructuras de datos más utilizadas.

List

Hay varias clases que implementan la interfaz List<E>. Las más utilizadas habitualmente son ArrayList<E> y la vieja conocida Vector<E>, que forma parte del framework Collections desde Java 1.2. Ambas extienden de AbstractList<E> y tienen una interfaz muy parecida.

Como en el caso de StringBuffer y StringBuilder la principal diferencia entre ambas clases es que Vector<E> es sincronizada y ArrayList<E> no sincronizada. Debido a esto no tendremos que preocuparnos de problemas de sincronización a la hora utilizar varios hilos con Vector<E> (hasta cierto punto). Pero a cambio, y por la misma razón, el rendimiento de Vector<E> es mucho peor que el de ArrayList<E>. Ergo, si no necesitamos sincronización o no estamos trabajando con más de un hilo de ejecución, lo adecuado es utilizar ArrayList<E>.

En todo caso, si trabajamos con varios hilos, también existe la posibilidad de sincronizar ArrayList<E> de forma externa o utilizar el método Collections.synchronizedList(List<T> list) para crear un wrapper que añade sincronización a ArrayList<E>. Vector<E>, no obstante, es ligeramente más rápido que un ArrayList<E> sincronizado con synchronizedList.

Tanto ArrayList<E> como Vector<E> utilizan un objeto Array<E> para almacenar los elementos internamente. Las colecciones de tipo Array<E>, sin embargo, tienen un tamaño fijo que se determina de antemano al llamar al constructor. Esto implica que cuando sobrepasamos dicho tamaño hay que crear un nuevo Array<E> y copiar el antiguo, lo que puede ser muy costoso computacionalmente. Por otro lado, si la capacidad máxima inicial del array fuera demasiado grande, estaríamos desperdiciando espacio.

Por defecto ArrayList<E> y Vector<E> utilizan arrays con capacidad para 10 elementos. Cuando el número de elementos sobrepasa la capacidad disponible Vector<E> dobla el tamaño del array interno, mientras que ArrayList<E> utiliza la fórmula (capacidad * 3) / 2 + 1.

Para indicar valores que se ajusten lo máximo posible al uso que vamos a hacer de nuestra lista tanto Vector<E> como ArrayList<E> cuentan, además de con un constructor vacío y un constructor al que pasar una colección con los elementos con los que inicializar el vector o la lista, con un constructor al que pasar un entero con la capacidad inicial de la colección.

Vector<E> cuenta también con un constructor extra mediante el que indicar el incremento en capacidad a utilizar cuando el número de elementos rebase la capacidad del vector, lo cuál puede ser muy interesante.

En cualquier caso, independientemente del constructor que utilicemos, al crear cualquier colección es una buena práctica utilizar el tipo más genérico posible para referirnos al nuevo objeto. Por ejemplo, sería preferible utilizar:

List<String> lista = new ArrayList<String>();

a

ArrayList<String> lista = new ArrayList<String>();

ya que al utilizar la primera versión, si es necesario en un futuro, podremos migrar fácilmente a una implementación distinta de List<E> gracias al polimorfismo.

Otra implementación para listas muy utilizada es LinkedList<E>, diseñada para obtener un mejor rendimiento cuando se insertan o eliminan muchos elementos de la mitad de la colección. Este tipo de lista, como su nombre indica, utiliza una lista doblemente enlazada internamente, en lugar de un array. En una lista enlazada tendremos un nodo por cada elemento introducido y cada uno de estos nodos tendrá el valor asociado a esa posición y una referencia al siguiente nodo. De esta forma, al insertar o eliminar un elemento cualquiera, basta con actualizar la referencia al siguiente nodo, en lugar de mover cada elemento a una posición superior o inferior como ocurriría con una implementación basada en Array<E> como Vector<E> y ArrayList<E>.

Sin embargo en las listas enlazadas, a diferencia de en los arrays, que se implementan directamente en hardware, el acceso a los elementos se realiza de forma secuencial, siguiendo las referencias de cada uno de los nodos, por lo que el acceso a una posición aleatoria de la colección es mucho más lento. Esta clase de colección, por tanto, tan solo debería utilizarse en casos en los que vayamos a insertar o eliminar muchos elementos de la mitad de la colección, pero no vayamos a realizar muchos accesos aleatorios.

Como Vector<E> y ArrayList<E>, y de hecho como todos los tipos de colección concretos, LinkedList<E> cuenta con un constructor vacío y un constructor que recibe una colección con los valores iniciales para la lista. De esta forma es sencillo copiar valores de una colección a otra o convertir un tipo de colección en otra distinta.

La interfaz que nos proporciona es muy parecida a la de Vector<E> y ArrayList<E>. De hecho esta clase extiende de la clase AbstractSequentialList<E>, que a su vez es hija de AbstractList<E>, la clase padre de Vector<E> y ArrayList<E>.

Por último, otra clase interesante dentro de la jerarquía de List<E> es CopyOnWriteArrayList<E>, perteneciente al paquete java.util.concurrent, y que, a diferencia de ArrayList<E> y LinkedList<E> es thread-safe, como Vector<E>, y ofrece un muy buen rendimiento a la hora de leer de la colección. Su desventaja es que el array que utiliza por debajo es inmutable, lo que hace que tengamos que crear un nuevo array cada vez que la colección se modifica. Puede ser una buena alternativa si utilizamos varios hilos de ejecución y no vamos a modificar mucho la lista.

De entre los métodos comunes a las clases ArrayList<E>, Vector<E>, LinkedList<E> y CopyOnWriteArrayList<E> los más interesantes son los siguientes:

  • boolean add(E o): Añade un nuevo elemento al final de la colección.
  • boolean add(int index, E element): Añade un nuevo elemento en la posición especificada.
  • boolean addAll(Collection<? extends E> c): Añade todos los elementos de la colección especificada a esta colección.
  • void clear(): Elimina todos los elementos de la colección.
  • boolean contains(Object o): Comprueba si el elemento especificado es parte de la colección.
  • E get(int index): Recupera el elemento que se encuentra en la posición espeficicada.
  • int indexOf(Object o): Devuelve la primera posición en la que se encuentra el elemento especificado en la colección, o -1 si no se encuentra.
  • int lastIndexOf(Object o): Devuelve la última posición en la que se encuentra el elemento especificado en la colección, o -1 si no se encuentra.
  • E remove(int index): Elimina el elemento de la posición indicada.
  • boolean remove(Object o): Elimina la primera ocurrencia del elemento indicado. Si se encontró y se borró el elemento, devuelve true, en caso contrario, false.
  • E set(int index, E element): Reemplaza el elemento que se encuentra en la posición indicada por el elemento pasado como parámetro. Devuelve el elemento que se encontraba en dicha posición anteriormente.
  • int size(): Devuelve el número de elementos que se encuentran actualmente en la colección.

Map

La interfaz Map<K,V> y las clases que la implementan vienen a reemplazar la antigua clase Dictionary.

HashMap<K,V> es el tipo de mapeo más sencillo y probablemente el más usado. Es la clase a utilizar si queremos asociar pares de claves y valores sin orden, sin más. Internamente, como su nombre indica, utiliza un hash para almacenar la clave. No permite claves duplicadas, pero si utilizar null como clave.

Hashtable<K,V> es una vieja conocida del JDK 1.0, que, como Vector<E> pasó a formar parte del framework de colecciones en Java 1.2. Esta clase es muy similar a HashMap<K,V>, con la excepción de que es sincronizada y que no acepta utilizar el valor null como clave. Como en el caso de Vector<E> contra ArrayList<E>, nos interesará utilizar HashMap<K,V> siempre que no estemos utilizando varios hilos de ejecución. En el caso de que necesitemos sincronización, otra opción es utilizar el método Collections.synchronizedMap sobre un HashMap, que funciona de forma similar a Collections.synchronizedList.

LinkedHashMap<K,V> es una clase introducida con el J2SE 1.4 que extiende HashMap<K,V> y utiliza una lista doblemente enlazada para poder recorrer los elementos de la colección en el orden en el que se añadieron. Esta clase es ligeramente más rápida que HashMap<K,V> a la hora de acceder a los elementos, pero es algo más lenta al añadirlos.

Por último tenemos TreeMap<K,V>, en el que los pares clave-valor se almacenan en un árbol ordenado según los valores de las claves. Como es de esperar es la clase más lenta a la hora de añadir nuevos elementos, pero también a la hora de accederlos.

De entre los métodos comunes a las cuatro clases los más utilizados son:

  • void clear(): Elimina todos los elementos de la colección.
  • boolean containsKey(Object key): Comprueba si la clave especificada se encuentra en la colección.
  • boolean containsValue(Object value): Comprueba si el valor especificado se encuentra en la colección.
  • V get(Object key): Devuelve el valor asociado a la clave especificada o null si no se encontró.
  • boolean isEmpty(): Comprueba si la colección está vacía.
  • Set keySet(): Devuelve un conjunto con las claves contenidas en la colección.
  • V put(K key, V value): Añade un nuevo par clave-valor a la colección
  • V remove(Object key): Elimina el par clave-valor correspondiente a la clave pasada como parámetro.
  • int size(): Devuelve el número de pares clave-valor que contiene la colección.
  • Collection values(): Devuelve una colección con los valores que contiene la colección.

Collections

Collections es una clase perteneciente al paquete java.util que proporciona una serie de métodos estáticos para manejar colecciones que pueden ser de mucha utilidad. A esta clase pertenecen los métodos synchronizedList y synchronizedMap que ya comentamos anteriormente. Otros métodos interesantes son:

  • int binarySearch(List list, Object key): Busca un elemento en una lista ordenada utilizando un algoritmo de búsqueda binaria. El método devuelve un entero indicando la posición en la que se encuentra el elemento, o bien un número negativo si no se encontró. Este número negativo indica la posición la que se encontraría el elemento de haber estado en la colección.
  • int frequency(Collection c, Object o): Devuelve el número de veces que se repite el elemento especificado en la colección.
  • Object max(Collection coll): Devuelve el mayor elemento de la colección.
  • Object min(Collection coll): Devuelve el menor elemento de la colección.
  • boolean replaceAll(List list, Object oldVal, Object newVal): Reemplaza todas las ocurrencias en la lista de un cierto elemento por otro objeto.
  • void reverse(List list): Invierte la lista.
  • void shuffle(List list): Modifica la posición de distintos elementos de la lista de forma aleatoria.
  • void sort(List list): Ordena una lista utilizando un algoritmo merge sort.


35 comentarios en «Colecciones en Java»

  1. Estupendo el post, aunque sólo para los que nos interesan estas cosas 😉

    Por cierto, cuando hablas de Treemap y dices:
    «Como es de esperar es la clase más lenta a la hora de añadir nuevos elementos, pero también a la hora de accederlos.»

    Imagino que quieres decir «… pero también más rápida a la hora de accederlos.», porque si no ya me dirás para qué sirven los árboles 😉

    Como comentario, quería decir a todo el que lea esto, que no es complicado usar colecciones en JAVA, y que siempre se piense en la concurrencia, o al menos en la posibilidad de añadirla en el futuro, porque una vez que aprendes a usarla, hay muchísimos casos en los que interesa.

    Saludos y enhorabuena a Zootropo por seguir en la brecha después de ¡tanto! tiempo.

    Calabacín

  2. @Calabacín HashMap es O(1) para acceder, añadir y eliminar elementos mientras que TreeMap es O(log N).

    Eso si, TreeMap suele ser más eficiente en el consumo de memoria.

    1. Estoy de acuerdo.

      A poco volumen de datos, es mas eficiente un HashMap. Pero a grandes volumenes, se hace notable la eficiencia de un TreeMap, claro que haciendo un buen uso de la sobrecarga del equals, para el criterio de orden.

  3. @Zootropo Hombre, lo que yo quería decir es que por cómo lo has escrito me había parecido una errata. Supuse que un árbol tendría alguna ventaja, y supuse que sería la velocidad.

    Pensando en lo que se dice, y no en la gramática (cosa que sinceramente no hice antes jeje), es de lógica que una tabla hash sea siempre más rápida, ya que vas directo al elemento siempre. Sin embargo, sí que me parece que un árbol puede ser más rápido que una lista (como LinkedHashMap), siempre que éste esté ordenado claro (y he entendido que está ordenado por claves).

    Sin embargo me llama la atención que un árbol sea más eficiente en cuanto a consumo de memoria, ya que todos los nodos tendrán enlaces a sus hijos (mínimo 2), y posiblemente a sus padres, con lo que en el mejor de los casos, consumirán tanta memoria como una lista enlazada (o un LinkedHashMap) o más.

    Todo esto son dudas que me surgen justo antes de irme a dormir. Igual mañana lo veo todo distinto 🙂

    1. En una tabla hash siempre necesitarás espacio adicional que casi no usarás ..por lo tanto siempre desperdiciarás memoria !

    2. Hola Calabacin lei tu inquietud con respecto a la rapidez del acceso a datos en un HashMap o TreeMap y a mi parecer la busqueda binaria deberia ser mucho mas rapida ya que el orden en las hashmap no tiene un orden logico, y en las treeMap si, generalmente en un arbol los elementos tienen un orden, el elemento raiz, el elemento menor a la izquierda y elemento mayor a la derecha, si hablamos de un orden binario, lo que al tener un arbol con demasiadas ramas al buscar un elemento verifica la raiz y si el elemento a buscar es mayor que la raiz descartara todos los elementos de izquierda y buscara por la derecha y lo mismo hara por la derecha y sus ramificaciones, espero no haberme ido por las ramas y haber sido claro jajaja, saludos.

  4. Excelente, me estoy empapando (conociendo) mas del uso del Java Collection Framework, lo que he andado buscando, son ejemplos, como crear desde cero, una lista (simple, lista enlazada doblemente enlazada), una cola y una pila, hay algun post sobre esto?
    De nuevo, gracias por compartir tus conocimientos, que Dios te siga bendiciendo!!!

  5. Hola, muchas gracias por compartir este tremendo post. Me sirve mucho para rendir la recuperación del parcial de metodologías de la programación.
    Hasta Luego!

  6. Hola.veo qe manejais mucho de java.m gustaria saber como convierto un hashmap en un vector. Gracias porqe si me ayudais me abreis echo un gran favor!

  7. bueno es de esperarse otro comentario positivo. buen aporte! ahora si en estos 10min de leer tan buen post, entendi lo que no pude en 2 horas con el profe 🙂

  8. Hola, como puedo crear un arraylist pero con datos de diferentes tipos?, por ejemplo:

    Nombre: Alumno1
    Cal: 5.0

    Nombre: Alumno2
    Cal: 4.0

    y asi sucesivamente?

    Ojala puedan ayudarme.

  9. ola tengo una duda cual es laa capacidad maxima de un hashmap…..y si se llena….puedo suegir agrandando su tamaño…..y hasta que tamaño si se puede…ojala puedan ayudarme

  10. Hola, muchas gracias por la info, la verdad es que esta buena y es muy llevadera.
    Me queda una duda sobre las linkedList. vos decis «Otra implementación para listas muy utilizada es LinkedList, diseñada para obtener un mejor rendimiento cuando se insertan o eliminan muchos elementos de la mitad de la colección».
    Sin embargo no seria al reves? las linked son mejores cuando los elementos que se van a leer o borrar se encuentran en los extremos de la lista dado que como el acceso es secuencial se tiene que mover por toda la lista para llegar a la mitad.
    Además de los nodos que tiene que referenciar al próximo y al anterior, es decir marcar cual es su antecesor y su sucesor. en cambio si fuera el primer elemento el que se inserta, solo tiene que anotar cual es su sucesor.
    Es una duda nomas, que me gustaría saber.
    Muchísimas gracias y un abrazo.

    pd: me voy a leer tu articulo sobre generics que me interesa.

  11. Muy buen articulo, como ya han dicho con un ejemplo de lista, cola y pila genericos lo bordas, eso si partiendo de un vector o de un ArrayList.

    Muy buen post, en serio.

  12. Pingback: Collection « delprogramador

  13. Pingback: Desempeño de C++ vs. Java: todo reside en la calidad del compilador (y del programador también) – ::everac99

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.