UC3M

El tamaño de una tabla hash es el otro parámetro que debe ser ajustado con cierto cuidado. Al igual que en el caso de la función de hash, se puede analizar cuales son las consecuencias extremas de la elección de un tamaño de tabla inadecuado. Por ejemplo, si el tamaño es demasiado pequeño, digamos 1, de nuevo la tabla se comporta como una lista encadenada. En cambio, si el tamaño es enorme, el malgasto de memoria es evidente, puesto que habrá un elevado número de posiciones cuya lista de colisiones está vacía.

Cuando se utilizan listas de colisión se suele utilizar una técnica basada en una “densidad”. Por densidad se entiende el valor al dividir el número de elementos en la tabla y su número de entradas. Si la función de hash produce una distribución uniforme de los elementos, un valor elevado de la densidad denota una longitud excesiva de las listas de colisiones. Un valor de densidad muy reducido denota una longitud muy corta de las cadenas de colisión y por tanto una infrautilización de memoria.

Las implementaciones más complejas de tablas hash incluyen dos umbrales para el valor de la densidad. Cada operación de inserción o borrado de un elemento consulta estos valores. Si la densidad supera el valor máximo, se reserva espacio para una tabla mayor, se borran todos los elementos de la tabla antigua y se insertan en la nueva (con densidad obviamente menor). Análogamente, si al borrar un elemento la densidad es menor que el umbral inferior, se realiza una operación similar pero con una nueva tabla más pequeña. De esta forma se consigue mantener de una forma transparente al exterior, el valor de la densidad en límites razonables. La operación de redimensionado de la tabla es cara en tiempo de CPU, pero se supone que las operaciones futuras de búsqueda, al encontrar listas de colisión de la dimensión adecuada, rentabilizan su ejecución.

Comprueba con estas preguntas si has entendido este documento.

Responde a las siguientes preguntas para ver si has entendido lo que se explica en este documento: