Dos claves distintas pueden transformarse en el mismo bucket — una colisión. Las tablas hash se mantienen en O(1) en promedio resolviendo colisiones y redimensionándose antes de que los buckets se llenen, controlado por el factor de carga.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| Operación | Promedio | Peor |
|---|---|---|
| búsqueda / inserción / eliminación | O(1) | O(n) |
| redimensionamiento único | — | O(n) |
| inserción (amortizada, con redimensionamiento) | O(1) | — |
Un redimensionamiento es O(n) pero ocurre raramente, por lo que se amortiza a O(1) por inserción.
Estos detalles internos explican por qué los mapas hash son rápidos en promedio pero pueden picos a O(n) — crucial para código sensible al rendimiento y defensas contra entrada adversaria (hash-flooding).
Comprender el factor de carga también explica los botones de ajuste de memoria/velocidad expuestos por bibliotecas reales.