El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Diccionaris i Conjunts a la Pràctica

Següent ►
►

Ja saps construir una taula hash des de zero; ara toca fer servir les dues que Python porta de sèrie, afinades durant dècades: dict i set. Aquesta lliçó és el retorn de la inversió de 05-01 i 05-02 — cada regla "arbitrària" de Python (per què una llista no pot ser clau, per què in és rapidíssim en un set i lent en una list) es tornarà evident ara que coneixes la maquinària de sota. La segona meitat és pura pràctica: els patrons professionals amb diccionaris i conjunts — indexar, agrupar, comptar, invertir — aplicats a TaskFlow, que en aquesta lliçó estrena el seu índex per id definitiu i el seu primer cercador per etiquetes. Tancarem amb la pregunta més important per al teu criteri d'enginyer: quan un hash no és la resposta.

Contingut

  1. dict i set: taules hash de producció
  2. El requisit de les claus: ser hashables
  3. El contracte hash/__eq__
  4. Operacions i costos del dict
  5. Ordre d'inserció preservat
  6. Patrons TaskFlow amb dict
  7. set: el diccionari sense valors
  8. Àlgebra de conjunts per a etiquetes
  9. Quan NO fer servir una taula hash

dict i set: taules hash de producció

Els dos protagonistes, traduïts al vocabulari del mòdul:

  • dict: el TAD diccionari de 05-01 implementat com a taula hash d'adreçament obert (la segona família de 05-02, en una variant sofisticada), amb redimensionament automàtic en superar 2/3 de càrrega. Tot el que la nostra TaulaHash feia, més anys d'optimització en C.
  • set: la mateixa taula, guardant només claus, sense valors. La seva especialitat és una única pregunta contestada en O(1): hi és o no hi és?

Portem fent servir dict des de la primera tasca del curs; la diferència és que a partir d'avui saps què pagues i què reps amb cada operació — i per què existeixen les seves regles.

El requisit de les claus: ser hashables

Prova això:

index = {}
index[("backend", "urgent")] = "combinació vàlida"   # tupla: funciona
index[["backend", "urgent"]] = "?"                   # llista...
# TypeError: unhashable type: 'list'

Per què la tupla sí i la llista no? La resposta és al cor de 05-01: la clau és l'adreça. En inserir, la taula calcula hash(clau) i guarda el parell a la casella resultant; en cercar, repeteix el càlcul. Ara imagina que Python permetés llistes com a claus:

etiquetes = ["backend", "urgent"]
index[etiquetes] = tasca          # suposem casella 5
etiquetes.append("bloquejada")    # la llista CANVIA...
index[etiquetes]                  # ...el seu hash canviaria → miraria en UNA ALTRA casella

El parell continuaria físicament a la casella 5, però la cerca aniria a una altra: dada perduda sense cap error, la versió silenciosa del desastre de la TaulaHashIngenua. Per això Python exigeix que les claus siguin hashables: que tinguin un hash que no pugui canviar durant la seva vida. A la pràctica, això vol dir immutables:

Tipus Hashable? Motiu
int, float, str, bool, None Sí Immutables
tuple Sí, si tot el seu contingut ho és Immutable per fora
tuple amb una llista dins, p. ex. (1, [2]) No El seu interior pot mutar
list, dict, set No Mutables
frozenset Sí El set congelat, immutable

Dues conseqüències pràctiques immediates: per fer servir diversos valors com a clau composta, empaqueta'ls en una tupla ((id_projecte, id_tasca)); per fer servir un conjunt com a clau (ho farem amb etiquetes), congela'l amb frozenset.

El contracte hash/__eq__

Sota el capó, la hashabilitat es recolza en dos mètodes especials: __hash__ (el que crida la funció hash()) i __eq__ (el que crida ==). La taula els fa servir en tàndem, exactament com la nostra TaulaHash: el hash tria la cubeta, la igualtat identifica la clau dins d'ella (p[0] == clau). D'aquí el contracte sagrat:

Si a == b, aleshores hash(a) == hash(b).

Si dues claus "iguals" tinguessin hashos diferents, anirien a caselles diferents i la taula contindria duplicats impossibles de trobar. Python el compleix de fàbrica (hash(1) == hash(1.0) perquè 1 == 1.0), i només t'afecta si defineixes classes pròpies: si sobreescrius __eq__, Python desactiva el __hash__ heretat (el teu objecte deixa de ser hashable) precisament perquè no trenquis el contracte per accident; recuperar la hashabilitat exigeix definir un __hash__ coherent, normalment delegant en una tupla de camps immutables:

class RefTasca:
    """Referència lleugera a una tasca, usable com a clau de dict."""
    def __init__(self, id_tasca):
        self.id = id_tasca
    def __eq__(self, altra):
        return isinstance(altra, RefTasca) and self.id == altra.id
    def __hash__(self):
        return hash(self.id)          # mateix id → mateix hash: contracte complert

Per a TaskFlow no necessitem tant: els nostres dicts-tasca són mutables (canvien d'estat, de prioritat), així que mai no seran claus; la clau és el seu id, que és un enter immutable. Aquesta separació — dada mutable com a valor, identificador immutable com a clau — és el disseny canònic.

Operacions i costos del dict

La taula de referència, ara amb explicació coneguda (mitjanes; el pitjor cas O(n) de 05-02 existeix però l'aleatorització del hash el confina):

Operació Sintaxi Cost mitjà
Inserir / actualitzar d[k] = v O(1)
Obtenir (clau segura) d[k] O(1); KeyError si no hi és
Obtenir amb reserva d.get(k, defecte) O(1), sense excepció
Obtenir-o-crear d.setdefault(k, inicial) O(1)
Esborrar del d[k] / d.pop(k, defecte) O(1)
Pertinença k in d O(1)
Recórrer-ho tot for k, v in d.items() O(n)
Bolcar ordenat per clau sorted(d) O(n log n) — no és gratis!

Els dos accessos "amb xarxa" mereixen ser reflexos teus:

  • get per llegir sense por: d.get(id, None) en comptes d'un if id in d seguit de d[id] (que a més paga el hash dues vegades).
  • setdefault per al patró "si la clau no existeix, crea-la amb un valor inicial i torna-me'l": una crida en lloc de tres línies. El veurem en acció a l'índex invertit.

Ordre d'inserció preservat

Des de Python 3.7, el llenguatge garanteix que iterar un dict recorre les claus en l'ordre en què es van inserir (una propietat de la implementació compacta de CPython que va acabar elevada a contracte del llenguatge). Tres precisions per no malinterpretar-la:

  • És ordre d'inserció, no ordre per clau: {3: "c", 1: "a"} itera 3, després 1. Ningú no ordena res.
  • Actualitzar el valor d'una clau existent no la mou al final: conserva la seva posició original.
  • El set no ofereix aquesta garantia: el seu ordre d'iteració és indefinit. No escriguis codi que en depengui.

És una propietat molt còmoda — els registres de TaskFlow surten en ordre cronològic d'alta sense esforç — però compte a demanar-li més del que dona: "ordre d'arribada" no és "ordre alfabètic" ni "ordre per prioritat". Per a aquests, continua llegint fins a la secció 9.

Patrons TaskFlow amb dict

Dades de treball per a tota la secció — fixa't en els camps opcionals assignada_a i etiquetes que estrenem:

tasques = [
    {"id": 1, "titol": "Dissenyar el logo", "prioritat": 2, "estat": "pendent",
     "assignada_a": "anna", "etiquetes": ["disseny", "web"]},
    {"id": 2, "titol": "Migrar la BD", "prioritat": 1, "estat": "en curs",
     "assignada_a": "bruno", "etiquetes": ["backend", "urgent"]},
    {"id": 3, "titol": "Revisar els textos", "prioritat": 3, "estat": "pendent",
     "assignada_a": "anna", "etiquetes": ["web"]},
    {"id": 4, "titol": "Apedaçar l'API", "prioritat": 1, "estat": "pendent",
     "assignada_a": "bruno", "etiquetes": ["backend", "urgent", "api"]},
    {"id": 5, "titol": "Tancar l'esprint", "prioritat": 2, "estat": "feta",
     "assignada_a": "carla", "etiquetes": ["gestió"]},
]

Patró 1 — L'índex per id. L'IndexTasques de 05-01, versió definitiva, en una línia de comprensió de diccionari:

index = {t["id"]: t for t in tasques}

def cercar_per_id(id_tasca):
    return index.get(id_tasca)        # O(1), None si no existeix

print(cercar_per_id(4)["titol"])      # Apedaçar l'API — sense recórrer res

La picada d'ullet de 02-03 queda saldada del tot: si les tasques viuen en una LlistaEnllacada, l'índex pot apuntar id→node i donar accés O(1) a l'interior de la llista. Regla de manteniment: qui dona d'alta o de baixa una tasca ha de tocar les dues estructures (llista i índex); un índex dessincronitzat és pitjor que cap índex.

Patró 2 — Agrupar per estat amb defaultdict. Volem estat → llista de tasques. Amb dict pur, cada inserció exigeix comprovar si la clau existeix; collections.defaultdict elimina aquest soroll fabricant el valor inicial (aquí, list()) en el primer accés a cada clau nova:

from collections import defaultdict

per_estat = defaultdict(list)         # clau absent → crea [] automàticament
for t in tasques:
    per_estat[t["estat"]].append(t)

print([t["id"] for t in per_estat["pendent"]])      # [1, 3, 4]
print(len(per_estat["cancel·lada"]))                # 0 (i crea la clau: vegeu Errors)

Patró 3 — Comptar per prioritat amb Counter. Comptar ocurrències és tan comú que la biblioteca estàndard ho porta fet: Counter és un dict amb valor per defecte 0:

from collections import Counter

per_prioritat = Counter(t["prioritat"] for t in tasques)
print(per_prioritat)                  # Counter({2: 2, 1: 2, 3: 1})
print(per_prioritat[1])               # 2 → tasques de prioritat 1 (màxima); clau absent → 0, sense error
print(per_prioritat.most_common(1))   # [(2, 2)] — empat 2-2: retorna la clau vista primer

Patró 4 — L'índex invertit etiqueta→tasques. L'índex per id respon "dona'm la tasca 4"; el cercador de TaskFlow necessita l'invers: "dona'm les tasques amb l'etiqueta urgent". L'estructura s'anomena índex invertit — invertim la relació tasca→etiquetes per obtenir etiqueta→ids — i és, a petita escala, el mateix que fa un cercador web amb paraula→documents:

def construir_index_etiquetes(tasques):
    index_inv = {}
    for t in tasques:
        for etiqueta in t.get("etiquetes", []):        # get: el camp és opcional
            index_inv.setdefault(etiqueta, set()).add(t["id"])
    return index_inv

per_etiqueta = construir_index_etiquetes(tasques)
print(per_etiqueta["urgent"])         # {2, 4}
print(per_etiqueta["web"])            # {1, 3}

Tres detalls d'ofici: t.get("etiquetes", []) tolera tasques sense el camp; setdefault(etiqueta, set()) crea el conjunt la primera vegada que apareix cada etiqueta (el patró obtenir-o-crear promès); i el valor és un set d'ids, no una llista de tasques — cosa que habilita l'àlgebra de la secció 8. Construir-lo costa O(total d'etiquetes); consultar-lo, O(1).

set: el diccionari sense valors

Quan només importa la pertinença, el set és l'eina. La comparació que portem fent tot el curs, en la seva forma final:

ids_llista = [t["id"] for t in tasques]       # list
ids_set = {t["id"] for t in tasques}          # set (comprensió de conjunt)

999 in ids_llista   # O(n): recorre i compara una a una
999 in ids_set      # O(1): hash, casella, resposta

Operacions bàsiques: add(x), discard(x) (no protesta si falta; remove(x) llança KeyError), x in s, len(s) — totes O(1) de mitjana. Els seus elements, com les claus del dict, han de ser hashables: pots tenir un set d'ids o de tuples, no de llistes ni de dicts-tasca.

L'ús reflex és la deduplicació: len(ids) != len(set(ids)) detecta duplicats en O(n); set(ids) els elimina. I el patró "vistos" — un set acumulant el que ja s'ha processat per saltar-se repetits en O(1) — reapareixerà literalment al BFS de grafs del mòdul 7 sota el nom de visitats.

Àlgebra de conjunts per a etiquetes

La joia del set són les seves operacions binàries, heretades de la teoria de conjunts:

Operació Operador Mètode Resultat
Unió a | b a.union(b) En a, en b, o en tots dos
Intersecció a & b a.intersection(b) Només el que és comú
Diferència a - b a.difference(b) En a però no en b
Diferència simètrica a ^ b — Només en un dels dos
Subconjunt? a <= b a.issubset(b) Tot a és dins de b?

Sobre l'índex invertit de la secció 6, aquestes operacions són el llenguatge de consulta del cercador de TaskFlow:

urgents = per_etiqueta.get("urgent", set())
backend = per_etiqueta.get("backend", set())
web = per_etiqueta.get("web", set())

print(urgents & backend)    # {2, 4}  → urgent I backend (AND)
print(urgents | web)        # {1, 2, 3, 4}  → urgent O web (OR)
print(backend - web)        # {2, 4}  → backend però NO web

Cada consulta composta es resol en una línia i en temps proporcional a la mida dels conjunts implicats — no al total de tasques. I si un dia necessites la combinació d'etiquetes com a clau d'un dict (p. ex. per desar consultes a la memòria cau), recorda la secció 2: frozenset({"urgent", "backend"}) és hashable; el set normal, no.

Quan NO fer servir una taula hash

El criteri d'un bon enginyer no és saber fer servir el martell, sinó saber quan el cargol no és un clau. La taula hash compra el seu O(1) destruint l'ordre de les claus: la funció hash escampa a propòsit (uniformitat, 05-02), així que claus veïnes (ids 41, 42, 43) acaben en caselles sense cap relació. Conseqüències:

  • "Dona'm les tasques ordenades per id" → el hash no en sap res; toca sorted(index) a O(n log n), cada vegada.
  • "Dona'm les tasques amb id entre 100 i 200" (consulta de rang) → el hash no s'hi pot ni acostar: no existeix "la clau següent". Només queda provar les 101 claus una a una o recórrer-ho tot.
  • "Quin és l'id mínim pendent?" → recorregut complet O(n). (Per extreure mínims repetidament ja tens la cua de prioritat de 04-04.)
Necessitat Estructura adequada
Cercar UNA clau exacta Taula hash — imbatible: O(1)
Recórrer en ordre per clau Estructura ordenada (mòdul 6)
Consultes de rang (entre a i b) Estructura ordenada (mòdul 6)
Predecessor / successor d'una clau Estructura ordenada (mòdul 6)

Aquesta "estructura ordenada" que manté les claus navegables sense pagar una ordenació per consulta existeix, és jeràrquica, i és el programa del mòdul 6: els arbres. De moment, queda't amb la frontera: exacte → hash; ordenat o rang → una altra cosa.

Errors Comuns i Consells

  • Fer servir un dict-tasca (o qualsevol mutable) com a clau: TypeError immediat — i ara saps que és Python protegint-te de la dada perduda silenciosa de la secció 2. Clau = identificador immutable; dada mutable = valor.
  • d[k] a pèl amb claus que poden faltar: cada KeyError en producció sol delatar un get que hi hauria d'haver estat. Reserva d[k] per a quan l'absència sigui un error del programa.
  • L'accés curiós al defaultdict: consultar per_estat["cancel·lada"] per "mirar" crea la clau amb una llista buida (és la seva funció). Per consultar sense crear, fes servir "cancel·lada" in per_estat o .get. Un defaultdict que creix només per culpa de les consultes és un clàssic desconcertant.
  • Mutar un dict mentre el recorres: RuntimeError: dictionary changed size during iteration. Recull primer les claus a esborrar en una llista i esborra després, o itera sobre una còpia (list(d.items())).
  • Confiar en l'ordre d'un set: no en té. Si l'ordre de sortida importa, ordena explícitament (sorted(s)) o fes servir un dict amb valors dummy si el que vols és "conjunt amb ordre d'inserció".
  • Consell: memoritza el trio get / setdefault / defaultdict com a nivells del mateix patró — llegir amb reserva, llegir-o-crear puntual, crear-sempre massiu. Triar el nivell just fa el codi curt i llegible.

Exercicis

  1. Tribunal de claus. Sense executar-ho, veredicte (hashable o no) i motiu: (1, "a"), [1, 2], ("x", (2, 3)), (1, [2, 3]), frozenset({"a", "b"}), {"a", "b"}. Bonus: per què hash(True) == hash(1) no és un accident sinó una obligació?
  2. Tauler d'equip. Amb la llista tasques de la secció 6, construeix en una sola passada per les dades (més el que necessitis de Counter): (a) per_persona: assignada_a → llista de títols, amb defaultdict; (b) carrega: assignada_a → nombre de tasques no fetes, amb Counter; i (c) imprimeix la persona més carregada amb most_common.
  3. Cercador AND/NOT. Fent servir construir_index_etiquetes i l'índex per id, escriu cercar(amb, sense) que rebi dues llistes d'etiquetes i retorni els títols de les tasques que tenen totes les d'amb i cap de les de sense. cercar(["backend", "urgent"], ["api"]) ha de retornar ["Migrar la BD"]. Compte amb l'etiqueta inexistent.

Solucions

Exercici 1. (1, "a"): hashable — tupla d'immutables. [1, 2]: no — llista, mutable. ("x", (2, 3)): hashable — tuples niades, tot immutable. (1, [2, 3]): no — la tupla és immutable per fora, però conté una llista que pot mutar; el seu hash no seria estable (l'intent llança TypeError). frozenset({"a", "b"}): hashable — està congelat. {"a", "b"}: no — el set és mutable (per a clau, congela'l). Bonus: com que True == 1, el contracte de la secció 3 obliga que hash(True) == hash(1); si no, d[1] = "x" i d[True] mirarien en caselles diferents tot i ser claus "iguals".

Exercici 2.

from collections import defaultdict, Counter

per_persona = defaultdict(list)
carrega = Counter()
for t in tasques:                                  # una sola passada: O(n)
    per_persona[t["assignada_a"]].append(t["titol"])
    if t["estat"] != "feta":
        carrega[t["assignada_a"]] += 1             # Counter: la clau neix a 0

print(dict(per_persona))
# {'anna': ['Dissenyar el logo', 'Revisar els textos'],
#  'bruno': ['Migrar la BD', "Apedaçar l'API"], 'carla': ["Tancar l'esprint"]}
print(carrega)                                     # Counter({'anna': 2, 'bruno': 2})
persona, n = carrega.most_common(1)[0]
print(f"Més carregada: {persona} amb {n} tasques") # anna (o bruno: empat a 2)

La Carla no apareix a carrega: la seva única tasca està feta i Counter només crea claus en sumar — comportament correcte per a "càrrega pendent". Amb empats, most_common retorna primer la clau que va assolir abans el recompte (ordre d'inserció); si el desempat importés, caldria definir-lo explícitament.

Exercici 3.

def cercar(amb, sense):
    if not amb:
        return []
    # AND: intersecar els conjunts d'ids de totes les etiquetes requerides
    resultat = set(per_etiqueta.get(amb[0], set()))   # còpia: no mutar l'índex
    for etiqueta in amb[1:]:
        resultat &= per_etiqueta.get(etiqueta, set())
    # NOT: restar els ids de cada etiqueta exclosa
    for etiqueta in sense:
        resultat -= per_etiqueta.get(etiqueta, set())
    return [index[id_]["titol"] for id_ in sorted(resultat)]

print(cercar(["backend", "urgent"], ["api"]))    # ['Migrar la BD']
print(cercar(["backend", "inexistent"], []))     # [] — get(..., set()) salva la consulta

Anatomia: l'AND és una intersecció encadenada (cada &= només pot encongir el resultat); el NOT, una diferència; get(etiqueta, set()) converteix l'etiqueta desconeguda en conjunt buit en comptes de KeyError — amb una de requerida inexistent l'AND col·lapsa a buit, que és la resposta correcta. El pas final tradueix ids→títols amb l'índex per id: els dos índexs de la lliçó cooperant, l'invertit per filtrar i el directe per resoldre. El sorted final dona sortida reproduïble (els sets no prometen ordre).

Conclusió

Ja domines les taules hash "de debò": dict i set amb les seves regles explicades per dins — claus hashables perquè la clau és l'adreça i una adreça no pot mutar, el contracte hash/__eq__, costos O(1) de mitjana i ordre d'inserció garantit (que no és ordre per clau). En el terreny pràctic, TaskFlow ha guanyat la seva infraestructura de consulta: índex per id, agrupació per estat (defaultdict), estadístiques per prioritat (Counter), un índex invertit d'etiquetes i un llenguatge de consulta AND/OR/NOT gràcies a l'àlgebra de conjunts. I tens la frontera clara: el hash és imbatible amb la clau exacta, però no sap d'ordre ni de rangs. La propera lliçó no introdueix teoria nova: és pur entrenament — sis exercicis progressius on aquests patrons (i la TaulaHash de 05-02) resolen problemes clàssics d'entrevista i necessitats reals de TaskFlow. A escalfar mans: ens veiem a 05-04.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats