¿Qué es una tabla hash y cómo logra búsqueda O(1)?

Question

Accepted Answer

Una **tabla hash** (hash map) almacena pares **key → value** y ofrece inserción, búsqueda y eliminación promedio **O(1)**. Funciona pasando cada clave a través de una **función hash** que la asigna a un índice en un array subyacente (un "bucket").

## Cómo funciona

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Ejemplo

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Complejidad

| Operación | Promedio | Peor caso |
|---|---|---|
| insertar | O(1) | O(n) |
| búsqueda | O(1) | O(n) |
| eliminar | O(1) | O(n) |

El **peor caso** O(n) ocurre cuando muchas claves colisionan en el mismo bucket.

## Por qué es importante

- **Fortalezas:** acceso basado en clave extremadamente rápido; claves flexibles.
- **Debilidades:** sin ordenamiento de claves; memoria adicional; O(n) en peor caso; requiere una buena función hash.

Las tablas hash son probablemente la estructura más utilizada en la práctica — detrás de diccionarios, conjuntos, cachés, índices de bases de datos y deduplicación.

Reemplazar un escaneo lineal con una búsqueda hash es una de las formas más comunes de convertir un algoritmo O(n²) en O(n).