Introduccrión al API Collections
miércoles, enero 16, 2002 at 1:00AM
Introducción al API Collections
Introducción.
Más o menos, todo el que ha hecho un programa en Java que tenía más de 3 clases ha usado alguna vez la clase java.util.Vector, java.util.Enumeration o similares. Son las famosas estructuras de datos, que se encargan de almacenar y agrupar nuestros objetos. La buena selección y el buen uso de las estructuras de datos es algo primordial para obtener un código claro y profesional.
Por razones que desconozco, la cantidad de clases e interfaces disponibles en Java 1 (hasta versión 1.2) era más bien excasa, y su diseño tampoco era el más lógico del mundo. Las clases Vector, Stack, HashTable, BitSet y el interface Enumeration se quedaban un poco cortas, y su uso en muchas ocasiones no era el más lógico del mundo (al menos a mi así me lo parecía), pero quién más y quién menos todos acabamos encontrando los trucos necesarios para manipularlas eficientemente.
Ahora, en Java 2, con nuevas clases (como HashSet o LinkedList) e interfaces (como Iterator o Comparator) el trabajo es, al menos en mi opinión, mucho mas claro y posiblemente eficiente.
Para leer este artículo sería recomendable que ya tuvieras algún tipo de contacto con Java, si es posible con esas clases que he mencionado como Vector y Enumeration, y que por supuesto conozcas las estructuras de datos típicas como cola, pila, árbol, etc.
La base de todo: interfaces Collection e Iterator.
Si a esta libreria se le llama Collections, no es de extrañar que la base de todo sea una interface llamada Collection, ¿no?. Esta interface tiene dos métodos fundamentales para el funcionamiento de todas las colecciones de datos:
boolean add(Object obj)
Iterator iterator()
No hace falta ser muy listo (simplemente son necesarios unos conocimientos mínimos de inglés o de otros lenguages de programación, ya que todos se parecen en cuanto a las palabras que usan) para saber que el método add añade un elemento a la colección, y que devuelve true o false en función de que la inserción haya tenido éxito o no.
El otro método, iterator, lo que hace es devolver un objeto que implementa el interface Iterator, que como pone en el título de esta sección, es el otro elemento básico de éste asunto que tenemos entre manos. Este es el elemento que se utiliza para recorrer todos los objetos de la colección a través de tres métodos fundamentales:
Object next()
boolean hasNext()
void remove()
De nuevo no me extenderé mucho explicando lo que hace cada método, asi que... next devuelve el siguiente elemento de la colección, hasNext te dice si hay mas elementos o no, y remove elimina el elemento actual, pero ojo, puesto que el Iterator es solo una lista de referenciass a los elementos de nuestra colección, lo elimina de nuestra colección, no solo del Iterator. Para los viejos, esto es algo asi como era Enumeration.
Un ejemplo típico de recorrido de una colección sería:
Iterator iter = miColeccion.iterator();
while (iter.hasNext())
{
MiObjeto obj = (MiObjeto) iter.next();
//manipular el objeto
//si es necesario lo borramos con:
//iter.remove();
}
Bonito diseño, ¿no?, con dos simples interfaces ya tenemos la base para un montón de estrucutras de datos distintas, asegurándonos poder diseñar métodos genericos para todo tipo de colecciones, ya que con estas dos interfaces tenemos los elementos básicos (y comunes a todas las colecciones de datos) de inserción, eliminación y recorrido.
Para terminar con esta sección, simplemente os daré la lista de métodos que contiene la interface Collection, para que al menos os suenen si nunca mirais la documentación del API, y os pido que le echeis un poco de imaginación para saber que hace cada uno.
int size()
boolean isEmpty()
boolean contains(Object obj)
boolean containsAll(Collection c)
boolean equals(Object other)
boolean addAll(Collection from)
boolean remove(Object obj)
boolean removeAll(Collection c)
void clear()
boolean retainAll(Collection c)
Object[] toArray()
y para facilitaros la vida cuando tengais que crear vuestra propia colección, podeís usar la clase abstracta AbstractCollection, que trae casi todos los métodos ya implementados.
Clases del API de Java 2
Ahora pasaremos a dar un repaso a las principales clases de colecciones que trae el API de Java 2. No será una referencia en profundidad, y supongo que no entrarán todas, pero suficiente para hacernos una idea de lo que hay y lo que podemos usar.
Listas enlazadas (LinkedList)
Supongo que más o menos todos sabeis lo que es una lista enlazada, asi que no me entretendré en recordarlo, y en el caso de que no lo sepais hay tutoriales en la red referentes a estructuras de datos, no debería ser difícil encontrar uno.
El API de Java es muy rico, más rico de lo que la gente cree, más rico de lo que la gente sabe, más rico aún de lo que yo creo y sé. He leido bastantes veces en las news... ¿como implemento una lista enlazada?. Siempre pensaba que es alguna especie de práctica típica que hay que hacer cuando empiezas a programar, pero un día me entere que no era así, que realmente era porque la necesitaban para un programa, así que la pregunta es... ¿por qué programar algo que ya esta hecho?.
La respuesta a lo de la lista enlazada es fácil, la clase LinkedList, que, como no, implementa el interface Collection, y posee ya un montón de métodos para realizar las operaciones típicas.
Pero para los despistdos, os tengo que recordar que una lista enlazada es una estrucutra posicional, es decir, que importa, y mucho, donde estas situado en cada momento. Al método add de la lista añade el elemento al final de la lista, para colocarlo en una posición determinada debes usar un Iterator. ¿Pero que pasa?, pues que no en todas las colecciones de datos importa el orden, como por ejemplo en los Set o conjuntos, asi que no quedaría bien para el diseño del API que se añadiera un método add a el interface Iterator.
Para solucionar este asunto se creó el interface ListIterator, que extiende a Iterator, y que sí presenta éste método add.
interface ListIterator extends Iterator
{
void add(Object);
Object previous()
boolean hasPrevious()
. . .
}
Aunque hay que darse cuenta de que éste método no devulve ningún valor (como si lo hacía add en el interface Collection), y que la inserción se realiza en la posición anterior a la que apunta el iterator. Además, podemos ver que proporciona los métodos necesarios para recorrer la lista en sentido inverso. Tambien existe un método set que sustituye el elemento actual, y algunos más, como por ejemplo para saber la posición actual en la que se encuentra dentro de la lista.
Para conseguir un iterator de este tipo, obviamente debemos llamar al método listIterator de la clase LinkdList.
Listas indexadas (ArrayList)
¿Pero que pasa si queremos acceder a una lista por su posición si tener que recorrerla secuencialmente?. Como hemos dicho por ahí (y si no lo he dicho lo digo ahora), las listas enlazadas tienen unos métodos get y set para poder acceder a los elementos, e incluso se podría acceder a una posición directamente, pero esta seria sólo nuestra impresión, ya que el método la recorreria secuencialmente. Para solucionar esto existe la clase ArrayList, que es el equivalente exacto a la famosa (y muy muy utilizada) Vector.
Vector es la excepción de las colecciones existentes antes de Java2, esta bien hecha y es realmente útil, por lo que se puede seguir utilizando, pero entonces ¿cuál es la direferencia entre ambas?. Bueno, la diferencia es que Vector es segura frente a threads. Entonces tú dirás, entonces Vector es mejor, bueno, pues no necesariamente, puede ocurrir que tu no utilices threads y que tu lista sea muy grande, por lo que estas comprobaciones extras repercutirían en el rendimiento, pero en principio no importa demasiado cual usar, aunque hay que tener en cuenta que la integración de ArrayList con el resto del API es mayor.
Conjuntos indexados (HashSet)
(nota: soy consciente de lo poco agraciada que suena la traducción conjuntos indexados, asi que si alguien connoce una mejor traducción para hash set que me la diga a al@javahispano.com).
De acuerdo, ya tenemos las listas, ya es suficiente. Pues no, que pasa si en vez de querer acceder según el orden de los elementos quieres acceder a ellos por su valor, pues que para encontrar un elemento tendras que recorrerte la lista. Esto lo arreglan los conjuntos indexados, que tienen un índice de valores clave que apuntan a los elementos
Ahora lo siento mucho, pero aunque no pensaba hacerlo, ahora tengo que explicar un poco el funcionamiento de los índices y demás para que algunas cosas que se comentan luego queden mas claras, asi que si ya sabes como funciona una estrucutra con hashing, sabes lo que es el índice de carga y demás asuntos te puedes saltar el siguiente parrafo.
Una estrucutra con hash no es mas que un array de listas enlazadas ordenadas, asi que no te asustes, no hay magina ni nada por el estilo. El secreto del hashing esta en los índices o claves del elemento, cuando metes un elemento en una de estas estructuras, se aplica un algoritmo interno a esta clave, de forma que se obtiene un indice numérico, de forma que el elemento se mete en la lista que tenga ese índice en el array de listas. Una forma de controlar el rendimiento de nuestra estructura, es indicar el número de listas (llamadas buckets, por razones que vienen de otros origenes) que contendrá inicialmente (initial bucket count). Cuantas más listas tengamos, es menos probable que estas se hagan grandes y cueste mas recorrerlas.
En Java2, el constructor por defecto de HashSet utiliza 101 buckets y un índice de carga de 0,75, aunque puedes especificiar los valores que necesites en el constructor.
HashSet(int initialCapacity)
HashSet(int initialCapacity, float loadFactor)
Despues de crear tu conjunto, puedes añadir valores con el método add, recuperarlos (si existen) con contents, y recorrer todos los elementos con un Iterator, aunque hay que tener en cuenta que este iterator recorre secuencialmente los buckets, por lo que el orden no seguire mas lógica que la de la clave del elemento.
Ahora, si has leido todo lo referente a esos conjuntos indexados deberias preguntarte... vale, ¿pero de donde sale ese índice o clave?. Pues sale del método hashCode que contiene la clase Object, padre de todos los objetos de Java, por lo que todos los objetos la tienen. El problema esta en que el algoritomo de hashing por defecto funciona a partir de las direcciones de memoria de los objetos, por lo que dos objetos con los mismo valores, al ser distintos objetos, podrían tener distintos índices aún cuando representen los mismo. Puedes hacer un algoritmo más adecuado sobreescribiendo este método, que tiene que devolver un entero, positivo o negativo. Pero si hace esto, asegurate de redefinir también el método equals, tambien viene de la clase Object, ya que la estrucutra lo usa para determinar el objeto a recuperar con el método contains, que por defecto, también se basa en las direcciones de memoria.
Arboles ()
La clase TreeSet es muy similar a la anterior, HashSet, con la diferencia de que esta vez los elementos si están ordenados. Esta estructura es el típico árbol binario que todos conocemos, por lo que no me dentendré a explicar su funcionamiento. Solo deciros que el rendimiento es algo inferior al de los conjuntos indexados, aunque en este caso los elementos están ordenados, y por supuesto el rendimiento en algunos casos es mucho mejor que el de un array o lista ordenada.
Pero... ¿como sabe como ordenar los elementos?. Bien, como es un poco largo, lo puedes ver en la siguiente sección.
Comparación de elementos: Comparable y Comparator
El interface Comparable es lo que usa el API Collections de Java para ordenar los elementos en las colecciones, como por ejemplo en los árboles TreeSet.
Este interface define un único método:
int compareTo(Object other)
que devolverá un número negativo, positivo o 0 en funcion de que el objeto que reciba hace la llamada sea menor, mayor o igual que el que se pasa como argumento.
a.compareTo (b) <0 a < b
a.compareTo (b) >0 a > b
a.compareTo (b) =0 a = b
Lo que haga el método para decidir si un elemento es mayor que otro es cosa tuya, eso es lo que tienes que implementar tú, por ejemplo:
public class Empleado implements Comparable{
. . .
private int nombre;
private int apellido;
private int edad;
. . .
public int getEdad (){
return this.edad;
}
. . .
public int compareTo (Object o){
Empleado temp = (Empleado) o;
return (this.edad - temp.getEdad());
}
. . .
}
Simple, ¿no?.
Lo malo de el interface Comparable es que sólo puede establecer un orden, es decir, ¿qué pasaría si ahora quisieramos ordenar nuestros empleados por su apellido?. Esto lo resuelve otro interface: Comparator. Este interface, que también se puede forzar a que lo usen las colecciones ordenadas de Java (normalmente pasándoselo a su constructor), tiene también un único método:
int compare(Object a, Object b)
El funcionamiento de este método es el mismo que en el de CompareTo de Comparable, asi que no hace falta decir más. En todo caso tengo en mente escribir un artículo práctico de su uso, con algunos trucos, para que os quede claro.
Como puedes ver es muy sencillo ordenar los elementos (¡que tiempos aquellos en los que había que pegarse con los punteros de Pascal! ;-) ), pero no cometas el error de ordenarlos si no lo necesitas, porque aunque sea sencillo y rápido, siempre es un tiempo que se pierde.
|
Reader Comments