Tablas hash

Diagrama de estructuras de datos: arbol binario, lista enlazada y tabla hash. — Estructuras de datos fundamentales y analisis de complejidad algoritmica.

Mapa conceptual

Calcular, no buscar Una tabla hash responde «¿dónde guardé el valor de la clave k?» sin buscar: aplica una función a k para obtener DIRECTAMENTE la posición. Esa idea —calcular dónde está en vez de buscarlo— le da O(1) a los diccionarios, a las cachés y a los índices.

Cómo funciona

Una función hash toma la clave y la reduce a un número (un entero).
Ese número módulo la capacidad de la tabla da el ÍNDICE del «cubo» donde irá el valor.
Para leer, se repite el cálculo y se va directo a ese cubo.
Resultado: acceso promedio O(1), sin recorrer nada.

El problema: colisiones

Distintas claves pueden producir el mismo índice: eso es una colisión. Como el número de claves posibles es infinito y los cubos finitos, por el principio del palomar las colisiones SON obligatorias; el diseño no las elimina, las gestiona.

Encadenamiento: cada cubo guarda una mini-lista de los que cayeron ahí. Buscar recorre solo esa lista.
Sondeo abierto: si el cubo está ocupado, se prueban cubos vecinos según una regla hasta hallar uno libre.

Deja espacio o haz resizes La métrica que lo gobierna todo es el factor de carga α = elementos / cubos. Con α ≈ 1 y un buen hash, las listas de colisión cortan y el promedio es O(1); si dejas crecer α mucho, todo se degrada hacia un recorrido lineal.

El O(1) de los diccionarios es PROMEDIO, no garantía. Asumir «siempre O(1)» es el error clásico.
Escenario	Búsqueda	Cuándo ocurre
Promedio (buen hash, α bajo)	O(1)	distribución uniforme de claves
Peor caso	O(n)	todas las claves colisionan (hash adversario o pésimo)
Cubo con cadena larga	O(longitud de cadena)	α alto o cluster de colisiones

[Búsqueda: hash (plana) vs árbol (log) vs escaneo (lineal)]

Esta actividad interactiva ('Grafico interactivo') requiere el motor completo de Lumbre. El contenido estatico se muestra arriba; para la experiencia interactiva, visita la version online de este objeto.

Errores frecuentes

Asumir O(1) garantizado: una función hash que concentra claves (o un ataque deliberado, como el hash-flooding) degrada a O(n).
Olvidar que las claves deben ser INMUTABLES y hashables: mutar la clave de un elemento ya insertado rompe el cálculo del cubo y lo «pierde».
No dimensionar la tabla: α alto llena las cadenas; por eso se duplica el tamaño y se reinserta (rehash) al crecer.

Ejemplo resuelto

Tabla de 10 cubos, función hash = longitud de la clave mod 10.
Insertar «ana» (len 3) va al cubo 3; «luis» (len 4) al cubo 4; «eva» (len 3) al cubo 3.
«ana» y «eva» colisionan: en encadenamiento, el cubo 3 guarda una lista de dos.
Buscar «eva»: hash da 3, se recorre SOLO la lista de ese cubo (2 elementos) y se compara la clave.
Si el cubo 3 acumulara miles, la búsqueda ahí sería lineal: señal de un hash que no dispersa.

Cuando escribes dict o set en Python, o cuando una base de datos resuelve una clave, o una caché consulta una sesión, hay una tabla hash detrás. Entender colisiones y factor de carga te advierte cuándo esa magia de «constant time» deja de serlo.

Una tabla hash da acceso promedio O(1), pero ¿qué situación la degrada hacia O(n)?

Relaciona cada término de una tabla hash con su papel:

Anatomía del hash

función hash

clave a número

cubo/bucket

posición en la tabla

colisión

dos claves, mismo índice

encadenamiento

lista por cubo

sondeo abierto

probar cubos vecinos

factor de carga α

elementos / cubos

O(1)

promedio, no garantía

clave inmutable

requisito para hashar

Tablas hash (repaso formal)
Funciones hash, resolución de colisiones y análisis de costo.

Explica con tus palabras por qué un set en Python responde «¿está x?» muchísimo más rápido que una list para millones de elementos, y describe una situación en la que aun así el set se degradaría y perdería su ventaja.

VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.