Hash

HASH
Consiste en:
* Crear un arreglo de claves.
* Asignar una clave a cada dato a través de una función, llamada función Hash.
* Asociar el dato a la clave.
* La búsqueda del dato serealiza utilizando la lista de claves que le corresponde y no el dato mismo.
* Es beneficio para una cantidad grande de datos.

Ventajas:
* Aumenta la velocidad de búsqueda por quedisminuye el conjunto de datos.
* Los datos no tienen que estar ordenados.
* Es independiente de la cantidad de datos (n).

Aplicaciones HASH:
* Contraseñas.
* Firmas Digitales.
*Integridad y autentificación de un mensaje.

Función Hash apropiada:
* El tamaño del arreglo debe ser más grande que el número de elementos a insertar.
* Para los elementos de tipo carácter, sedivide en cada uno de sus caracteres y se calcula la suma del valor entero (ASCII) y a la suma se le aplica el modulo por el tamaño del arreglo hash.
* Si los elementos son numéricos, se establecela función hash en términos del residuo entre el número y el tamaño del arreglo.
* Cuanto más grande el rango de la función, menos probable que dos datos generen el mismo valor de asignación.Soluciones a las colisiones:
* Factor de carga, relación entre el número de elementos (n) y tamaño del arreglo (m)
λ = n / m
* Doble Direccionamiento
* Cuando se detecta una colisión sedebe generar otra dirección aplicando una función hash h2 a la dirección previamente obtenida. Y se realiza una búsqueda lineal en las posiciones que se encuentre en la distancia calculada.
*h1 = x % m / h2 = R – (x % R)
M: tamaño del arreglo de claves.
R: menor primo siguiente al tamaño de arreglo. Se obtiene mejores resultados cuando el tamaño del arreglo es un número primo.
*Inserción de una clave: O(1)
* Buscar la posición sobre el arreglo: O(1)
* Eliminación de una clave toma un tiempo: O(1+ λ). Aquí suponemos que la clave debe ser buscada dentro de la lista,...