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.