Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Mapa mental

Resolución de colisiones Hash

Jose Cabrera Español

Mapa mental sobre Resolución de colisiones Hash: clasificación de los métodos, consideraciones y búsqueda en listas

Mapa mental: Resolución de colisiones Hash

Contenido del mapa

Resolución de colisiones Hash

  1. Clasificación de los métodos: • Reasignación • Arreglos anidados • Encadenamiento

  2. 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.

  3. 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.
        • 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:
      • al igual que sucede con las operaciones de ordenador cuando se realizan operaciones de busqueda.

Información

Descripción
Mapa Mental sobre Resolución de colisiones Hash, creado por Jose Cabrera el 04/12/2017.
Creado por
Jose Cabrera
Visitas
0
Valoración

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?