Mind map
Resolución de colisiones Hash

Mapa mental: Resolución de colisiones Hash
Map content
Resolución de colisiones Hash
Clasificación de los métodos: • Reasignación • Arreglos anidados • Encadenamiento
Consideraciones: • La estructura de datos para almacenar las claves originales según la dirección o índice generado por la función Hash, debe de implementarse cómo una estructura circular.
Busqueda en listas:
- con mucha frecuencia los trabajadores trabajan con grandes cantidades de datos
- la busqeda ecuencial busca un elemento en una lista utilizando un valor destino llamado clave
- busqueda binaria:
- la busqueda secuencial se aplica a cualquier lista, si la lista esta ordenada.
- Búsqueda mediante Hashing
- Existe un método que puede aumentar la velocidad de búsqueda donde los datos no necesitan estar ordenados y esencialmente es independiente del número n. Este método se conoce como transformación de claves o hashing. El hashing consiste en convertir el elemento almacenado (numérico o alfanumérico) en una dirección (índice) dentro del array.
- MÉTODO DE DIVISIÓN: Se escoge un número m mayor que el número n de elementos a insertar, es decir, el array posee más posiciones que elementos a insertar. La función hash H se define por: H(X) = X % m o H(X) = (X % m) + 1 donde X % m indica el resto de la división de X por m. La segunda fórmula se usa cuando queremos que las direcciones hash vayan de 1 a m en vez de desde 0 hasta m-1. El mejor resultado del método de división se obtiene cuando m es primo (es decir, m no es divisible por ningún entero positivo distinto de 1 y m).
- MÉTODO DEL MEDIO DEL CUADRADO: La clave es multiplicada por sí misma y los dígitos del medio (el número exacto depende del rango del índice) del cuadrado son utilizados como índice.
- MÉTODO DE DIVISIÓN: Se escoge un número m mayor que el número n de elementos a insertar, es decir, el array posee más posiciones que elementos a insertar. La función hash H se define por: H(X) = X % m o H(X) = (X % m) + 1 donde X % m indica el resto de la división de X por m. La segunda fórmula se usa cuando queremos que las direcciones hash vayan de 1 a m en vez de desde 0 hasta m-1. El mejor resultado del método de división se obtiene cuando m es primo (es decir, m no es divisible por ningún entero positivo distinto de 1 y m).
- La idea general de usar la clave para determinar la dirección del registro es una excelente idea, pero se debe modificar de forma que no se desperdicie tanto espacio. Esta modificación se lleva a cabo mediante una función que transforma una clave en un índice de una tabla y que se denomina función de Randomización o Hash. Si H es una función hash y X es un elemento a almacenar, entonces H(X) es la función hash del elemento y se corresponde con el índice donde se debe colocar X.
- TRUNCAMIENTO: Ignora parte de la clave y se utiliza la parte restante directamente como índice. Si las claves, por ejemplo, son enteros de 8 dígitos y la tabla de transformación tiene 100 posiciones, entonces el 1º, 2º y 5º dígitos desde la derecha pueden formar la función hash. Por ejemplo, 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.
- MÉTODO DE SUPERPOSICIÓN: Consiste en la división de la clave en diferentes partes y su combinación en un modo conveniente (a menudo utilizando suma o multiplicación) para obtener el índice. La clave X se divide en varias partes X1, X2, ..., Xn, donde cada una, con la única posible excepción de la última, tiene el mismo número de dígitos que la dirección especificada. A continuación, se suman todas las partes. En esta operación se desprecian los dígitos más significativos que se obtengan de arrastre o acarreo. Hay dos formas de conseguir la función hash mediante este método:
- TRUNCAMIENTO: Ignora parte de la clave y se utiliza la parte restante directamente como índice. Si las claves, por ejemplo, son enteros de 8 dígitos y la tabla de transformación tiene 100 posiciones, entonces el 1º, 2º y 5º dígitos desde la derecha pueden formar la función hash. Por ejemplo, 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.
- Existe un método que puede aumentar la velocidad de búsqueda donde los datos no necesitan estar ordenados y esencialmente es independiente del número n. Este método se conoce como transformación de claves o hashing. El hashing consiste en convertir el elemento almacenado (numérico o alfanumérico) en una dirección (índice) dentro del array.
- al igual que sucede con las operaciones de ordenador cuando se realizan operaciones de busqueda.
Information
- Description
- Mind Map on Resolución de colisiones Hash, created by Jose Cabrera on 04/12/2017.
- Created by
- Jose Cabrera
- Views
- 0
- Rating