Una tabla de hash es una estructura de datos en forma de arreglo, que contiene un indexado preferentemente de un conjunto de datos pertenecientes a un mismo contexto. Su función se basa en convertir un valor, considerado clave o llave, en un índice a los datos almacenados. Si bien existen varios métodos de indexación, la tabla de hash posee la particularidad de ahorro de memoria y menor tiempo de complejidad. A diferencia de por ejemplo el direccionamiento directo, donde se posee un universo u con n llaves, de las cuales una determinada cantidad k tienen asignación y el resto son NIL (o null), la tabla de hash va creando llaves a medida que nuevas claves son ingresadas, vinculándolas a los datos guardados.
Tabla 1: Ejemplo de Direccionamiento Directo[1]
En el primer ejemplo, si el universo de claves es grande y la cantidad de llaves utilizadas k es pequeña, la cantidad de memoria desperdiciada es importante, haciéndolo poco eficiente. Con una tabla hash, siendo creados los índices bajo demanda, el espacio es proporcional haciéndolo más eficiente con un k pequeño. La particularidad que presentan las tablas de hash es que en vez de almacenar cada llave en un slot, todos los elementos hash son almacenados en un sólo slot de la función h(k), siendo h la función hash para buscar la llave k.
La asignación de índices se realiza mediante una función de resumen (en inglés llamadas hash), la cual es resultado de aplicar una función resumen a un texto es un número grande, el número resumen, que tiene las siguientes características:
· Todos los números resumen generados con un mismo método tienen el mismo tamaño sea cual sea el texto utilizado como base.
· Dado un texto base, es fácil y rápido (para un ordenador) calcular su número resumen.
· Es imposible reconstruir el texto base a partir del número resumen.
· Es imposible que dos textos base diferentes tengan el mismo número resumen.[2]
El performance de las tablas de Hashing se ve alterado por varios factores, tales como la implementación del código y si este es recursivo o no. Pero principalmente se pueden destacar dos parámetros en especial: Capacidad Inicial y Factor de Carga. El primero, capacidad inicial (Initial capacity), contiene el número de cubos en la tabla de hash; factor de carga (Load capacity) es aquel parámetro que calcula que tan llena esta la tabla de Hash y así obtener más capacidad antes de que esta llegue a su capacidad máxima. Si el número de entradas de la tabla de Hashing excede el producto del factor de carga y la capacidad existente, la capacidad se incrementa en un método llamando rehash. En JAVA, por ejemplo se asigna el valor por defecto al factor de carga de 0.75 que, ofrece un equilibrio entre un buen tiempo de ejecución y una cantidad de espacio aceptable. Contrariamente, valores más altos llegan a disminuir la sobrecarga de espacio, pero aumentan el costo de tiempo para buscar una entrada, logrando que el código no sea tan eficiente.
En las tablas de hashing, cuando se utilizan los algoritmos de función de resumen, puede suceder una colisión entre datos sobre la misma clave, generando así el mismo índice hash para dos datos. Este es un potencial problema, si no se maneja adecuadamente. La solución más popular es que el índice apunte a ambos datos, almacenados en un arreglo, donde cada slot T[j] contiene una lista encadenada de todas las llaves cuyo valor hash es j.[3]
Tabla 2: Solución de colisiones con encadenamiento[4]
De todas formas, se intenta buscar un algoritmo de hash perfecto, donde no se generen colisiones y siempre se garanticen direcciones distintas. Desafortunadamente, evitar por completo las colisiones es casi imposible. Se dice que 1 de 10120000 algoritmos evitarían dichas colisiones. Para reducir el número de colisiones se intenta:
· Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones
· Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
· Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahí buscar por el registro deseado.[5]
Algoritmos de ejemplo cotidiano que pueden ser identificados son el SHA-1 (Secure Hash Algorithm) y el MD5, utilizados para identificar si la descarga de un archivo ha sido descargado por completo y correctamente comparando su hash con el original para garantizar la integridad del archivo. Mediante estos algoritmos se realiza el cálculo del índice generado utilizando el archivo como clave y se comparan para corroborar que generen el mismo índice único.
[5] http://ict.udlap.mx/people/carlos/is215/ir09.html
Autores: Nicolás Manuel Ruiz - Jose Alejandro Jaime
Autores: Nicolás Manuel Ruiz - Jose Alejandro Jaime
No hay comentarios:
Publicar un comentario