INVESTIGACIÓN DE FUNCIONES DE HASH Y SOLUCIÓN DE
COLISIONES
MATERIA: ESTRUCTURA DE DATOS
Grupo: B
Carrera: Ingeniería en sistemas computacionales
Fecha: 26/Enero/2024
, FUNCIONES HASH
Este método permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos
ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente
independiente del número de componentes del arreglo. Trabaja basándose en la función de
transformación (H) que convierte una clave en una dirección (índice) del arreglo.
Cuando se tienen claves que no se corresponden con los índices (como alfanuméricas), o cuando
las claves son valores numéricos muy grandes, debe utilizarse la función hash que permita
transformar la clave para obtener una dirección apropiada. Esta función debe de ser simple de
calcular y debe de asignar direcciones de la manera más uniforme posible.
Por todo lo mencionado, para trabajar con este método de búsqueda 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.
Función módulo o división
La función de este método es dividir el valor de la llave entre un número apropiado, y después
utilizar el residuo de la división como dirección relativa para el registro. Queda definida por la
siguiente fórmula:
Se recomienda que N sea el número primo inmediato inferior al número total de elementos.
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.
EJEMPLO:
Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones
generadas son las siguientes:
dirección = (7259%100) = 59
dirección = (9359%100) = 59
COLISIONES
MATERIA: ESTRUCTURA DE DATOS
Grupo: B
Carrera: Ingeniería en sistemas computacionales
Fecha: 26/Enero/2024
, FUNCIONES HASH
Este método permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos
ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente
independiente del número de componentes del arreglo. Trabaja basándose en la función de
transformación (H) que convierte una clave en una dirección (índice) del arreglo.
Cuando se tienen claves que no se corresponden con los índices (como alfanuméricas), o cuando
las claves son valores numéricos muy grandes, debe utilizarse la función hash que permita
transformar la clave para obtener una dirección apropiada. Esta función debe de ser simple de
calcular y debe de asignar direcciones de la manera más uniforme posible.
Por todo lo mencionado, para trabajar con este método de búsqueda 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.
Función módulo o división
La función de este método es dividir el valor de la llave entre un número apropiado, y después
utilizar el residuo de la división como dirección relativa para el registro. Queda definida por la
siguiente fórmula:
Se recomienda que N sea el número primo inmediato inferior al número total de elementos.
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.
EJEMPLO:
Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones
generadas son las siguientes:
dirección = (7259%100) = 59
dirección = (9359%100) = 59
