El módulo 4 terminó con una pregunta incómoda: llevamos todo el curso escribiendo tarea["id"] y tarea["prioridad"] dando por hecho que esa consulta es instantánea, pero ¿por qué un dict encuentra una clave entre miles en tiempo constante, cuando buscar en una lista es O(n)? Ya lo habíamos medido en el experimento con timeit de la lección 01-02 —la curva del dict se mantenía casi plana mientras la de la list se disparaba—, pero medir no es entender. En esta lección desvelamos el truco: la tabla hash, la estructura que convierte una clave en la posición exacta donde mirar. Es una de las ideas más influyentes de la informática, y entenderla te cambia la forma de ver casi todo el software que usas: cachés, bases de datos, índices, el propio intérprete de Python. Construiremos una versión mínima con nuestras propias manos y descubriremos, honestamente, dónde se rompe: ese punto de rotura es el programa de la siguiente lección.

1. La pregunta pendiente y la pista que ya teníamos
2. La idea central: convertir la clave en un índice
3. Dos analogías: los casilleros y el índice del libro
4. El TDA diccionario (o mapa)
5. La función hash a alto nivel: hash() y el operador %
6. Una tabla hash mínima (e ingenua)
7. El problema inevitable: dos claves, una casilla
8. TaskFlow: el índice id→tarea
9. Los costes esperados

Recapitulemos qué sabemos sobre buscar:

• En una list o ListaEnlazada: buscar por id es O(n). Hay que mirar elemento a elemento porque la posición de una tarea no guarda ninguna relación con su id. Lo sufrimos en 01-02 y lo volvimos a firmar en el buscar de la ListaEnlazada (02-02).
• En un array por índice: acceder a la posición i es O(1). La lección 01-05 nos dio el motivo exacto: memoria contigua y la fórmula base + i × tamaño. El procesador no busca la casilla i; calcula su dirección y va directo.
• En 02-03 dejamos caer un guiño: "algún día tendremos un índice id→nodo que evite recorrer la lista". Ese día es hoy.

Junta las dos primeras piezas y la pregunta se afila: el array es rapidísimo, pero solo si le hablas en su idioma, que son los índices enteros (0, 1, 2...). Nosotros queremos hablar en el idioma del problema: ids, títulos, nombres de usuario. La tabla hash es, ni más ni menos, un traductor entre ambos idiomas.

La idea cabe en una frase: si tuviéramos una función que convierte cualquier clave en un índice de array, buscar por clave costaría lo mismo que acceder por índice: O(1).

El plan completo tiene tres pasos:

1. Reservamos un array de capacidad casillas (por ejemplo, 8).
2. Para guardar el par (clave, valor), calculamos indice = funcion_hash(clave) % capacidad y dejamos el par en array[indice].
3. Para recuperar el valor de una clave, repetimos exactamente el mismo cálculo y miramos en esa casilla.

Fíjate en el detalle que lo sostiene todo: guardar y buscar usan el mismo cálculo. No hay que recordar dónde dejamos cada cosa, porque la propia clave es la dirección (una vez traducida). Por eso a las tablas hash también se las llama estructuras de direccionamiento calculado: no buscan, calculan.

Compáralo con lo que hacía la list: allí la posición de una tarea dependía del orden de llegada, una información arbitraria que no podemos reconstruir a partir del id; de ahí el O(n). Aquí la posición depende solo de la clave, y la clave la tenemos siempre en la mano.

Los casilleros del gimnasio. Imagina 100 casilleros numerados del 0 al 99 y esta regla: "cada socio usa el casillero de las dos últimas cifras de su DNI". El socio con DNI terminado en 42 deja su mochila en el casillero 42 y, al volver, va directo al 42: no abre los 100 uno a uno. La regla es la función hash; el número de casillero, el índice; y las dos últimas cifras son, literalmente, un % 100. Observa también la sombra de la analogía: si dos socios tienen DNI terminado en 42, hay conflicto de casillero. Guárdate esa sombra, volveremos a ella.

El índice alfabético de un libro. Para encontrar "recursión" en un manual de 800 páginas no lees las 800 (búsqueda lineal): vas al índice del final, buscas por la letra R y saltas a la página exacta. El índice es una estructura auxiliar, mantenida aparte, cuyo único propósito es traducir "término" → "posición". Una tabla hash es eso mismo, pero donde la traducción no está escrita en ninguna parte: se calcula al vuelo.

Como hicimos con pilas y colas, separemos el qué del cómo (la distinción TDA vs implementación del módulo 1). El TDA que queremos se llama diccionario (también mapa o array asociativo): una colección de pares clave → valor con claves únicas. Su contrato:

Dos observaciones importantes:

• El contrato no dice nada de orden. Un diccionario no promete "el primero", "el último" ni "el más prioritario"; promete acceso por clave. Es un contrato distinto al de pila, cola o lista — otra herramienta, otro problema.
• Las claves son únicas: insertar dos veces la misma clave no crea dos entradas, sino que sobrescribe el valor. Exactamente lo que queremos en un índice de tareas: un id, una tarea.

La tabla hash es la implementación estrella de este TDA (no la única: en el módulo 6 veremos que los árboles binarios de búsqueda también lo implementan, con otras virtudes). El dict de Python es una tabla hash; el set también, guardando solo claves sin valor. Los usaremos "por dentro" en 05-03; primero ganémonos el derecho construyendo una.

Una función hash toma una clave de cualquier tipo (entero, cadena, tupla...) y devuelve un entero, siempre el mismo para la misma clave. Python trae una de serie:

• Para enteros pequeños, hash(n) es el propio n: la traducción es trivial.
• Para cadenas y otros objetos, Python mezcla sus bytes hasta producir un entero que parece aleatorio pero es determinista. Cómo se cocina esa mezcla —y qué la hace buena o mala— es el corazón de la lección 05-02; hoy nos basta con usarla como caja negra, igual que hicimos con heapq en 04-04.
• Nota práctica: el hash de las cadenas cambia entre ejecuciones del programa (Python lo aleatoriza por seguridad). Dentro de una misma ejecución es estable, que es lo que la tabla necesita; pero no imprimas hash("hola") hoy y esperes el mismo número mañana.

Ese entero enorme (o negativo) no sirve como índice de un array de 8 casillas. El ajuste final lo hace el operador módulo, viejo conocido de la ColaCircular (04-03): % capacidad pliega cualquier entero al rango 0..capacidad-1, y en Python el resultado nunca es negativo si capacidad es positiva.

Con esas dos piezas ya podemos escribir una tabla hash completa... si nos permitimos una ingenuidad que enseguida saldrá cara. Cada casilla del array guardará un par (clave, valor) o None si está libre:

Desmenucemos las decisiones:

• _indice concentra la traducción en un solo sitio: hash() mezcla, % capacidad pliega. El guion bajo señala que es un método interno.
• insertar no recorre nada: calcula y escribe. obtener no recorre nada: calcula y lee. Ni un solo bucle — ahí está el O(1).
• En obtener guardamos también la clave dentro del par y la comprobamos (par[0] == clave). ¿Paranoia? No: es la primera grieta de la ingenuidad asomando. Si en esa casilla hubiera aterrizado otra clave, sin esta comprobación devolveríamos un valor ajeno sin avisar.

Probémosla con tareas de TaskFlow:

Funciona, y funciona en O(1). Disfrutémoslo tres segundos, porque...

...la capacidad es 8 y los ids posibles son infinitos. Tarde o temprano, dos claves distintas producirán el mismo índice. Con enteros es fácil provocarlo: 3 % 8 y 11 % 8 dan ambos 3.

Lo que ha pasado se llama colisión: dos claves distintas, un mismo índice. Nuestra versión ingenua la gestiona de la peor manera posible: el segundo inquilino machaca al primero. La tarea 3 no está "difícil de encontrar"; está perdida. Y gracias a la comprobación par[0] == clave, al menos obtener(3) devuelve None en vez de mentirnos entregando la tarea 11 como si fuera la 3 — sin ella, el fallo sería silencioso, la peor clase de fallo.

Que quede claro desde hoy: las colisiones no son un caso raro que se pueda ignorar; son matemáticamente inevitables (en 05-02 lo demostraremos con el principio del palomar, y de paso verás que ocurren mucho antes de lo que la intuición sugiere). Toda tabla hash real dedica la mitad de su ingeniería a convivir con ellas. Cómo lo hace —encadenamiento, direccionamiento abierto, redimensionado— es exactamente el temario de la próxima lección.

Situemos la pieza en nuestra aplicación. Hasta hoy, TaskFlow guarda sus tareas en estructuras que preservan un orden (la ListaEnlazada del módulo 2, las colas del módulo 4), y cada vez que alguien pregunta por un id concreto pagamos un recorrido:

El plan del módulo 5 es mantener un índice: una tabla hash id→tarea que convive con la estructura principal, igual que el índice del libro convive con sus páginas:

La cuenta es sencilla: con 10.000 tareas, buscar_por_id_lento examina de media 5.000; el índice examina una casilla. Es la explicación del experimento de 01-02 que llevábamos cuatro módulos debiendo. Pero la versión 0.1 hereda la enfermedad de su tabla: registra las tareas 3 y 11 y una de las dos se esfuma. Un gestor de tareas que pierde tareas no es un gestor de tareas; antes de conectar este índice al resto de TaskFlow necesitamos la tabla de verdad de 05-02.

Cerremos con la tabla de costes que este módulo promete y que 05-02 justificará:

Dos lecturas honestas:

• El titular es la columna del promedio: acceso por clave en O(1), la propiedad que ninguna estructura de los módulos 1–4 podía ofrecer.
• La letra pequeña es el peor caso O(n): si el destino (o una función hash mala) amontona todas las claves en la misma casilla, la tabla degenera en una búsqueda lineal disfrazada. Por qué el promedio es excelente pese a ello, y cómo se mantiene a raya el peor caso, es parte de lo que 05-02 tiene que explicar.

• Confundir el hash con el índice. Son dos pasos distintos: hash(clave) produce un entero cualquiera (enorme, quizá negativo); % capacidad lo pliega al rango de casillas. Mezclarlos lleva a errores como usar hash(clave) directamente de índice (IndexError o, peor, índices negativos que en Python funcionan accediendo por el final... en la casilla equivocada).
• Olvidar guardar la clave junto al valor. Si la casilla solo guarda el valor, no hay forma de detectar que la casilla está ocupada por otra clave, y obtener devuelve datos ajenos sin error. Guardar el par completo convierte un fallo silencioso en un fallo visible.
• Persistir hashes de cadenas. Como el hash de str cambia entre ejecuciones, guardar hash("etiqueta") en un fichero o BD y reutilizarlo al día siguiente romperá el programa de formas desconcertantes. El hash vive y muere con la ejecución.
• Asumir que el diccionario da orden. Su contrato es acceso por clave; si tu problema necesita "el siguiente por orden de llegada" o "el más prioritario", las estructuras de los módulos 2–4 siguen siendo las correctas. Índice y estructura ordenada suelen convivir, no competir.
• Consejo: cuando dudes de por qué la tabla hash es O(1), vuelve mentalmente a 01-05. Todo el edificio descansa sobre base + i × tamaño; el hash solo fabrica el i.

1. A mano, sin ordenador. Con capacidad = 10 y sabiendo que para enteros hash(n) == n, calcula la casilla de los ids 7, 23, 40, 17 y 100. ¿Qué pares de ids colisionan? ¿Qué ids habrían colisionado con capacidad = 8?
2. Completa la tabla ingenua. Añade a TablaHashIngenua el método borrar(clave), que vacíe la casilla y devuelva el valor borrado (o None si la clave no estaba). Cuidado con un matiz: ¿qué debe pasar si en la casilla vive otra clave que colisionó con la buscada?
3. Caza la colisión. Escribe una función primera_colision(claves, capacidad) que reciba una lista de ids enteros y devuelva la primera pareja (a, b) que caiga en la misma casilla, o None si no hay ninguna. Pruébala con los ids [1, 9, 4, 12, 6] y capacidad = 8.

Ejercicio 1. Con capacidad = 10, la casilla es la última cifra: 7→7, 23→3, 40→0, 17→7, 100→0. Colisionan 7 y 17 (casilla 7) y 40 y 100 (casilla 0). Con capacidad = 8: 7→7, 23→7, 40→0, 17→1, 100→4 — colisionan 7 y 23. Moraleja doble: la colisión depende tanto de las claves como de la capacidad, y cambiar la capacidad recoloca todo (idea que reaparecerá en 05-02 con el nombre de rehashing).

Ejercicio 2.

El matiz está en par[0] == clave: si la casilla la ocupa una clave distinta (colisión), borrar a ciegas destruiría datos ajenos. Con la comprobación, borrar(3) tras el atropello de la sección 7 devuelve None — coherente, porque la tarea 3 ya había sido machacada por la 11. La tabla ingenua no puede hacerlo mejor; la de 05-02, sí.

Ejercicio 3.

Con [1, 9, 4, 12, 6] y capacidad 8: 1→1, 9→1 → colisión inmediata (1, 9). Guiño autorreferente: hemos usado un dict (una tabla hash) para estudiar colisiones de tablas hash — con una list de ocupadas, la función sería O(n²).

Ya tienes la idea que sostiene medio software moderno: una función hash convierte la clave en el índice de un array, y el acceso por posición de 01-05 hace el resto — buscar deja de ser recorrer y pasa a ser calcular. Formalizamos el TDA diccionario (insertar, obtener, borrar, contiene), construimos una TablaHashIngenua que de verdad responde en O(1), y montamos sobre ella la versión 0.1 del índice id→tarea de TaskFlow... que pierde tareas en cuanto dos ids caen en la misma casilla. Esa es la frontera exacta entre el juguete y la estructura real: las colisiones. En la próxima lección veremos qué hace buena a una función hash (y mediremos la diferencia entre una buena y una mala), demostraremos que las colisiones son inevitables y construiremos la TablaHash definitiva que las resuelve — reutilizando, por cierto, una vieja amiga del módulo 2: la ListaEnlazada. Nos vemos en 05-02.