delprogramador

Just another WordPress.com site

Archive for the month “February, 2012”

Collection’s

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:

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

a

  1. 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.
Advertisements

Welcome

Bienvenidos a la nueva pagina de orientacion a la programacion en terminos generales y detallados…

Post Navigation