Hash

TAD Tabla Hash


Definición.


Es un conjunto formado por un número arbitrario de elementos distintos (del mismo tipo), identificado cada uno por una palabra clave diferente, junto con un conjunto de procedimientos de acceso.

Breve Introducción.


A diferencia de una Búsqueda indexada por claves ordinaria, donde usamos el valor de las claves como índices de un arreglo ynecesitamos indispensablemente que los mismos sean enteros distintos dentro de un rango equivalente al rango del Arreglo, utilizar el método de Hashing nos permite manejar aplicaciones de búsqueda donde no tenemos claves con tan fortuitas propiedades. El resultado es un método de búsqueda completamente diferente a los métodos basados en comparaciones, ahora en vez de navegar por las estructurascomparando palabras clave con las claves en los items, tratamos de referenciar items en una tabla directamente haciendo operaciones aritméticas para transformar claves en direcciones de la tabla. Esto último se logra implementando una Función Hash, que se va a encargar de dicha transformación.

Idealmente , todas las claves van a mapear a direcciones diferentes, pero es muy frecuente que dos omas claves diferentes sean transformadas a la misma dirección, cuando esto pasa, decimos que estamos en presencia de una Colisión. Es por eso que también debemos implementar algún proceso de resolución de Colisiones, que se va a encargar de tratar tales situaciones. Uno de los métodos de resolución de colisiones que existen usa Listas ligadas (Linked lists) y se lo denomina “encadenamientodirecto” o “Hashing abierto” el cual es muy útil en situaciones dinámicas, donde el numero de elementos es difícil de predecir por adelantado.

El Hashing es un buen ejemplo de balance entre tiempo y espacio. Si no hubiera limitaciones de memoria, entonces podríamos hacer cualquier búsqueda en un solo acceso simplemente utilizando la clave como una dirección de memoria. Este ideal no puede serllevado a cabo, porque la cantidad de memoria requerida es prohibitiva cuando las claves son largas. De la misma manera, si no hubiese limitación de tiempo, podríamos usar un mínimo espacio en memoria usando un método secuencial. Hashing provee una manera de usar una razonable cantidad de memoria y tiempo y lograr un balance entre los dos extremos mencionados. En particular, podemos lograr elbalance que deseemos simplemente ajustando el tamaño de la tabla, sin necesidad de re-escribir código o cambiar algoritmos.

En líneas generales podemos decir, que es razonable esperar búsquedas (Search), borrados (Delete) e inserciones (Insert) en tiempo constante , independientemente del tamaño de la tabla. O sea que es ideal para aplicaciones que realicen mayoritariamente este tipo deoperaciones, por el otro lado, Hashing no provee implementaciones eficientes para otras operaciones como por ejemplo Ordenamiento (Sort) o Selección (Select)

Funciones Hash:
Es la que se va a encargar de transformar las claves en direcciones de la tabla.
Podríamos definir a la “función ideal” como aquella que distribuya a todos nuestros objetos lo mas uniformemente posible sobre la gama devalores índice, es decir, si tenemos una tabla que puede almacenar M items, entonces requerimos de una función que transforme claves a enteros en el rango [0, M-1] ,que la salida sea aproximadamente equiprobable para cada entero., y que la distribución no esté ligada a patrón alguno. Debe ser calculable de modo eficiente, o sea, estar compuesta de un numero reducido de operaciones aritméticas básicas.No hay reglas que permitan determinar cual será la función mas apropiada para un conjunto de claves, para asegurarse de una uniformidad máxima. Hacen un análisis de las características de las claves, puede sin embargo ayudar en la elección de la función.
La implementación de la función hash depende del tipo de clave. No va a ser la misma si la clave es un int, un float o un String...