Scribd
Cargar
10 vistas9 páginas

Estructura y Funcionamiento de Tablas Hash

Las tablas hash son una estructura de datos que permite realizar búsquedas de elementos de forma eficiente. Utilizan una función hash que dispersa los elementos en la tabla y una función de modulo para determinar la posición de almacenamiento. Las colisiones, cuando dos elementos tienen el mismo código hash, pueden afectar el rendimiento. El factor de carga mide la carga de la tabla y el rehashing redistribuye los elementos cuando el factor supera cierto umbral para mantener la complejidad constante.

Cargado por

Herly Hinz Maldonado Chumbe
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
10 vistas9 páginas

Estructura y Funcionamiento de Tablas Hash

Las tablas hash son una estructura de datos que permite realizar búsquedas de elementos de forma eficiente. Utilizan una función hash que dispersa los elementos en la tabla y una función de modulo para determinar la posición de almacenamiento. Las colisiones, cuando dos elementos tienen el mismo código hash, pueden afectar el rendimiento. El factor de carga mide la carga de la tabla y el rehashing redistribuye los elementos cuando el factor supera cierto umbral para mantener la complejidad constante.

Cargado por

Herly Hinz Maldonado Chumbe
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Tablas Hash

Estructura de datos

Grupo 8
Integrantes

AQUINO CASTRO Matias Zuriel


PATIÑO REYNOSO Alberto Rolibert
PARI AGUILAR Luis
POMA GOCHE Karin Abigail
Universo de Objetos
Cuando tenemos una cantidad considerable de objetos y queremos realizar una búsqueda
entre ellos, surgen algunos inconvenientes.
En el caso de un array, con una cantidad considerable de elementos no podríamos saber
con exactitud el índice en el cual se encuentra el dato que buscamos.
Estas problemáticas se pueden solucionar con la implementación de una tabla hash, la
cual es una estructura de datos mas efizaces al momento de realizar la búsqueda de
elementos.
Función de dispersión
Esta función permite la dispersion de los elementos de la tabla mediante una función,
existen muchos tipos de funciones hash, pero la principal es la que utiliza aritmetica
modular.
Para esta función se define un
tamaño, que es el numero primo
siguiente a la cantidad de datos
a almacenar, y luego se le aplica
a la clave o al dato que se quiere
almacenar el modulo tamaño.
En el caso del ejemplo el tamaño es 7 por ende se aplica el mod 7 a cada una de las
claves a almacenar y estas se almacenan en la tabla
Colisiones
Las colisiones son un fenómeno muy frecuente en las Tablas Hash, ocurren cuando dos
o más objetos que se incluyen a una tabla tienen el mismo valor Hash.

¿Cómo afectan las colisiones al


funcionamiento de una tabla hash?
Una gran cantidad de colisiones
dentro de una tabla hash puede
causar que las operaciones dentro de
una tabla Hash incrementen su costo
de realización, por lo que la tabla se
hace ineficiente.
Factor de carga
El factor de carga es la proporción entre los elementos ingresados y su capacidad. Por
ejemplo, si ingresamos 6 elementos a una tabla con una capacidad para 10, entonces
su factor de carga será 60%.
La consideración del factor de carga
es muy importante para saber si la
tabla hash va a ser la optima al
momento de realizar acciones
como insertar, buscar y eliminar
objetos. En general, se considera
que una tabla hash con factor de
carga >75% es deficiente.
Rehashing
Rehashing es el proceso de recalcular el código hash de las entradas ya almacenadas
(pares clave-valor), para moverlas a otro hashmap de mayor tamaño cuando se
alcanza/se cruza el umbral.
¿Porqué usar rehashing?
El rehashing se realiza porque cada vez
que se inserta un nuevo par clave-valor
en el mapa, el factor de carga aumenta y
debido a ello la complejidad también
aumenta. Y si la complejidad aumenta,
nuestro HashMap no tendrá una
complejidad de tiempo O(1) constante.
¿Cómo usar rehashing?
Para cada nueva entrada en el mapa, comprueba el factor de carga.
Si el factor de carga es mayor que su valor umbral (por defecto 0,75 para HashMap),
entonces inicia el Rehash.
Para el Rehash, inicialice un nuevo array del doble del tamaño del anterior.
Copie todos los elementos en un nuevo array y conviértalo en el nuevo array de cubos.

¿Qué es el factor de carga en


HashMap?
El factor de carga en HashMap es básicamente
una medida que decide cuándo aumentar
exactamente el tamaño del HashMap para
mantener la misma complejidad temporal de
O(1).
Gracias

También podría gustarte