Tablas hash

Búsqueda O(1) por cualquier llave: hashéala hacia un bucket. La estructura detrás de todo diccionario.

La idea, y el detalle

• Hashea la llave → entero → índice de bucket (mod capacidad)
• Vas directo al slot — sin escanear
• Las colisiones son inevitables; dos formas de manejarlas:
  • Encadenamiento: una lista por bucket
  • Direccionamiento abierto: avanzas al siguiente slot libre

Mira cómo las colisiones forman cadenas

3, 11 y 19 hashean todas al bucket 3 → una cadena de tres. La búsqueda solo recorre esa cadena corta.

El factor de carga es la perilla

$\alpha = n/m$ — elementos por bucket

• Encadenamiento: longitud de cadena esperada $\alpha$ → $O(1+\alpha)$
• Probing: probes ~ $\tfrac{1}{2}(1 + \tfrac{1}{1-\alpha})$
• Redimensiona para mantener α acotado → O(1). Peor caso O(n).

Desde cero vs librería

El direccionamiento abierto le gana al encadenamiento (cache). dict le gana a ambos (C). Todos O(1).

Conclusión

O(1) promedio en get/put/delete — siempre que el factor de carga se mantenga acotado. Aunque sin orden. Lo que sigue: la función hash en sí.