hash
Páginas: 2 (315 palabras)
Publicado: 3 de diciembre de 2013
Funciones Hash
En organizaciones de datos, y en el procesamiento de archivos de acceso directo se busca una correspondencia entre la clave del objeto y la dirección física donde éste se almacena.En este caso, la función HASH de la clave, nos define la posición del registro en la tabla.
La función HASH es una transformación matemática que sirve como base para obtener una dirección. Hayvarias técnicas pseudoaleatorias incorporadas en la determinación de direcciones, las más comunes son:
División por un número primo. En este caso se toma el primo mayor entre los menores al númerode posiciones de la tabla. Se divide el número de posiciones por este primo y el residuo se toma como posición.
Supongamos por ejemplo que se tiene un archivo de 7000 registros al que se le hanasignado 7965 posiciones. El mayor número primo menor que 7965 es 7963. Si la clave es 28361, entonces:
28361 = 7963 * 3 + 4472
La dirección asignada en este caso es: 4472.
Doblamiento.Estatécnica se utiliza cuando la clave tiene gran número de dígitos. Consiste en separar la clave en varios grupos de dígitos y sumarlos entre si. El resultado es una función HASH obtenida por doblamiento.Por ejemplo: Si la clave es 163456789, entonces separamos la clave en tres grupos, así: 16 3456 789. Al sumar estos grupos, obtenemos 4261 que corresponde al HASH de la clave.
Ejemplo: Sean N =100 el tamaño del arreglo, y sean sus direcciones los números entre 1 y 100. Sean K1 = 7259 y K2 = 9359 dos claves a las que deben asignarse posiciones en el arreglo. Se aplica la función HASH (K) = Kmod100 + 1, para calcular las direcciones correspondientes a K1 y K2.
H (K1) = 7259 mod100 + 1 = 60
H (K2) = 9359 mod100 + 1 = 60
Como H(K1) es igual a H(K2) y K1 es distinto de K2, se estáante una colisión. Se aplica ahora la fórmula, pero en vez de 100 se utiliza un valor primo (97).
H (K1) = 7259 mod97 + 1 = 82
H (K2) = 9359 mod97 + 1 = 48
Con N = 97 se ha eliminado la...
En organizaciones de datos, y en el procesamiento de archivos de acceso directo se busca una correspondencia entre la clave del objeto y la dirección física donde éste se almacena.En este caso, la función HASH de la clave, nos define la posición del registro en la tabla.
La función HASH es una transformación matemática que sirve como base para obtener una dirección. Hayvarias técnicas pseudoaleatorias incorporadas en la determinación de direcciones, las más comunes son:
División por un número primo. En este caso se toma el primo mayor entre los menores al númerode posiciones de la tabla. Se divide el número de posiciones por este primo y el residuo se toma como posición.
Supongamos por ejemplo que se tiene un archivo de 7000 registros al que se le hanasignado 7965 posiciones. El mayor número primo menor que 7965 es 7963. Si la clave es 28361, entonces:
28361 = 7963 * 3 + 4472
La dirección asignada en este caso es: 4472.
Doblamiento.Estatécnica se utiliza cuando la clave tiene gran número de dígitos. Consiste en separar la clave en varios grupos de dígitos y sumarlos entre si. El resultado es una función HASH obtenida por doblamiento.Por ejemplo: Si la clave es 163456789, entonces separamos la clave en tres grupos, así: 16 3456 789. Al sumar estos grupos, obtenemos 4261 que corresponde al HASH de la clave.
Ejemplo: Sean N =100 el tamaño del arreglo, y sean sus direcciones los números entre 1 y 100. Sean K1 = 7259 y K2 = 9359 dos claves a las que deben asignarse posiciones en el arreglo. Se aplica la función HASH (K) = Kmod100 + 1, para calcular las direcciones correspondientes a K1 y K2.
H (K1) = 7259 mod100 + 1 = 60
H (K2) = 9359 mod100 + 1 = 60
Como H(K1) es igual a H(K2) y K1 es distinto de K2, se estáante una colisión. Se aplica ahora la fórmula, pero en vez de 100 se utiliza un valor primo (97).
H (K1) = 7259 mod97 + 1 = 82
H (K2) = 9359 mod97 + 1 = 48
Con N = 97 se ha eliminado la...
Leer documento completo
Regístrate para leer el documento completo.