La tabla Hash
Integrantes
● Cajamalqui Davila Josemaria Piero
● Villena Ochoa yorshyo Artemio
● Vera Alavarado Carlos Sandino
¿Qué es la tabla Hash?
Una tabla hash o mapa hash es una
estructura de datos que asocia llaves o
claves con valores. La operación
principal que soporta de manera
eficiente es la búsqueda: permite el
acceso a los elementos (teléfono y
dirección, por ejemplo) almacenados a
partir de una clave generada usando el Funcionamiento:
nombre, número de cuenta o id.
Funciona transformando la clave con
una función hash en un hash, un
número que la tabla hash utiliza para
localizar el valor deseado.
Colisiones
Objetos “x” ; “y”
Estas se producen cuando
diferentes objetos indican al Donde:
mismo lugar o índice Hash x != y && hash(x)= hash(y)
Formas de Resolver una Colisión
Resolución mediante exploración Resolución mediante encadenamiento enlazado
Tratan de buscar una posición libre en la tabla para realizar la En cada posición de la tabla de Hash se
inserción del elemento. mantiene una Lista Enlazada en la que van
insertando los elementos cuyo valor Hash les
● Exploración lineal
asigna la misma posición.
Visita la siguiente casilla. Si está libre, realiza la
inserción. Si no está libre, pasa a visitar la siguiente
casilla.
● Exploración cuadrática
Visita la casilla i² posiciones más adelante de la que
causó la i-ésima colisión. Si no está libre, repite el
proceso hasta encontrar una que esté libre.
Hashing Enlazado
El Hashing Enlazado usa un vector de Listas Enlazadas.
Aquellos objetos que reciban un determinado valor de Hash, se insertan en lista enlazada
correspondiente.
Ejemplo de Uso de Tabla de Hash
Insertar los elementos {5, 10, 3, 15, 20, 19} en una Tabla Hash de tamaño 10 y con función hash:
Rehashing en una Tabla
Si el Factor de Carga ( grado de ocupación) de una Tabla de Hash es alto(>75%), el número de colisiones aumenta significativamente.
Solucion: Rehashing
Aumentar el tamaño de la tabla para reducir el factor de carga.
Ventajas:
Permite mantener un reducido factor de carga para que las principales operaciones (insertar, buscar, eliminar) se realicen en tiempo constante.
Inconvenientes:
Requiere construir un nuevo array e insertar nuevamente todos los datos.
Desventajas del uso de la Tabla Hash
● Para almacenar “N” datos se requiere que el tamaño de la Tabla Hash
sea M>>N, para poder reducir el número de colisiones.
● No es posible obtener el elemento mínimo ni máximo con un coste
temporal asintótico inferior al lineal con el número de entradas.
● No es posible obtener una secuencia ordenada de sus elementos con
un coste temporal asintótico lineal con el número de entradas.
Conclusiones
❏ Las Tablas Hash permiten que las operaciones de insertar, buscar y eliminar sea de
forma constante.
❖ Esto teniendo en cuenta que el factor de carga no sea muy excesivo para reducir la
probabilidad de colisión.
❏ Se tiene que elegir de forma correcta la función de Hash.
❖ Debe de ser fácilmente calculable, sin muchas operaciones por realizar.
❖ Debe de tener una buena distribución de valores entre todos los componentes de la tabla.
❏ Requisitos para la aplicación de la Tabla de Hash.
❖ Correcta digitación del código.
❖ Correcta digitación de la función.
❖ Tablas de símbolos de un compilador.
