El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

El mòdul 4 va acabar amb una pregunta incòmoda: portem tot el curs escrivint tasca["id"] i tasca["prioritat"] donant per fet que aquesta consulta és instantània, però per què un dict troba una clau entre milers en temps constant, quan cercar en una llista és O(n)? Ja ho havíem mesurat a l'experiment amb timeit de la lliçó 01-02 —la corba del dict es mantenia gairebé plana mentre la de la list es disparava—, però mesurar no és entendre. En aquesta lliçó desvelem el truc: la taula hash, l'estructura que converteix una clau en la posició exacta on mirar. És una de les idees més influents de la informàtica, i entendre-la et canvia la manera de veure gairebé tot el programari que fas servir: memòries cau, bases de dades, índexs, el mateix intèrpret de Python. Construirem una versió mínima amb les nostres pròpies mans i descobrirem, honestament, on es trenca: aquest punt de trencament és el programa de la lliçó següent.

Contingut

La pregunta pendent i la pista que ja teníem
La idea central: convertir la clau en un índex
Dues analogies: les taquilles i l'índex del llibre
El TAD diccionari (o mapa)
La funció hash a alt nivell: hash() i l'operador %
Una taula hash mínima (i ingènua)
El problema inevitable: dues claus, una casella
TaskFlow: l'índex id→tasca
Els costos esperats

La pregunta pendent i la pista que ja teníem

Recapitulem què sabem sobre cercar:

En una list o LlistaEnllacada: cercar per id és O(n). Cal mirar element a element perquè la posició d'una tasca no guarda cap relació amb el seu id. Ho vam patir a 01-02 i ho vam tornar a signar al cercar de la LlistaEnllacada (02-02).
En un array per índex: accedir a la posició i és O(1). La lliçó 01-05 ens en va donar el motiu exacte: memòria contigua i la fórmula base + i × mida. El processador no cerca la casella i; en calcula l'adreça i hi va directe.
A 02-03 vam deixar caure una picada d'ullet: "algun dia tindrem un índex id→node que eviti recórrer la llista". Aquest dia és avui.

Ajunta les dues primeres peces i la pregunta s'esmola: l'array és rapidíssim, però només si li parles en el seu idioma, que són els índexs enters (0, 1, 2...). Nosaltres volem parlar en l'idioma del problema: ids, títols, noms d'usuari. La taula hash és, ni més ni menys, un traductor entre tots dos idiomes.

La idea central: convertir la clau en un índex

La idea cap en una frase: si tinguéssim una funció que converteix qualsevol clau en un índex d'array, cercar per clau costaria el mateix que accedir per índex: O(1).

El pla complet té tres passos:

Reservem un array de capacitat caselles (per exemple, 8).
Per guardar el parell (clau, valor), calculem index = funcio_hash(clau) % capacitat i deixem el parell a array[index].
Per recuperar el valor d'una clau, repetim exactament el mateix càlcul i mirem en aquella casella.

graph LR
    K["clau<br/>(p. ex. id 42)"] --> H["funcio_hash(clau)"]
    H --> M["% capacitat"]
    M --> I["índex<br/>(p. ex. 2)"]
    I --> A["array[2]<br/>base + 2 × mida → O(1)"]

Fixa't en el detall que ho sosté tot: guardar i cercar fan servir el mateix càlcul. No cal recordar on hem deixat cada cosa, perquè la mateixa clau és l'adreça (un cop traduïda). Per això les taules hash també s'anomenen estructures d'adreçament calculat: no cerquen, calculen.

Compara-ho amb el que feia la list: allà la posició d'una tasca depenia de l'ordre d'arribada, una informació arbitrària que no podem reconstruir a partir de l'id; d'aquí el O(n). Aquí la posició depèn només de la clau, i la clau la tenim sempre a la mà.

Dues analogies: les taquilles i l'índex del llibre

Les taquilles del gimnàs. Imagina 100 taquilles numerades del 0 al 99 i aquesta regla: "cada soci fa servir la taquilla de les dues últimes xifres del seu DNI". El soci amb DNI acabat en 42 deixa la motxilla a la taquilla 42 i, en tornar, va directe a la 42: no obre les 100 una a una. La regla és la funció hash; el número de taquilla, l'índex; i les dues últimes xifres són, literalment, un % 100. Observa també l'ombra de l'analogia: si dos socis tenen el DNI acabat en 42, hi ha conflicte de taquilla. Guarda't aquesta ombra, hi tornarem.

L'índex alfabètic d'un llibre. Per trobar "recursió" en un manual de 800 pàgines no llegeixes les 800 (cerca lineal): vas a l'índex del final, cerques per la lletra R i saltes a la pàgina exacta. L'índex és una estructura auxiliar, mantinguda a part, l'únic propòsit de la qual és traduir "terme" → "posició". Una taula hash és exactament això, però on la traducció no està escrita enlloc: es calcula al vol.

El TAD diccionari (o mapa)

Com vam fer amb piles i cues, separem el què del com (la distinció TAD vs implementació del mòdul 1). El TAD que volem s'anomena diccionari (també mapa o array associatiu): una col·lecció de parells clau → valor amb claus úniques. El seu contracte:

Operació	Què fa	En Python (`dict`)
`inserir(clau, valor)`	Associa el valor a la clau; si la clau existia, en reemplaça el valor	`d[clau] = valor`
`obtenir(clau)`	Retorna el valor associat a la clau	`d[clau]` / `d.get(clau)`
`esborrar(clau)`	Elimina el parell	`del d[clau]`
`conte(clau)`	Existeix la clau?	`clau in d`

Dues observacions importants:

El contracte no diu res de l'ordre. Un diccionari no promet "el primer", "l'últim" ni "el més prioritari"; promet accés per clau. És un contracte diferent del de pila, cua o llista — una altra eina, un altre problema.
Les claus són úniques: inserir dues vegades la mateixa clau no crea dues entrades, sinó que en sobreescriu el valor. Exactament el que volem en un índex de tasques: un id, una tasca.

La taula hash és la implementació estrella d'aquest TAD (no l'única: al mòdul 6 veurem que els arbres binaris de cerca també l'implementen, amb altres virtuts). El dict de Python és una taula hash; el set també, guardant només claus sense valor. Els farem servir "per dins" a 05-03; primer guanyem-nos el dret construint-ne una.

La funció hash a alt nivell: `hash()` i l'operador `%`

Una funció hash pren una clau de qualsevol tipus (enter, cadena, tupla...) i retorna un enter, sempre el mateix per a la mateixa clau. Python en porta una de sèrie:

print(hash(42))          # 42  → per a enters petits, hash(n) == n
print(hash("revisio"))   # p. ex. -8103770210014465245 (un enter enorme)
print(hash("revisio"))   # el MATEIX enter, dins de la mateixa execució
print(hash((1, "a")))    # les tuples també tenen hash

Per a enters petits, hash(n) és el mateix n: la traducció és trivial.
Per a cadenes i altres objectes, Python en barreja els bytes fins a produir un enter que sembla aleatori però és determinista. Com es cuina aquesta barreja —i què la fa bona o dolenta— és el cor de la lliçó 05-02; avui en tenim prou fent-la servir com a caixa negra, igual que vam fer amb heapq a 04-04.
Nota pràctica: el hash de les cadenes canvia entre execucions del programa (Python l'aleatoritza per seguretat). Dins d'una mateixa execució és estable, que és el que la taula necessita; però no imprimeixis hash("hola") avui i n'esperis el mateix número demà.

Aquest enter enorme (o negatiu) no serveix com a índex d'un array de 8 caselles. L'ajust final el fa l'operador mòdul, vell conegut de la CuaCircular (04-03): % capacitat plega qualsevol enter al rang 0..capacitat-1, i en Python el resultat mai no és negatiu si capacitat és positiva.

capacitat = 8
print(hash(42) % capacitat)         # 2 → l'id 42 viu a la casella 2
print(hash("revisio") % capacitat)  # algun valor entre 0 i 7

Una taula hash mínima (i ingènua)

Amb aquestes dues peces ja podem escriure una taula hash completa... si ens permetem una ingenuïtat que aviat sortirà cara. Cada casella de l'array guardarà un parell (clau, valor) o None si està lliure:

class TaulaHashIngenua:
    """Diccionari clau→valor sobre un array. ADVERTIMENT: ingènua a propòsit."""

    def __init__(self, capacitat=8):
        self.capacitat = capacitat
        self.caselles = [None] * capacitat   # array de caselles buides

    def _index(self, clau):
        """El traductor: de clau a posició de l'array."""
        return hash(clau) % self.capacitat

    def inserir(self, clau, valor):
        """Guarda el parell on digui el hash. Cost: O(1)."""
        self.caselles[self._index(clau)] = (clau, valor)

    def obtenir(self, clau):
        """Repeteix el mateix càlcul i mira aquella casella. Cost: O(1)."""
        parell = self.caselles[self._index(clau)]
        if parell is not None and parell[0] == clau:
            return parell[1]
        return None                          # casella buida o d'una altra clau

    def conte(self, clau):
        return self.obtenir(clau) is not None

Desgranem les decisions:

_index concentra la traducció en un sol lloc: hash() barreja, % capacitat plega. El guionet baix assenyala que és un mètode intern.
inserir no recorre res: calcula i escriu. obtenir no recorre res: calcula i llegeix. Ni un sol bucle — aquí hi ha el O(1).
A obtenir guardem també la clau dins del parell i la comprovem (parell[0] == clau). Paranoia? No: és la primera esquerda de la ingenuïtat traient el cap. Si en aquella casella hi hagués aterrat una altra clau, sense aquesta comprovació retornaríem un valor aliè sense avisar.

Provem-la amb tasques de TaskFlow:

t1 = {"id": 1, "titol": "Dissenyar el logo", "prioritat": 2, "estat": "pendent"}
t5 = {"id": 5, "titol": "Migrar la BD", "prioritat": 1, "estat": "en curs"}

taula = TaulaHashIngenua(capacitat=8)
taula.inserir(1, t1)     # hash(1) % 8 = 1 → casella 1
taula.inserir(5, t5)     # hash(5) % 8 = 5 → casella 5

print(taula.obtenir(5)["titol"])    # Migrar la BD  (directe a la casella 5)
print(taula.obtenir(3))             # None          (casella 3 buida: no existeix)

Funciona, i funciona en O(1). Gaudim-ne tres segons, perquè...

El problema inevitable: dues claus, una casella

...la capacitat és 8 i els ids possibles són infinits. Tard o d'hora, dues claus diferents produiran el mateix índex. Amb enters és fàcil provocar-ho: 3 % 8 i 11 % 8 donen tots dos 3.

t3 = {"id": 3, "titol": "Revisar els textos", "prioritat": 3, "estat": "pendent"}
t11 = {"id": 11, "titol": "Tancar l'esprint", "prioritat": 1, "estat": "pendent"}

taula.inserir(3, t3)      # hash(3) % 8 = 3  → casella 3
taula.inserir(11, t11)    # hash(11) % 8 = 3 → la MATEIXA casella 3!

print(taula.obtenir(11)["titol"])   # Tancar l'esprint   (bé...)
print(taula.obtenir(3))             # None               (la tasca 3 HA DESAPAREGUT!)

El que ha passat s'anomena col·lisió: dues claus diferents, un mateix índex. La nostra versió ingènua la gestiona de la pitjor manera possible: el segon inquilí aixafa el primer. La tasca 3 no està "difícil de trobar"; està perduda. I gràcies a la comprovació parell[0] == clau, almenys obtenir(3) retorna None en comptes de mentir-nos entregant la tasca 11 com si fos la 3 — sense aquesta comprovació, la fallada seria silenciosa, la pitjor mena de fallada.

Que quedi clar des d'avui: les col·lisions no són un cas rar que es pugui ignorar; són matemàticament inevitables (a 05-02 ho demostrarem amb el principi del colomar, i de passada veuràs que passen molt abans del que la intuïció suggereix). Tota taula hash real dedica la meitat de la seva enginyeria a conviure-hi. Com ho fa —encadenament, adreçament obert, redimensionament— és exactament el temari de la propera lliçó.

TaskFlow: l'índex id→tasca

Situem la peça a la nostra aplicació. Fins avui, TaskFlow guarda les seves tasques en estructures que preserven un ordre (la LlistaEnllacada del mòdul 2, les cues del mòdul 4), i cada vegada que algú pregunta per un id concret paguem un recorregut:

def cercar_per_id_lent(tasques, id_cercat):
    """Versió que hem fet servir (i patit) des del mòdul 1. Cost: O(n)."""
    for tasca in tasques:
        if tasca["id"] == id_cercat:
            return tasca
    return None

El pla del mòdul 5 és mantenir un índex: una taula hash id→tasca que conviu amb l'estructura principal, igual que l'índex del llibre conviu amb les seves pàgines:

class IndexTasques:
    """Índex id→tasca de TaskFlow. Versió 0.1: sobre la taula ingènua."""

    def __init__(self, capacitat=8):
        self.taula = TaulaHashIngenua(capacitat)

    def registrar(self, tasca):
        self.taula.inserir(tasca["id"], tasca)

    def cercar_per_id(self, id_tasca):
        return self.taula.obtenir(id_tasca)   # O(1): calcula i mira

El compte és senzill: amb 10.000 tasques, cercar_per_id_lent n'examina de mitjana 5.000; l'índex examina una casella. És l'explicació de l'experiment de 01-02 que devíem des de feia quatre mòduls. Però la versió 0.1 hereta la malaltia de la seva taula: registra les tasques 3 i 11 i una de les dues s'esfuma. Un gestor de tasques que perd tasques no és un gestor de tasques; abans de connectar aquest índex a la resta de TaskFlow necessitem la taula de debò de 05-02.

Els costos esperats

Tanquem amb la taula de costos que aquest mòdul promet i que 05-02 justificarà:

Operació	Taula hash (cas mitjà)	Taula hash (pitjor cas)	`list` / `LlistaEnllacada`
`inserir(clau, valor)`	O(1)	O(n)	O(1) al final
`obtenir(clau)`	O(1)	O(n)	O(n) cercar
`esborrar(clau)`	O(1)	O(n)	O(n)
`conte(clau)`	O(1)	O(n)	O(n)

Dues lectures honestes:

El titular és la columna del cas mitjà: accés per clau en O(1), la propietat que cap estructura dels mòduls 1–4 no podia oferir.
La lletra petita és el pitjor cas O(n): si el destí (o una funció hash dolenta) amuntega totes les claus a la mateixa casella, la taula degenera en una cerca lineal disfressada. Per què el cas mitjà és excel·lent malgrat això, i com es manté a ratlla el pitjor cas, és part del que 05-02 ha d'explicar.

Errors Comuns i Consells

Confondre el hash amb l'índex. Són dos passos diferents: hash(clau) produeix un enter qualsevol (enorme, potser negatiu); % capacitat el plega al rang de caselles. Barrejar-los porta a errors com fer servir hash(clau) directament d'índex (IndexError o, pitjor, índexs negatius que en Python funcionen accedint pel final... a la casella equivocada).
Oblidar guardar la clau al costat del valor. Si la casella només guarda el valor, no hi ha manera de detectar que la casella està ocupada per una altra clau, i obtenir retorna dades alienes sense error. Guardar el parell complet converteix una fallada silenciosa en una fallada visible.
Persistir hashos de cadenes. Com que el hash de str canvia entre execucions, guardar hash("etiqueta") en un fitxer o BD i reutilitzar-lo l'endemà trencarà el programa de maneres desconcertants. El hash viu i mor amb l'execució.
Assumir que el diccionari dona ordre. El seu contracte és accés per clau; si el teu problema necessita "el següent per ordre d'arribada" o "el més prioritari", les estructures dels mòduls 2–4 continuen sent les correctes. Índex i estructura ordenada solen conviure, no competir.
Consell: quan dubtis de per què la taula hash és O(1), torna mentalment a 01-05. Tot l'edifici descansa sobre base + i × mida; el hash només fabrica la i.

Exercicis

A mà, sense ordinador. Amb capacitat = 10 i sabent que per a enters hash(n) == n, calcula la casella dels ids 7, 23, 40, 17 i 100. Quins parells d'ids col·lisionen? Quins ids haurien col·lisionat amb capacitat = 8?
Completa la taula ingènua. Afegeix a TaulaHashIngenua el mètode esborrar(clau), que buidi la casella i retorni el valor esborrat (o None si la clau no hi era). Compte amb un matís: què ha de passar si a la casella hi viu una altra clau que va col·lisionar amb la cercada?
Caça la col·lisió. Escriu una funció primera_collisio(claus, capacitat) que rebi una llista d'ids enters i retorni la primera parella (a, b) que caigui a la mateixa casella, o None si no n'hi ha cap. Prova-la amb els ids [1, 9, 4, 12, 6] i capacitat = 8.

Solucions

Exercici 1. Amb capacitat = 10, la casella és l'última xifra: 7→7, 23→3, 40→0, 17→7, 100→0. Col·lisionen 7 i 17 (casella 7) i 40 i 100 (casella 0). Amb capacitat = 8: 7→7, 23→7, 40→0, 17→1, 100→4 — col·lisionen 7 i 23. Moralitat doble: la col·lisió depèn tant de les claus com de la capacitat, i canviar la capacitat ho recol·loca tot (idea que reapareixerà a 05-02 amb el nom de rehashing).

Exercici 2.

    def esborrar(self, clau):
        """Buida la casella de la clau i en retorna el valor, o None."""
        i = self._index(clau)
        parell = self.caselles[i]
        if parell is not None and parell[0] == clau:   # ocupada I per aquesta clau
            self.caselles[i] = None
            return parell[1]
        return None                               # buida, o d'una altra clau

El matís és a parell[0] == clau: si la casella l'ocupa una clau diferent (col·lisió), esborrar a cegues destruiria dades alienes. Amb la comprovació, esborrar(3) després de l'atropellament de la secció 7 retorna None — coherent, perquè la tasca 3 ja havia estat aixafada per la 11. La taula ingènua no ho pot fer millor; la de 05-02, sí.

Exercici 3.

def primera_collisio(claus, capacitat):
    ocupades = {}                       # casella → clau que l'ha ocupada primer
    for clau in claus:
        casella = hash(clau) % capacitat
        if casella in ocupades:
            return (ocupades[casella], clau)
        ocupades[casella] = clau
    return None

print(primera_collisio([1, 9, 4, 12, 6], 8))   # (1, 9): totes dues → casella 1

Amb [1, 9, 4, 12, 6] i capacitat 8: 1→1, 9→1 → col·lisió immediata (1, 9). Picada d'ullet autoreferent: hem fet servir un dict (una taula hash) per estudiar col·lisions de taules hash — amb una list d'ocupades, la funció seria O(n²).

Conclusió

Ja tens la idea que sosté mig programari modern: una funció hash converteix la clau en l'índex d'un array, i l'accés per posició de 01-05 fa la resta — cercar deixa de ser recórrer i passa a ser calcular. Hem formalitzat el TAD diccionari (inserir, obtenir, esborrar, conte), hem construït una TaulaHashIngenua que de debò respon en O(1), i hi hem muntat al damunt la versió 0.1 de l'índex id→tasca de TaskFlow... que perd tasques tan bon punt dos ids cauen a la mateixa casella. Aquesta és la frontera exacta entre la joguina i l'estructura real: les col·lisions. A la propera lliçó veurem què fa bona una funció hash (i mesurarem la diferència entre una de bona i una de dolenta), demostrarem que les col·lisions són inevitables i construirem la TaulaHash definitiva que les resol — reutilitzant, per cert, una vella amiga del mòdul 2: la LlistaEnllacada. Ens veiem a 05-02.

Introducció a les Taules Hash

Contingut

La pregunta pendent i la pista que ja teníem

La idea central: convertir la clau en un índex

Dues analogies: les taquilles i l'índex del llibre

El TAD diccionari (o mapa)

La funció hash a alt nivell: `hash()` i l'operador `%`

Una taula hash mínima (i ingènua)

El problema inevitable: dues claus, una casella

TaskFlow: l'índex id→tasca

Els costos esperats

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Introducció a les Taules Hash

Contingut

La pregunta pendent i la pista que ja teníem

La idea central: convertir la clau en un índex

Dues analogies: les taquilles i l'índex del llibre

El TAD diccionari (o mapa)

La funció hash a alt nivell: hash() i l'operador %

Una taula hash mínima (i ingènua)

El problema inevitable: dues claus, una casella

TaskFlow: l'índex id→tasca

Els costos esperats

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

La funció hash a alt nivell: `hash()` i l'operador `%`