Es común encontrarse con programas en Java y en general diferentes lenguajes de programación donde el uso de las estructuras de datos no es eficiente. Por ejemplo, un error típico es el uso de una lista cuando no se necesitan elementos ordenados. Todos estos “pequeños” errores terminan por afectar el desempeño y la calidad de las aplicaciones. Este post describe las estructuras de datos más utilizadas y sus diferentes implementaciones en Java.
Para tomar un ejemplo, validé las operaciones de agregar (add) y establecer (set) de dos implementaciones de Lista. ArrayList y LinkedList.
La tabla muestra los resultados en milisegundos.
| Estructura de Datos | Operación | Tiempo (ms) (Menor es mejor) |
| ArrayList | Add | 6 |
| ArrayList | Set | 2 |
| LinkedList | Add | 5 |
| LinkedList | Set | 54 |
Mientras el comportamiento al momento de agregar elementos es muy similar, la operación de establecer es bastante diferente, nueve(9) veces más rápido en el ArrayList. Si bien, ambas clases implementan la interfaz Lista. Las diferencias en la implementación varían sustancialmente el desempeño y el consumo de memoria.
JAVA.UTIL
El Framework de colecciones de Java es un de los paquetes mas utilizados y contiene diferentes estructuras de datos con diferentes prestaciones y características. Del Framework, introducido en Java 1.2, destacan cinco principales estructuras de datos. Cada una de estas interfaces son definiciones extensibles que tienen múltiples implementaciones.
Collection
Es la interfaz principal de todas las colecciones básicamente define un contenedor de elementos que puede realizar las tareas usuales (agregar, borrar, eliminar).
Set
Es una colección de elementos que no puede tener elementos duplicados. Un ejemplo de su uso es en las colecciones.
List
Es una colección ordenada de elementos. Puede tener elementos duplicados y acceder a los elementos por su posición (Index).
Queue (Cola)
Es una colección de múltiples elementos donde se es posible acceder a los elementos de uno de los extremos de la lista. Además de los métodos básicos de una colección permite la inserción, y extracción de los elementos extremos. Las colas usualmente se comportan como una FIFO (First in First out – primero en entrar, primero en salir) pero es posible encontrarlas por un operador o comparador especifico.
Deque
Es una colección de múltiples elementos donde es posible acceder a ambos extremos de la lista. Los Deque pueden encontrarse Como FIFO (First in – First Out) o LIFO (Last in – Last Out).
Map
Es un objeto que relaciona la llave de un objetivo con su respectivo valor. Un mapa no puede tener llaves duplicadas y cada llave debe tener un único elemento correspondiente.
Comparando las implementaciones.
Si bien cada una de las implementaciones y estructuras de datos tiene funcionalidad y prestaciones particulares. Me concentrare en las mas comunes List, Set y Map. La columna desempeño representa el tiempo en las operaciones mas comunes.
Set
| Descripción. | Desempeño. | |
| TreeSet | Es un set que permiten mantener un orden específico de los elementos. | O(log(n)) |
| HashSet | Basado en un HashMap es el set más eficiente pero no garantiza que se mantenga el orden de los elementos. | O(1) |
| LinkedHashSet | Es considera una implementación intermedia entre el TreeSet y HashSet pues es implementado usando un HashMap pero permite conservar el orden de los elementos al momento de inserción. | O(1) |
Para los Set realice una simple operación de inserción de elementos para comprobar su ordenamiento.
public void testSet(Set<SetElement> set, String description)
{
set.add(new SetElement(2));
set.add(new SetElement(3));
set.add(new SetElement(1));
System.out.println(description);
Iterator<SetElement> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next().value);
}
}
Resultado de la consola. El TreeSet almacena los elementos en orden natural , el linked HashSet en el orden de inserción, y HashSet de manera aleatoria.
List
| Descripción. | |
| ArrayList | Es el tipo de lista más común y provee tiempo constante para operaciones de acceso por posición. |
| LinkedList | Es una lista optimizada para realizar modificaciones donde es necesario iterar sobre la lista. Provee tiempo constante para este tipo de operaciones sin embargo el tiempo de consultas por posición es lineal. |
public static void removeElement(List<Long> list, String description)
{
Long start = System.currentTimeMillis();
for (int i = 0; i < 1000; i++)
{
list.remove(i);
}
Long end = System.currentTimeMillis();
System.out.println(description);
System.out.println(end - start);
}
| Número de operaciones vs Tiempo (Menor es mejor) |
1000 | 10000 |
| ArrayList | 68 ms | 609 ms |
| LinkedList | 4 ms | 174 ms |
La diferencia en el desempeño es sustancial y se debe a que la implementación de una ArrayList esta basada en un vector mientras la implementación de un LinkenList esta basada en nodos con apuntadores. La operación de borrado en una ArrayList requiere la creación y copiado de un vector para el ArrayList mientras que para la LinkedList es solo cuestión de cambiar apuntadores.
public LinkedList<T>
{
class Node<T> {
T data;
Node next;
Node prev;
}
private Node<T> first;
private Node<T> last;
private int size;
}
public ArrayList<T>
{
private Object[] array;
private int size;
}
Map
| Descripción. | Desempeño. | |
| TreeMap | Es un mapa de elementos que garantiza el ordenamiento de los elementos por su clave (Key). | (log(n)) |
| HashMap | Es el mapa más eficiente pero no garantiza que se mantenga el orden de los elementos. | O(1) |
| LinkedHashMap | Es considera una implementación intermedia entre el TreeMap y HashMap pues es implementado usando un HashMap pero permite conservar el orden de los elementos al momento de inserción. | O(1) |
La diferencia principal entre el HashMap y LinkedHashMap es que el cada entrada del HashMap consta de su Key y Valor mientras que en un LinkedHashMap además del Key y Valor tenemos apuntadores a la entra siguiente y la entrada anterior. Esta diferencia en la implementación mejora el desempeño trae un consumo de memoria extra y una latencia en las operaciones comunes (ver datos de prueba a continuación).
Long start = System.currentTimeMillis();
long before = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
Map<String, Integer> map = new LinkedHashMap<>();
TestHelper.initMap(map, ELEMENTS);
long after = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
System.out.println(after - before);
Long end = System.currentTimeMillis();
System.out.println("Memory : " + String.valueOf(after - before));
System.out.println("Time : " + String.valueOf(end - start)
HashMap
Memory : 12.625.320 bytes
Time : 43 ms
LinkedHashMap
Memory : 13.013.464 bytes
Time : 45 ms
Eso es todo. Si bien son conceptos básicos espero el Post les sea de interés. En conclusión no existen mejores o peores estructuras de datos sino la estructura de datos adecuada para solucionar un problema.
Desarrollo & diseño de Software 