La estructura de datos HashMap de java (2)

Como se ha comentado en la anterior entrada, HashMap es una estructura de datos que, por diseño, busca optimizar las operaciones de búsqueda e inserción de parejas clave-valor {k, v}

Lo esencial del funcionamiento de la estructura HashMap es que se pueda identificar a priori de la manera más aproximada posible la posición en la estructura de datos de una pareja clave-valor {k, v} de forma que se evite realizar costosas búsquedas elemento a elemento por toda la estructura del HashMap. Dado que en las estructuras HashMap no se permite que haya más de una pareja clave-valor con igual clave k, para buscar una pareja {k, v} bastará con localizar en la estructura una clave k dada.

Si conocida la clave k puedo identificar a priori el lugar que le correspondería a la pareja {k, v} en la estructura, puedo realizar la búsqueda directamente sin necesidad de bucles ni iteraciones sobre el conjunto de la estructura, mejorando enormemente la eficiencia de la estructura de datos. Recuérdese que en una estructura HashMap se debe realizar una búsqueda de la clave k no sólo para localizar el valor v asociado, sino para verificar si existe ya una pareja con esa misma clave antes de realizar una inserción de una nueva pareja {k, v}.

En notación Big(O) se diría que la complejidad de un algoritmo de búsqueda capaz de identificar directamente la posición de un elemento es O(1) (constante) porque se accede al dato independientemente de la posición en que se encuentre sin necesidad de bucles ni iteraciones.

En realidad, en una estructura de datos como HashMap no se garantiza que se pueda identificar con exactitud la posición de una pareja de claves {k, v} a priori. Lo más que se puede saber a priori es el bucket que le correspondería a la pareja {k, v}caso de existir en la estructura una pareja clave valor con esa clave. En una estructura HashMap, el bucket o lista enlazada simple que corresponde a una pareja {k, v} depende del valor de la clave k. Una vez identificado el bucket que le corresponde a la clave k será necesario recorrer uno a uno todos sus nodos para comprobar si existe una pareja {k, v} con la mencionada clave k. El tiempo de búsqueda, por tanto, depende de la longitud del bucket con lo que no se puede garantizar una complejidad O(1). Pero sí se puede reducir enormemente la complejidad si por lo menos se puede identificar a priori el bucket en el que se debería encontrar la pareja {k, v} en el caso de que haya una pareja clave-valor con clave k. Además, si la estructura HashMap está bien implementada, los buckets estarán formados por pocos elementos con lo que el recorrido por sus elementos será rápido.

Para conocer a priori el bucket es necesario identificar a priori la posición del índice i del array subyacente de la estructura HashMap de la que cuelga el bucket que contiene la entrada que se busca. Para ello, en una estructura HashMap existe una correspondencia directa entre el hash de la clave k y el índice i del array del que cuelga el bucket que le corresponde a la clave, caso de existir. Si el HashMap está bien configurado y la función hashCode que calcula el hash de k es eficiente, los buckets dispondrán de pocos elementos o incluso de un solo elemento, con lo que la eficiencia de la operación de búsqueda de la pareja {k, v} estará garantizada.

Asignación de buckets a una pareja {k, v}

La clave por tanto está en cómo se asigna el bucket que le corresponde a una pareja {k, v}. Como se ha comentado, el bucket depende de la clave k. La siguiente figura muestra el procedimiento empleado. Como se ve, el proceso consta de dos pasos:

1. En primer lugar se calcula el hashcode de la clave k. Para ello, se aplica el método hashCode() que todo objeto tiene implementado (como mínimo lo hereda de la clase Object) y que, si es necesario, se debe sobreescribir. Este es el punto de partida para identificar la posición de una pareja {K, V} en una estructura de datos.

   El hash de la clave k que debe devolver el método hashCode() es un valor entero int. Existen infinidad de técnicas para calcular el hash de una instancia. No es objeto de esta entrada explicar cómo implementar un método hashCode() eficiente pero, lógicamente, debe ser poco costoso computacionalmente; debe devolver un valor constante para un mismo objeto aunque éste experimente mutaciones; debe garantizar que dos instancias distintas de k produzcan también un código hash distinto dentro de un rango determinado y debe distribuir los valores del hash dentro de dicho rango de la manera más uniforme posible. Téngase en cuenta en todo caso que un método hash erróneo tendrá como consecuencia un uso ineficiente de la estructura HashMap.

2. Una vez calculado el hash de k, se debe aplicar un método que asigne un índice del array a la clave k en función de dicho hash. Lógicamente el rango del índice del array va de 0 al valor length-1, siendo length la longitud del array, por lo que no puedo usar valor del hash como índice porque lo normal es que el rango del hash sea distinto al de los posibles valores del índice del array. Se necesita por tanto un método que adjudique un valor del índice a partir del valor del hash.

   En este punto es preciso adoptar un compromiso: lo ideal para que la estructura sea lo más eficiente posible desde el punto de vista computacional es que el array posea tantas entradas como posibles valores puede tomar la función hashCode() de un objeto k. De esta manera se podría realizar una correspondencia directa 1 a 1 del valor del hash de k a la posición i que ocupará el nodo que guarda la pareja {k, v} en el array. Entonces podríamos hablar de una complejidad O(1) dado que no sería necesario buscar la pareja {k, v} dentro de los buckets: cada pareja posible {k, v} se encontraría en una posición distinta del array y esta posición sería directamente identificable a partir del hash de k. De hecho, no habría buckets en sentido estricto ni listas enlazadas, puesto que todos los nodos se almacenarían directamente en el array de la estructura.

   Lógicamente esto no es viable. Los arrays son por definición de longitud fija y reservan memoria para guardar los datos en el momento de su creación. Crear un array con tantos elementos como valores posibles puede tomar el hash de un objeto es inviable por la cantidad de memoria que exigiría. Forzosamente tiene que haber menos elementos en el array del objeto HashMap que valores posibles tiene el hash del objeto k.

Dicho de otra forma: es inevitable que a claves k distintas, aunque tengan distinto hash, se les asigne una misma posición en el array de la estructura HashMap. Pero en una posición del array sólo cabe la referencia a un objeto. ¿Cómo almaceno entonces dos parejas {k, v} distintas que he asignado a una única posición de memoria en un array? Para eso existen los buckets. Como se ha comentado, los buckets son listas enlazadas simples que cuelgan de una posición del array. Si asigno una pareja {k, v} a una posición del array que ya está ocupada por un nodo, lo que se hará es enganchar el nuevo nodo al ya existente creando una lista enlazada o bucket. Si ya existían varios nodos colgando de un nodo en ese elemento del array lo que se hará es enganchar el nuevo nodo al último nodo (cola o tail) de la lista enlazada simple o bucket.

A la asignación de un mismo bucket a claves k distintas algunos lo llaman colisión de hash o hash collision, pero en realidad lo que ocurre es otro tipo de colisión. El fenómeno de colisión de hash se da cuando dos objetos distintos producen el mismo hash, pero en este caso se trata de asignar el mismo índice del array a dos entradas distintas tengan o no distinto hash por la sencilla razón de que hay menos registros en el array que posibles valores del hash con lo que mi función asigna el mismo índice a distintos hashcodes. Esto no quita que si el hashCode() no está bien implementado pueda darse el fenómeno de la colisión de hash que, en todo caso, es indeseable.

Para la asignación de posiciones del array a parejas {k, v} a partir del valor del hash de k, HashMap usa el método privado indexFor(h, l):

static int indexFor(int h, int length) {
   return h & (length-1);
}

Donde h es el hash de la clave k y length la longitud del array.

El operador & calcula el producto lógico a nivel de bits entre los valores h y (length - 1). Básicamente efectúa dos operaciones:

1. Traduce los operandos a código binario y aplica una máscara para que la longitud de los números binarios h y (length -1) sea equivalente.

2. Realiza el producto lógico entre ambos números binarios.

Por ejemplo, supongamos los siguientes valores:

Hash de k: h = 77_797_729

Longitud del array de la estructura HashMap: 16

h (binario): 100 101 000 110 001 100 101 100 001 (77797729, en decimal)

length-1 (binario): 000 000 000 000 000 000 000 000 111 (16-1 = 15, en decimal)

Se aplica la máscara y se opera:

h AND (l-1) = 001 AND 111 = 001 (1 en decimal)

Por lo tanto, a la pareja {k , v} le corresponderá el bucket que cuelga de la posición 1 del array de la estructura. Si el método hasCode() está bien implementado devolverá códigos hash únicos y diferentes para distintos objetos K y los códigos estarán uniformemente distribuidos en su rango de valores. Si este requisito se cumple, el método indexFor(int h, ing length) repartirá las entradas uniformemente entre los buckets que cuelgan del array.

Otra opción habría sido asignar al nodo un índice que fuera el resto de la división entre el hash y la longitud del array (operación módulo), pero esta operación resulta computacionalmente más costosa por lo que el desarrollador de HashMap optó por la solución propuesta.