Introducción a la estructura HashMap

HashMap es una estructura de datos disponible en Java que implementa la interfaz Map y se utiliza para almacenar parejas clave-valor {K, V}. La estructura HashMap se usa también para implementar la clase HashSet lo que la convierte en una de las estructuras de datos clave en Java.

El diseño de HashMap está pensado para permitir el almacenamiento, acceso y búsqueda de parejas clave-valor con la mayor eficiencia posible. Esta eficiencia se traduce en lograr la máxima velocidad en las siguientes operaciones:

• Búsqueda de parejas clave valor conocida la clave V get(K k)

• Inserción de nuevas parejas clave-valor V put(K v, V v) en la estructura.

La importancia de realizar dichas operaciones lo más eficientemente posible es consecuencia de la propia naturaleza de la estructura HashMap, que permite la inclusión de parejas {k, v} con valores v repetidos, pero no admite que dos entradas {k, v} tengan la misma clave k. Caso de que se solicite la inclusión en la estructura de una pareja {k, v} con una clave repetida, se insertará la nueva pareja en sustitución de la anterior.

Esto exige que, cada vez que se introduce una nueva entrada {k, v}, se tenga que consultar si la estructura ya cuenta con una entrada con la clave k. Dicho de otro modo: toda tarea de inserción de una nueva entrada en la estructura HashMap requiere de una tarea de lectura previa para verificar si existe ya una entrada con la misma clave que la entrada que se quiere añadir.

Estructura interna de HashMap

Internamente, un objeto HashMap está implementado mediante una estructura bien conocida en computación denominada hash table. Estas estructuras están compuestas por un array en cuyos elementos se almacenan referencias a cabeceras (heads) de listas enlazadas simples (Singly Linked List); a cada una de estas listas enlazadas simples se las denomina un bucket. Los elementos de los buckets son unos objetos denominados nodos, cada uno de los cuales guarda una pareja clave-valor {k, v} junto con el hash de la clave k y una referencia al siguiente nodo de la lista enlazada. La siguiente figura muestra la estructura de una hash table particularizada para HashMap:

A continuación se describen los componentes descritos en la figura.

• Array de nodos Node<K, V>: Como todo array en Java, el array de nodos es un objeto contenedor que almacena un número fijo de valores de un mismo tipo; en este caso, instancias de la clase Node<K, V> llamadas nodos. Node<K, V> es una clase anidada de la estructura HashMap no accesible desde el exterior. Cada uno de los nodos constituye la cabecera (head) de una lista enlazada simple (Singly Linked List) que, como se ha comentado, se denomina bucket. Como todo array, el array de nodos cuenta con un índice numérico a través del cual se puede acceder a sus elementos. También, como ocurre en todo array, sus posiciones de memoria se encuentran adyacences; ésto y el hecho de disponer de un índice, dota a los arrays de gran eficiencia en el acceso a los datos que almacena. El array de nodos de HashMap es subyacente, entendido esto como que no es accesible directamente y es el propio objeto HashMap el que lo gestiona internamente.

  El array y sus buckets no se rellenan secuencialmente desde la posición 0 en adelante, pero tampoco aleatoriamente: existe una correspondencia directa entre el hash de la clave k de la pareja clave valor <K, V> que se quiere insertar en el HashMap y el número de índice del array en que se encuentra el bucket al que se añadirá la pareja, como se verá.

  La longitud inicial del array es un parámetro de construcción del objeto HashMap y por defecto es 16. Como todo array, una vez creado no se puede modificar su tamaño pero, si se alcanza un cierto grado de ocupación, un objeto HashMap puede realizar una reestructuración interna que modifique la longitud de este array sustituyéndolo por otro que doble el tamaño del anterior. En principio se puede establecer una longitud inicial cualquiera, pero se recomienda que sea una potencia de 2 porque internamente, por razones que se verán más adelante, HashMap redondeará el valor que introduzcamos a la potencia de 2 más próxima.

• La clase Node<K, V>. Las instancias de esta clase son los nodos de las listas enlazadas que forman los buckets. Node<K, V> es una clase anidada de HashMap cuyas instancias almacenan las entradas {k, v}.

•   static class Node<K,V> implements Map.Entry<K,V> {
          final int hash;
          final K key;
          V value;
          Node<K,V> next;
  
          Node(int hash, K key, V value, Node<K,V> next) {
               this.hash = hash;
               this.key = key;
               this.value = value;
               this.next = next;
           }
    }
  

  Como se puede observar, una instancia de la clase Node<K, V> guarda una pareja clave-valor {k , v } de una única entrada en los campos final K key y V value. El campo final int hash guarda el hashcode de k, necesario para identificar el bucket en el que colgar la entrada. El el campo Node<K, V> next guarda la referencia del siguiente nodo de la lista enlazada si lo hubiera. Si no, su valor es null.

• Buckets. Los buckets son listas enlazadas simples (Singly Linked List) de nodos que, como se ha comentado, son instancias del tipo Node<K, V>; el primer elemento de la lista (cabecera o head) se almacena en un elemento del array. Se puede decir por tanto que cada bucket cuelga de un elemento del array. Cuando se realiza una inserción de una pareja {k, v}, HashMap crea un nodo y decide en qué bucket colocarlo; esto dependerá, como se verá, del hash de la clave k de la pareja {k, v}. Dicho de otra forma: a partir del hashcode se identifica el índice del array del que cuelga el bucket en el que se colocará el nodo. Lo que funciona en la inserción también se aplica en la lectura: dada una clave k podré identificar el bucket en que se encuentra el nodo que contiene la pareja {K, V} a partir del hashcode de la clave k.

Hasta aquí, la descripción de la estructura interna de la clase HashMap. En la próxima entrada veremos su funcionamiendo.