En informática, Hash se refiere a una función o método
para generar claves o llaves que representen de manera casi unívoca a
un documento, registro, archivo, etc., resumir o identificar un dato a través
de la probabilidad, utilizando una función hash o algoritmo hash. Un
hash es el resultado de dicha función o algoritmo.
Una función de hash es una función para resumir o identificar
probabilísticamente un gran conjunto de información, dando como
resultado un conjunto imagen finito generalmente menor. Varían en los
conjuntos de partida y de llegada y en cómo afectan a la salida similitudes
o patrones de la entrada. Una propiedad fundamental del hashing es que si dos
resultados de una misma función son diferentes, entonces las dos entradas
que generaron dichos resultados también lo son.
Es posible que existan claves resultantes iguales para objetos diferentes, ya
que el rango de posibles claves es mucho menor que el de posibles objetos a
resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros
no tienen un tamaño límite).
Son usadas en múltiples aplicaciones, como los arrays asociativos, criptografía,
procesamiento de datos y firmas digitales, entre otros. Una buena función
de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada;
es decir que se podrán identificar unívocamente las entradas.
La idea basica de esta organización es dividir los registros de un archivo
en cubos, cada una consiste en uno o mas bloques de almacenamiento.
Una funcion Hash h toma como argumento un valor para la llave del archivo y
produce un numero entre 0 y el valor maximo. Si v es un valor llave, h(v) indica
el numero de cubo en el cual el registro con llave v va a buscarse.
Es deseable que h(v) distribuya sin repeticiones (colisiones), los cubos, es
decir que h(v1)<> h(v2) para v1 y v2.
Caracteristicas de las funciones HASH:
Deben calcularse fácilmente
La funcion debe distribuir uniformemente las direcciones sobre el conjunto l
de direcciones de forma que minimice el numero de colisiones.
.
Tablas hash
Las tablas hash, una de las aplicaciones más extendidas de las funciones
de hash, aceleran el proceso de búsqueda de un registro de información
según una. Por ejemplo, una cadena alfanumérica puede ser utilizada
para buscar la información de un empleado en la base de datos de un sistema.
La utilización de tablas hash provee de un acceso casi directo a dichos
registros, lo que significa que, en promedio, una búsqueda puede llegar
a requerir sólo uno o dos intentos en la memoria o el archivo que contiene
la información. Naturalmente, se prefiere una buena función de
hash que evitará colisiones de hash.
Si asumimos que la clave es una cadena de bytes, entonces la función
de hash debería ser como un índice de los registros que tiene
una distribución aleatoria sobre las cadenas de entrada esperadas. De
otra forma, habría más colisiones de hash degradando así
el tiempo de búsqueda.
Algoritmo Rabin-Karp
Este algoritmo es relativamente rápido para la búsqueda de cadena
de caracteres. En promedio, el tiempo de ejecución es lineal con respecto
a la longitud de la entrada. Se basa en la utilización de funciones hash
para comparar cadenas.
Un modelo simple (e ineficiente) de función de hash es
f(x) = 0 para todo entero x.
Obviamente, la colisión hash en esta función es total. Una un
poco más interesante es:
f(x) = x mod 1021
Esto es devuelve el resto de la división x entre 1021. Obviamente, la
colisión es menor siempre que el conjunto del cual toma valores x no
sea muy grande o lo suficientemente aleatorio. Además, nótese
que el hecho de que 1021 sea un número primo no es algo azaroso sino
que fue cuidadosamente elegido ya que mecanismos que utilizan éste tipo
de funciones con números primos como base son muy comunes en criptografía.
Aritmética Modular
Se elige m un numero primo, o con pocos divisores, mayor que el numero n de
registros h(v)=k%m para que las direcciones vayan de o a m-1
H(v)= (k%m) + 1 las direcciones van de 1 a m
K es el conjunto de claves
Ejemplo:
Se tiene un archivo de alumnos y se supone que el numero de direcciones es 996,
m=997.
H(245 643)=245 643%997
H(245 981)=245 981%997
H(257 135)=257 135%997
M=10
99% 10 =9
95% 10=5
96% 10=6
86% 10=6