Hash plegamiento

HASH PLEGAMIENTO

Plegamiento
Consiste en dividir el número en diferentes partes, y operar con ellas
(normalmente con suma o multiplicación).
La función hash se define de la siguinete forma:
• H(x)= X1 + X2 + X3+ … +Xr
• Por ejemplo, si dividimos el número de 7 cifras en 2, 2 y 3 cifras y se
suman, dará otro número de tres cifras (y si no, se toman las tres
últimas cifras):
También se producecolisión: cuando dos clavez se direcciona a la
misma dirección o bucket se dice que hay una colisión, y a las claves se
les denomina sinónimos.

• La técnica de plegar la clave de dispersión seutiliza a menudo para trasformar una clave muy
grande en otra más pequeña y, a continuación, aplicar la función hash de aritmética modular.

5700931 → 57 + 00 + 931 = 988
3498610 → 34 + 98 + 610 = 7420056241 → 00 + 56 + 241 = 297
9134720 → 91 + 34 + 720 = 845
5174929 → 51 + 74 + 929 = 1054

Tratamiento de colisiones
•

Hay diferentes maneras de solucionarlas pero lo más efectivo es en vez de crearun
arreglo de número, crear un arreglo de punteros, donde cada puntero señala el
principio de una lista enlazada.

•

Así, cada elemento que llega a un determinado índice se pone en el último lugar dela
lista de ese índice.

•

El tiempo de búsqueda se reduce considerablemente, y no hace falta poner
restricciones al tamaño del arreglo, ya que se pueden añadir nodos dinámicamente a
la lista.PRUEBA LINEAL
Consiste en que una vez detectada la colisión se debe recorrer el arreglo secuencialmente a partir
del punto de colisión, buscando al elemento.
El proceso de búsqueda concluye cuando elelemento es hallado, o bien cuando se encuentra una
posición vacía.
El arreglo se trata como una estructura circular: el siguiente elemento después del último es el
primero.
La función de rehashing es, portanto, de la forma: R(H(X)) = (H(X) + 1) % m (siendo m el tamaño del
arreglo).
Ejemplo: Si la posición 397 ya estaba ocupada, el registro con clave 0596397 es colocado en la
posición 398, la cual...