Tablas Hash

Una tabla hash implementa un diccionario utilizando una función hash para mapear claves a posiciones de un array, lo que permite la inserción, eliminación y búsqueda en tiempo constante esperado cuando las colisiones se gestionan adecuadamente.

Definition

Una tabla hash es una estructura de datos que almacena pares clave-valor en un array, utilizando una función hash para calcular a partir de cada clave un índice en el array, con un esquema de resolución de colisiones para manejar claves distintas que se mapean al mismo índice.

Scope

Este tema cubre los diccionarios basados en hashing: las funciones hash y sus propiedades deseables, las estrategias de resolución de colisiones (encadenamiento separado y direccionamiento abierto), el factor de carga y el redimensionamiento, los marcos de hashing universal y perfecto que ofrecen garantías demostrables, y estructuras probabilísticas relacionadas como los filtros de Bloom. Se excluyen las estructuras de diccionario ordenadas, que se tratan en el apartado de árboles de búsqueda.

Core questions

• ¿Qué hace que una función hash sea buena y cómo se elige para distribuir las claves de manera uniforme?
• ¿Cómo se resuelven las colisiones mediante encadenamiento o direccionamiento abierto, y cómo afectan al costo?
• ¿Cómo rige el factor de carga el tiempo de operación esperado y cuándo desencadena el redimensionamiento?
• ¿Cómo proporcionan el hashing universal y el perfecto garantías de rendimiento demostrables?
• ¿Cuándo es preferible una estructura probabilística eficiente en espacio como un filtro de Bloom a una tabla exacta?

Key concepts

• función hash
• encadenamiento separado
• direccionamiento abierto
• factor de carga
• rehashing y redimensionamiento
• hashing universal
• hashing perfecto
• filtro de Bloom

Key theories

Hashing universal

Al elegir la función hash al azar de una familia cuidadosamente diseñada (universal), se puede garantizar un bajo número esperado de colisiones para cualquier conjunto fijo de claves, haciendo improbables los casos adversos en el peor de los escenarios.

Resolución de colisiones y factor de carga

El encadenamiento separado almacena las claves colisionantes en listas por ranura, mientras que el direccionamiento abierto sondea ranuras alternativas; el tiempo de operación esperado se rige por el factor de carga (entradas por ranura), y las tablas se redimensionan para mantenerlo acotado.

Clinical relevance

Las tablas hash se encuentran entre las estructuras de datos más utilizadas en la computación: implementan diccionarios y conjuntos en bibliotecas estándar, potencian la indexación de bases de datos y las cachés en memoria, soportan tablas de símbolos en compiladores y subyacen a la deduplicación y las pruebas de pertenencia. Los filtros de Bloom escalan las consultas de pertenencia en bases de datos y redes donde el almacenamiento exacto es inviable.

History

El hashing se originó en la década de 1950 con trabajos atribuidos a Hans Peter Luhn en IBM. Burton Bloom introdujo el filtro de Bloom, eficiente en espacio, en 1970. Carter y Wegman formalizaron el hashing universal y, posteriormente, el fuertemente universal a finales de los años 70 y principios de los 80, proporcionando al hashing su rigurosa base teórica.

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

¿Por qué las operaciones de la tabla hash se describen como O(1) esperado en lugar de O(1) garantizado?

Si muchas claves colisionan, las operaciones pueden degradarse hacia O(n). El tiempo constante se mantiene en expectativa bajo una buena función hash y un factor de carga acotado; el hashing universal hace improbable un caso malo, pero las garantías en el peor de los casos requieren hashing perfecto u otras técnicas.

¿Qué es un filtro de Bloom y en qué se diferencia de una tabla hash?

Un filtro de Bloom es una estructura probabilística compacta que prueba la pertenencia a un conjunto utilizando varias funciones hash sobre un array de bits. Puede producir falsos positivos pero nunca falsos negativos, y no almacena claves, intercambiando la exactitud por grandes ahorros de espacio en comparación con una tabla hash.