Hash tables, diccionarios o la memoria del futuro

El ordenador, siguiendo el modelo actual, posee una memoria dividida en celdas que puede referenciarse palabra a palabra para obtener contenido de manera inmediata.  Los ingenieros decimos que el acceso a una celda de memoria tiene coste en O(1) o constante. No hay que buscar nada tan sólo pedir lo que haya en la celda número 42 y ¡presto! ahí está.

Este esquema de memoria es muy versátil porque representa listas de elementos. Casi cualquier estructura de datos puede representarse en una lista y, utilizando punteros, las listas no tienen por qué ser homogeneas. Podemos guardar en ellas de todo e identificar cada objeto guardado por el índice dentro de la lista. En otras palabras, por su posición.

Traducir una lista de objetos a un segmento de la memoria es tan simple como conocer el número de elementos, el tamaño de los mismos y la posición del primero.

Sobra decir que al concepto de lista está unido, muy fuertemente, el concepto de orden y posición.

Si hablamos de colecciones de elementos sin orden, como por ejemplo un conjunto, dónde no nos interesa en qué posición está un objeto, tan sólo si está o no está, encontramos que las listas dejan de resolver el problema elegantemente. Sin duda añadir un objeto a una lista es tan sencillo como añadir un nuevo elemento a una lista… ¿o no? Es un conjunto y en los conjuntos, formalmente descritos, no hay dos elementos iguales por lo que nos convendría no tener repeticiones. Así que antes de insertar un objeto habrá que buscarlo en la lista lo que en el mejor de los casos, tiene una complejidad de O(log n) y en el caso medio, de O(n). En palabras sencillas, buscar es una tarea sencilla pero cara en colecciones muy grandes.

Además, encontrar un objeto del conjunto, al no tener un orden predeterminado (nadie nos asegura que siempre metamos A primero, B segundo,  C tercero…), requiere una búsqueda también. Y eliminarlo, por definición requiere primero encontrarlo, así que tres cuartos de lo mismo.

Con esto en mente, un pedazo de ingeniero eléctrico, Dudley Allen Buck, describió un nuevo tipo de memoria llamada asociativa o direccionada por contenido. Esta memoria toma un objeto entero y lo busca en su interior pero esta búsqueda está hecha de tal forma que el acceso sigue siendo constante. ¿Magia? Nop, ¡ingenio!

La solución por hardware es muy simple aunque el diseño final de la memoria resulta más complicado que las memorias RAM corrientes. Consiste en, mediante circuitería, comparar el elemento que se desea recuperar con toda la memoria. Evidentemente, un circuito de comparación por cada bit en la memoria son muchos miles de millones de circuitos de comparación lo que encarece notablemente el coste.

La solución por software es más complicada pero mucho más barata y consiste en utilizar una tabla hash. La idea, no obstante, es muy sencilla: tomamos un objeto, le hacemos alguna transformación y lo convertimos en un número y tomamos el numero como la posición en una lista donde debería ir el objeto.

Ahora, si queremos comprobar si  un objeto está en el conjunto, basta con realizar la transformación e ir a mirar justo a ese lugar de la lista.

A esa transformación se la llama función hash y a la lista de elementos, tabla hash.

Funciones hash

Las funciones hash son procedimientos matemáticos que condensan información. Toman un objeto complejo y devuelven por lo general un número entero que lo representa de alguna manera llamado valor, código o clave hash.

Tienen muchos usos y se espera de ellas que cumplan una serie de propiedades:

• Bajo coste. Si el procedimiento de cómputo del valor es costoso, entonces lo que ganamos evitando la búsqueda, lo perdemos realizando la transformación.
• Determinista. La función no puede depender de un estado o involucrar un procedimiento aleatorio o el valor obtenido para un objeto podría no ser siempre el mismo con lo que perderíamos la ventaja de la búsqueda.
• Continuidad. Objetos similares deberían producir números cercanos. Es como funciona la corrección automática de términos de búsqueda de Google, por ejemplo. Quiere decir que «complejo» y «conplego» deberían convertirse en números muy parecidos.
• Rango variable. El rango es el conjunto de todos los posibles valores de salida de una función. El rango de una función hash es, por lo general, finito. Esto significa que puede producir hasta un número fijo de resultados y no más. Aun así, existen generadores de  funciones hash que, indicando el tamaño del nuevo rango, producen una nueva función hash que puede ser:
• Diferente a la función para el rango anterior por lo que aplicar la nueva función a un objeto devendrá en un valor hash distinto del que se hubiese obtenido con la función vieja.
• Parecida a la función para el rango anterior por lo que es muy probable que al aplicar la nueva función a un objeto, el resultado sea el mismo o muy similar al que se hubiese obtenido previamente.
• Minimización de colisiones o uniformidad. Llegamos al cogollo del asunto. Hemos dicho que el rango de una función hash es finito por lo que si el conjunto de datos de entrada es más grande que el rango, lógicamente algún valor se tendrá que repetir (intenta empaquetar 90 libros en 20 cajas, a ver cómo lo haces). Pues bien, cada vez que la función produce el mismo valor para un par de objetos se dice que ha habido una colisión. Es deseable que las funciones hash minimizen el número de colisiones y que distribuyan los datos de entrada uniformemente sobre el rango (en el ejemplo de los libros, es deseable que haya como mucho, 5 libros por caja).

Tablas hash

Las tablas hash también reciven el nombre de diccionarios porque son conjuntos de pares clave-valor donde la clave es el resultado de aplicar la función hash sobre el valor. Se dice que la búsqueda se realiza por clave para recuperar un valor.

Ahora que sabemos qué es una función hash, basta con pensar que una tabla hash es una lista con un número de posiciones disponibles igual al rango de la función hash. Como hemos comentado anteriormente, la función hash puede producir que dos objetos distintos nos lleven a la misma posición, por ello una tabla hash no guarda directamente los elementos sino una lista de los mismos.

Así, cada posición de la tabla hash se denomina bucket o cubo porque almacena los objetos con el mismo valor hash.

Algunas tablas guardan el elementos más accedido primero y luego los demás de manera que cuando se trata de buscar un elemento en concreto, se le aplica la función, se obtiene el valor, se visit la posición correspondiente y se compara con el primer elemento. Es muy probable que se trate de este pero, si no lo es, sencillamente se busca en la lista del bucket.

Las tablas hash poseen un determinado umbral de llenado. Una vez rebasado, la tabla se expande para poder albergar más elementos. La nueva tabla puede requerir una función hash distinta así que le toca extraer todos los elementos, pasarles la nueva función y volverlos a incluir en la nueva. Otro procedimiento consiste en crear una nueva tabla y conservar la vieja, buscar en ambas, insertar sólo en la nueva y cuando la vieja quede vacía, eliminarla.

La principal ventaja de una tabla hash es, sin duda, la velocidad. La desventaja principal es que elegir una función de hash que funcione bien de forma general es prácticamente imposible y escoger una para un tipo de datos dado es más una cuestión de arte e intuición. Si no se escoge la función hash cuidadosamente, el número de colisiones podría dispararse y el rendimiento decaer considerablemente.

Usos y aplicaciones

Muchos lenguajes de programación modernos incluyen las tablas hash como tipo de dato básico. El uso de tablas hash tiene sus máximos exponentes en:

1. Arrays asociativos. Listas cuyos índices suelen ser cadenas de texto, aunque también podrían ser cualquier cosa. Por ejemplo, el número de teléfono de 555-666-777 está en un array asociativo indexado bajo el nombre de «John».
2. Indexación de bases de datos. Si sabemos de antemano que en una base de datos vamos a realizar búsquedas de un determinado campo, podemos usar una tabla hash aplicada sobre este campo para recuperar la información rápidamente.
3. Conjuntos. Un conjunto es, directamente, una tabla hash. El orden no importa y (dejando a parte o resolviendo las colisiones como hemos visto) la función hash nos permite ver si el elemento está contenido o no en tiempo constante.
4. Representación de objetos. Muchos lenguajes de programación modernos como Perl, Python, Lua o Javascript usan tablas hash para representar sus objetos. Las claves suelen ser los nombres de sus miembros o métodos (sean funciones, tipos simples o tipos compuestos) mientras que los valores son punteros a los respectivos miembros o métodos.

Conclusiones

De todos sus usos, la representación de objetos es la más interesante. Los lenguajes verdaderamente orientados a objetos, los cuales definen su entorno de ejecución en base a sí mismos, gozan de un dinamismo y versatilidad extremas. Practicamente cualquier cosa puede representarse como un conjunto de propiedades con nombre y valor, esto es, un diccionario. Además, la inclusión de tipos ejecutables (es decir, variables que pueden contener programas) permiten todo tipo de transformaciones en los objetos: añadir métodos, quitarlos, redefinirlos…

Desde mi punto de vista, me parece la memoria del futuro, una especie de estructura de datos universal.