Estructuras de datos · #8 de 11
Diccionarios
Mapeo clave-valor, métodos e internos
Por qué importa
Las tablas hash resuelven una enorme clase de problemas en tiempo O(1) promedio.
La idea
Un dict es una tabla de búsqueda rápida: clave → valor. Las claves deben ser hashables (es decir: cadenas, números, tuplas; no listas). Desde Python 3.7, los diccionarios recuerdan el orden de inserción.
Pruébalo
Construir, buscar, valores por defecto:
prices = {"apple": 1.0, "banana": 0.5}
prices["cherry"] = 2.5
print(prices)
# .get() returns a default instead of raising KeyError
print(prices.get("grape", 0.0))
# setdefault() inserts if missing, then returns the value
prices.setdefault("date", 3.0)
print(prices)
Conteo: el clásico modismo de “frecuencia”:
from collections import Counter
text = "mississippi"
counts = Counter(text)
print(counts)
print(counts.most_common(2))
Iteración: items() produce tuplas (clave, valor), perfectas para desempaquetar.
scores = {"Ada": 95, "Linus": 88, "Margaret": 99}
for name, score in scores.items():
print(f"{name:>10}: {score}")
# Dict comprehension
inverted = { score: name for name, score in scores.items() }
print(inverted)
Métodos principales de dict (debes conocerlos)
| Método | Qué hace | Ejemplo |
|---|---|---|
get(k, d) |
búsqueda segura | d.get("x", 0) |
keys() |
vista de las claves | list(d.keys()) |
values() |
vista de los valores | list(d.values()) |
items() |
vista de los pares | list(d.items()) |
update(...) |
fusionar/actualizar | d.update({"x":1}) |
pop(k) |
quitar una clave | d.pop("x") |
popitem() |
quitar el último par | d.popitem() |
setdefault(k, d) |
obtener o asignar | d.setdefault("x", 0) |
copy() |
copia superficial | d.copy() |
fromkeys(keys, v) |
inicializar | dict.fromkeys(keys, 0) |
Patrón de agrupación
setdefault convierte “agrupar elementos por una clave” en una sola línea:
groups = {}
for item in items:
groups.setdefault(item[0], []).append(item)Patrón Two Sum
El truco hash canónico de “recuerda lo que has visto”: O(n) en lugar de O(n²):
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = iVerificación rápida
- P: ¿Qué devuelve
dict.get(k)si la clave no existe? R:None(o el valor por defecto que indiques).
Mini ejercicios
- Cuenta los caracteres de una cadena.
- Encuentra el primer número repetido.
- Construye un diccionario palabra → conteo.
Buenas y malas prácticas
- Usa
in dpara comprobar las claves. - Prefiere
getpara el acceso opcional. - No mutes un diccionario mientras lo iteras.
- No uses claves no hashables (
list,dict,set).
Profundizando — cómo funcionan los diccionarios
Internos de la tabla hash
- Tabla hash: las claves se hashean a un índice de la tabla.
- Colisiones: distintas claves pueden mapear al mismo índice.
- Resolución: CPython usa direccionamiento abierto con sondeo (rápido en promedio).
- Factor de carga: a medida que la tabla se llena, Python la redimensiona para mantener rápidas las búsquedas.
Reglas de hashabilidad
- Hashables:
int,float,str,tuple(si sus elementos son hashables),frozenset. - No hashables:
list,dict,set.
Garantía de orden
- Python 3.7+ preserva el orden de inserción (una garantía oficial del lenguaje).
Errores comunes
- Error: Acceder a claves inexistentes con
[]. Solución: Usaget(). - Error: Sobrescribir valores sin querer. Solución: Inspecciona las claves antes de asignar.
- Error: Usar una lista como clave. Solución: Usa una tupla o
frozenset. - Error: Suponer que
dict.keys()es una lista. Solución: Envuélvela conlist(...)cuando haga falta.
Conclusiones clave
- Las claves deben ser hashables; los valores pueden ser cualquier cosa.
dict.get(k, default)evita elKeyError;setdefaultinserta si no existe.collections.Counteres lo primero a lo que recurrir para los conteos de frecuencia.- Las comprensiones de diccionario:
{k: v for ... if ...}reflejan las comprensiones de lista. get,set,in,popson ~O(1) en promedio; en el peor caso O(n) bajo muchas colisiones.