BÚSQUEDA POR TRANSFORMACIÓN DE
CLAVES (HASH)“NO A LA SEGUNDA MATRICULA”
AUTORES: JENNIFER BEDÓN – JEAN GOMEZ – JENIFFER GUEMAN – HENRY LAGLA – EDISON MACAS
Objetivo general:
• Adquirir conocimientos sustentables acerca de la Búsqueda por Transformación de Claves (Hash) mediante el uso de la memoria técnica que dará al estudiante facilidad para comprender este método de búsqueda, y así los estudiantes puedan resolver problemas donde será necesario utilizar los conocimientos adquiridos.
Objetivos específicos:
• Conocer los métodos que utiliza la Búsqueda por Transformación de Claves (Hash) y aplicarlos en algoritmos.
• Realizar algoritmos de búsqueda en los diferentes lenguajes estudiados que son: C++, Visual Basic y Java.
• Realizar presentaciones en Prezi y Power Point.
• Realizar un video tutorial sobre este método de búsqueda y subirlo a YouTube.
Asignar a un valor una posición determinada de un arreglo y la
recupera fácilmente. Convierte una clave dada en una dirección (índice), dentro
del arreglo.Los elementos no deben estar
ordenados El tiempo de búsqueda es
prácticamente independiente del número de componentes
del arreglo.
Debe elegirse previamente:
Una función hash que sea fácil de calcular y que distribuya uniformemente las claves.
Un método para resolver colisiones. Si estas se presentan
se debe contar con algún método que genere posiciones
alternativas
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
TABLAS HASH
Función de dispersión que
permita a partir de los datos
(llamados clave) obtener el índice donde estará el
dato en el arreglo
Un vector capaz de
almacenar “m”
elementos
Una función de
resolución de
colisiones
Son estructuras tipo vector que ayudan a asociar claves con valores o datos.
SE CONSTRUYE CON TRES ELEMENTOS BÁSICOS:
MÉTODOS DE TRANSFORMACIÓN DE
CLAVES
• Existen numerosos métodos de transformación de claves. Todos ellos tienen en común la necesidad de convertir claves en direcciones.
• Existen varios métodos:
• Función Modulo• Función Cuadrática• Función Truncamiento• Función Plegamiento
FUNCIÓN MÓDULO (POR DIVISIÓN)
Toma el residuo de la división de la clave entre el
número de componentes del
arreglo.
La función hash queda:
H(k) = (K mod N) +1
Para que la distribución sea
uniforme, N debe ser un número
primo. (El número primo próximo a N)
Sea N=100, el tamaño del arregloSus direcciones de 1-100.
Sea K1 = 7259 K2 = 9359
Dos claves que deban asignarse posiciones en el arreglo
H(K1) = (7259 mod 100) +1=60H(K2) = (9359 mod 100) +1=60
Donde H(K1) es igual a H(K2) y K1 es distinto de K2, es una colisión
Se aplica N igual a un valor primo en lugar de utilizar N=100
H(K1) = (7259 mod 97) +1=82H(K2) = (9359 mod 97) +1=48
Con N=97 se ha eliminado la colisión
FUNCIÓN CUADRÁTICAConsiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El número de dígitos a tomar queda determinado por el rango del índice. Sea K la clave del dato buscar. La función hash queda definida por la siguiente fórmula:
H(K) = digitos_centrales (K2) + 1
La suma de una unidad a los dígitos centrales es para obtener un valor entre 1 y N. ejem:
Clave (K) Mitad del cuadrado(K2)
Dirección
186 186 2 = 034596 45 + 1 = 46
581 5812 = 337561 75 + 1 = 76
723 7232 = 522729 27 + 1 = 28
FUNCIÓN PLEGAMIENTOConsiste en dividir la clave (dígito) en partes iguales. Las operaciones entre los dígitos (partes) puede ser por medio de suma, resta o multiplicación.
H(K) = dígmensig ((d1 ... di) + (di+1 ... dj) + ... + (dl ... dn)) + 1
El operador que aparece en la fórmula operando las partes de la clave es el de suma. Pero puede ser el de la multiplicación. La suma de una unidad a los dígitos menos significativos (dígmensig) es para obtener un valor entre 1 y N.Ejem:
Clave (K) Plegamiento (suma) Dirección
197452 19 | 74 | 52 145 + 1 = 46
280304 28 | 03 | 04 35 + 1 = 36
484001 48 | 40 | 01 89 + 1 = 90
Truncamiento
El truncamiento consiste en tomar algunos dígitos de la
clave y con estos formar una posición en un array. Se ignora parte de la clave para con el
resto formar un índice de almacenamiento.
Existen casos en los que a la clave generada se les agrega una unidad, esto es para los
casos en el que el vector de almacenamiento tenga valores entre 1 y el 100, así se evita la
obtención de un valor 0
H(K1)=dígitos(7 2 5 9)+1=76H(K2)=dígitos(9 3 5 9)+1=96
Lo positivo del truncamiento y una de las ventajas por sobre otros
métodos de búsqueda y ordenamiento es que no solo
funciona con valores numéricos, también funciona con caracteres alfabéticos, esto se puede aplicar
de dos formas:
Transformar cada carácter en un número asociado a su posición
en el abecedario.
Transformar cada carácter en un número asociado a su valor
según el código ASCII.
Ejemplo De truncamiento
La idea consiste en tener un listado de números, seleccionar por ejemplo la posición 2, 4 y 5; para así tener una posición en donde poder almacenar
la clave. Llevando esto a un ejemplo práctico?5700931 7033498610 4810056241 0649134720 1425174829 142
MÉTODOS DE TRATAMIENTO DE COLISIONES
Reasignación
Existen varios métodos que trabajan bajo el
principio de comparación y reasignación de elementos. Se
analizaran tres de ellos:
Prueba cuadrática
Doble dirección
hash Prueba Lineal
Arreglos anidados
Áreas de desborde
Métodos mas usados para resolver colisiones
Pru
eb
a
Lin
eal
Consiste en que una vez detectada la colisión se debe de recorrer el arreglo
secuencialmente a partir del punto de colisión, buscando al elemento el proceso de búsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una
posición vacía
Se trata al arreglo como a una estructura circular: el siguiente elemento después del ultimo es el primero
Prueba Cuadrática
Las direcciones alternativas se generan como D + 1, D + 4, D + 9,
. . ., D + i² en vez de D + 1, D + 2,...,D + i como en la prueba lineal.
La principal desventaja de este método es que pueden quedar casillas del
arreglo sin visitar
Además, como los valores de las direcciones varían en 1² unidades,
resulta difícil determinar una condición general para detener el
ciclo.
Este problema podría solucionarse empleando una variable auxiliar, cuyos valores dirijan el recorrido del
arreglo de tal manera que garantice que serán visitadas todas las casillas.
Doble Dirección
Consiste en generar otra dirección hash, una vez que se detecta la colisión, la generación de la nueva dirección se hace a partir de la
dirección previamente obtenida más uno.
El proceso termina cuando el elemento es encontrado o existe una posición vacía
La función hash H 2 que se
aplique a las sucesivas
direcciones puede ser o no ser la misma
que originalmente se aplicó a la
clave.
Ejemplo
ARREGLOS ANIDADOS
Este método consiste en que cada elemento del arreglo tenga otro arreglo en el cual se
almacena los elementos
colisionados
elegir un tamaño adecuado de arreglo el coste de memoria
el número de valores colisionados que
pudiera almacenar
depende del espacio que se halla asignado
Ocupa un espacio adicional al de la tabla
Requiere un manejo de lista ligada
Si la lista crecen demasiado se pierde el acceso directo del método hash
desventajas
ENCADENAMIENTO
Cada elemento del arreglo tiene un apuntador a una lista ligada, la
cual se irá generando e ira almacenando los valores
colisionados
CONCLUSIONES:
• Las tablas hash permiten que el coste medio de las operaciones insertar, buscar y eliminar sea constante, siempre que el factor de carga no sea excesivo para reducir la probabilidad de colisión.
• Una función hash debe ser fácilmente calculable, sin costosas operaciones, también debe tener una buena distribución de valores entre todas los componentes de la tabla.
• Si la función está mal diseñada producirá muchas colisiones.
• La fortaleza de una función hash requiere que estas colisiones sean las mínimas posibles y que encontrarlas sea lo más difícil posible.
RECOMENDACIONES:
• Tome en cuenta los requisitos para elaborar una buena tabla hash.
• Escoja el tipo de tabla adecuado para nuestro algoritmo.
• Trate de que el número de colisiones sea casi nulo.
• En caso de que existan colisiones opte por el método de tratamiento más adecuado para su algoritmo.
Recommended