Función Hash: metodos de división y de medio Cuadrado.
14
Universidad Nacional de Costa Rica Hash : -Método de división. -Método del medio cuadrado.
-
Upload
ana-castro -
Category
Software
-
view
596 -
download
7
Transcript of Función Hash: metodos de división y de medio Cuadrado.
Universidad
Nacional de
Costa RicaHash :
-Método de división.
-Método del medio cuadrado.
Hash:Una función hash H es una función computable mediante un algoritmo,
H: U→ M
x→ h(x),
que tiene como entrada un conjunto de elementos, que suelen ser cadenas, y los convierte (mapea) en un rango de salida finito, normalmente cadenas de longitud fija.
Uso de funciones Hash:proteger la
confidencialidad de una
contraseña
garantizar la integridad
de los datos.
verificar la identidad del emisor de un mensaje
mediante firmas digitales.
Colisión:Un problema potencial encontrado en elproceso hash, es que tal función no puedeser uno a uno; las direcciones calculadaspueden no ser todas únicas, cuando
H(K1) = H(K2).
Si K1 es diferente de K2 decimos que hayuna colisión. A dos claves diferentes que lescorresponda la misma dirección relativa seles llama sinónimos.
Método de División
La función de este método es dividir el valor
de la llave entre un numero apropiado, y
después utilizar el residuo de la división
como dirección relativa para el registro.
F(hash) = llave % divisor.
Existen varios factores que deben
considerarse para seleccionar el divisor:
divisor > n :
suponiendo que
solamente un
registro puede ser
almacenado en
una dirección
relativa dada.
Seleccionarse el
divisor de tal forma
que la
probabilidad de
colisión sea
minimizada.
Uso:Cuando la distribución de los valores de llaves
no es conocida.
Ejemplo:
Si la tabla hash tiene
tamaño m = 12 y la llave
es
k = 100, entonces
h(k) = 100 mod 12 = 4.
Método de medio
cuadradoConsiste en elevar al cuadrado la clave y tomar losdígitos centrales como dirección. El número dedígitos a tomar queda determinado por el rangodel índice. Sea K la clave del dato a buscar, lafunción hash queda definida por la siguienteformula:
H(K) = digitos_centrales (K^2) + 1
Las suma de los dos dígitos centrales de la clave K (elevada al cuadrado) más 1, debe obtener un valor entre 1 y N (N, tamaño del arreglo).
Uso:puede aplicarse en archivos con factores de
cargas bastantes bajas
Ejemplo: Sea N=100 el tamaño delarreglo.
Sea su dirección los númerosentre 1 y 100.
Sea K1 = 7259 una clave a laque se le debe asignar unaposición en el arreglo.
K1^2 = 52 693 081H(K1) = ( 52 693 081 ) + 1 = 94
EJERCICIO
C++
Gracias!
Estudiantes:
Mª Analive Castro Vargas.
Andrés Dalolio Aguilar.
Fernando Navarro Juárez.
