Una pequeña introducción a las Tablas Hash

Este es un concepto ampliamente utilizado en informática y que es muy fácil encontrarte cuando haces una entrevista de trabajo técnica, no es raro enfrentarse a la pregunta ¿Qué es una tabla Hash y qué coste tiene? Responder correctamente a esta pregunta puede marcar una gran diferencia y quedar como un gurú.

Antes que nada comentarte que este post es meramente teórico y nada que ver con un lenguaje en concreto, tengo preparado un siguiente donde entraremos a picar código, pero como no todo en la vida es tirar código como cosacos, creo que en ocasiones es bueno saber lo que está ocurriendo por detrás de eso que estás codificando, te evitará alguna que otra liada parda en el futuro.

Estas tablas son algo que se utiliza en muchísimos algoritmos, sobre todo cuando se tiene una gran cantidad de información sobre la que hay que hacer búsquedas, permiten un ahorro considerable de memoria y pueden ser muy eficientes si el número de registros se mantiene dentro de lo previsto.

Las tablas Hash, o tablas de dispersión si lo prefiere en castellano, son un tipo de estructura de datos asociativa, relaciona una llave y un valor utilizando una función de Hash, esta función será la encargada de calcular el íncide al que han de ir los elementos que estamos guardando en la tabla.

Estas funciones tienen una serie de propiedades:

  • Debe repartir equiprobablemente los valores, o sea, se debe mantener una distribución de probabilidadad y no devolver siempre el mismo índice.
  • Esta función se debe poder calcular de manera eficiente.
  • Si se producen cambios en la clave, debe suponer cambios significativos en esta función.

Hay exactamente dos dimensiones sobre las que poder evaluar las funciones Hash, por los datos y por su eficiencia, estas tablas están muy relacionadas con los datos que se van a guardar en ellas, no es lo mismo guardar una relación de DNIs que para trabajar en firma digital (donde podemos crear un hash de la información enviada y cifrarlo con nuestra clave privada para que cualquiera con nuestra clave pública pueda ver el hash real y verificar que el contenido del archivo es el que hemos mandado nosotros), este análisis nos deberá indicar la probabilidad de posibles colisiones (insertar dos entradas distintas con la misma clave). No podemos olvidar que esta función debe ser eficiente, su complejidad deberá ser constante a lo sumo de orden logarítmico.

He nombrado la palabra maligna, colisión. En las funciones Hash utilizadas para la ordenación, es muy frecuente que se den casos de colisión de dos claves, si esto ocurre hay que realizar una resolución de dichas colisiones, esto no se puede quedar así, tendremos que buscar una forma de solucionar la colisión en caso de producirse.

Tenemos dos métodos principales para solucionarlo. Hashing Abierto y Hashing Cerrado.

El Hashing Abierto utiliza estructuras dinámicas externas a la tabla para almacenar las claves que han colisionado. Este método es válido, pero no es del todo eficiente, por eso se recomienda la otra solución, el Hashing Cerrado.

El Hashing Cerrado permite resolver la colisión mediante una búsqueda alternativa y hacer la insercción en otra ubicación de la misma tabla.

El problema del Hashing Cerrado es que a medida que la tabla se llena, aumentará la probabilidad de colisión, tenemos tres apaños para reducir este problema, hacer un recorrido Lineal, o sea, a la dirección obtenida por la función Hash se le añade un incremento lineal para obtener otra dirección (vamos, ir sumando uno al índice hasta encontrar un hueco), recorrido Cuadrático, este método permite una mayor dispersión de las colisiones que el lineal, haremos una exploración completa y recorreremos todos los bloques de la tabla, finalmente tenemos el recorrido mediante doble Hashing, que no es otra cosa que añadir una segunda función Hash distinta a la original, un clásico es acudir a los números primos para recuperar el nuevo índice, pero ojo, este número primo siempre deberá ser menor que el tamaño de la tabla.

Bueno, pues esto es muy por encima el mundo de las tablas Hash, si te encuentras muy motivado, puedes hacerte tu propia tabla Hash, como puedes ver en el siguiente vídeo:

O, si eres javero, puedes aprovecharte de las estructuras que ya están en nuestro querido java.util, como son HashTable y HashMap y sobre ellas te hablaré en el próximo post.

Dejar una contestacion

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *