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

HOME

La TaulaHashIngenua de la lliçó anterior ens va donar el O(1)... i va perdre la tasca 3 tan bon punt l'id 11 va aterrar a la seva casella. Aquesta lliçó repara aquesta ferida en dos fronts. Primer, el front preventiu: entendre què fa bona una funció hash, perquè una funció ben dissenyada reparteix les claus i fa les col·lisions rares. Segon, el front curatiu: acceptar que rares no vol dir impossibles (ho demostrarem), i construir una taula que les resolgui sense perdre ni una dada. El resultat serà la TaulaHash definitiva del curs — amb encadenament, factor de càrrega i redimensionament —, la peça que TaskFlow necessitava perquè el seu índex id→tasca sigui fiable. És la lliçó més de "taller d'enginyeria" del mòdul: aquí es veu com es dissenya de debò una estructura de dades professional.

Contingut

Què li demanem a una funció hash
Hash d'enters i hash de cadenes: una de dolenta i una de bona
Mesurant la diferència: l'histograma
Les col·lisions són inevitables: el principi del colomar
Estratègia curativa 1: encadenament
La classe TaulaHash completa
Factor de càrrega i redimensionament (rehashing)
Estratègia curativa 2: adreçament obert
Encadenament vs adreçament obert
El pitjor cas O(n), explicat de debò

Què li demanem a una funció hash

Una funció hash h(clau) → enter és apta per a una taula si compleix tres propietats, per ordre d'importància:

Determinista: la mateixa clau produeix sempre el mateix hash (dins de la mateixa execució). És innegociable: guardar i cercar fan servir el mateix càlcul, així que si h canviés d'opinió, guardaríem en una casella i cercaríem en una altra. Una funció hash que faci servir random o l'hora actual no és una funció hash: és un generador de dades perdudes.
Uniforme: els hashos s'han de repartir per tot el rang com si fossin aleatoris, sense ser-ho. Si la funció afavoreix certes zones, les claus s'amunteguen en poques caselles i el O(1) de mitjana s'erosiona cap al O(n). Aquesta és la propietat difícil, i la que separa una funció bona d'una de dolenta.
Ràpida: s'executa a cada inserir, obtenir, esborrar i conte. Una funció hash de cost alt grava cada operació de la taula; O(longitud de la clau) és l'estàndard.

Hi ha una tensió estètica curiosa: volem un resultat que sembli caòtic (uniformitat) produït per un procés totalment predictible (determinisme). Dissenyar bones funcions hash és l'art de fabricar caos reproduïble.

Hash d'enters i hash de cadenes: una de dolenta i una de bona

Enters: el cas fàcil. hash(n) == n per a enters petits en Python, i sol bastar: els ids de TaskFlow (1, 2, 3...) es reparteixen perfectament amb % capacitat. La uniformitat l'hereta de les mateixes claus — amb la lletra petita que claus amb patró (tots els ids múltiples de 8, per exemple) poden ressonar malament amb certes capacitats; hi tornarem als consells.

Cadenes: aquí cal treballar. Una cadena és una seqüència de caràcters, i cada caràcter té un codi enter (ord("a") és 97). La temptació immediata és sumar-los:

def hash_suma(text):
    """Funció hash DOLENTA: suma els codis dels caràcters."""
    return sum(ord(c) for c in text)

És determinista i ràpida... però fatalment no uniforme, per un defecte estructural: la suma ignora l'ordre. hash_suma("amor") i hash_suma("roma") són idèntics — totes les permutacions de les mateixes lletres col·lisionen sempre, amb qualsevol capacitat. I hi ha un segon defecte més subtil: claus de longitud semblant produeixen sumes semblants, apilotades en una franja estreta de valors.

La solució clàssica és el hash polinòmic: recórrer els caràcters acumulant, però multiplicant l'acumulador per una constant a cada pas, de manera que la posició importi:

def hash_poli(text, base=31):
    """Funció hash raonable: polinòmica. h = c0·31^(n-1) + c1·31^(n-2) + ... + cn"""
    h = 0
    for c in text:
        h = (h * base + ord(c)) % (2 ** 32)   # acotem a 32 bits
    return h

Desgranem per què funciona:

Cada caràcter queda multiplicat per una potència diferent de 31 segons la seva posició: el primer caràcter pesa 31^(n-1), l'últim pesa 1. Reordenar els caràcters canvia el resultat — adeu al problema dels anagrames.
La multiplicació reiterada fa que un canvi en un sol caràcter es propagui i alteri el resultat de manera aparentment caòtica (el "caos reproduïble" que buscàvem). S'escullen bases primeres com 31 o 131 perquè barregen bé i no comparteixen factors amb capacitats habituals.
El % (2 ** 32) manté el número en 32 bits perquè no creixi sense límit; és un detall de contenció, no de disseny.

Aquest esquema no és cap joguina acadèmica: el hash de les cadenes en Java és exactament un polinòmic amb base 31. CPython fa servir una cosa més blindada (SipHash, amb l'aleatorització entre execucions que vam veure a 05-01), però la idea de fons — barrejar posició i valor — és la mateixa.

Mesurant la diferència: l'histograma

Les paraules "uniforme" i "apilotada" s'entenen millor veient-les. Prenem 100 claus amb estructura realista — els ids textuals "T-001" a "T-100" de les tasques de TaskFlow — i repartim-les en 20 cubetes amb cada funció, comptant quantes cauen a cadascuna:

claus = [f"T-{i:03d}" for i in range(1, 101)]     # T-001 .. T-100
CAPACITAT = 20

def histograma(funcio_hash, nom):
    cubetes = [0] * CAPACITAT
    for clau in claus:
        cubetes[funcio_hash(clau) % CAPACITAT] += 1
    print(f"--- {nom} ---")
    for i, n in enumerate(cubetes):
        print(f"{i:2} | {'#' * n} ({n})")

histograma(hash_suma, "hash_suma")
histograma(hash_poli, "hash_poli")

Sortida (retallada a les cubetes més il·lustratives):

--- hash_suma ---
 1 | ######### (9)
 2 | ########## (10)
 3 | ######### (9)
 ...
10 | ## (2)
11 | # (1)
12 |  (0)
13 |  (0)
...
--- hash_poli ---
 3 | ##### (5)
 4 | ###### (6)
 5 | ###### (6)
 6 | ##### (5)
 7 | ###### (6)
 ...

El veredicte és visual: amb hash_suma, el repartiment és una muntanya — cubetes amb 10 claus al costat de dues cubetes buides (les sumes d'aquestes claus es concentren en una franja, i el % 20 dibuixa aquesta franja a la taula). Amb hash_poli, totes les cubetes tenen entre 4 i 6 claus: pràcticament l'ideal de 100/20 = 5. I el defecte dels anagrames, negre sobre blanc:

print(hash_suma("T-012"), hash_suma("T-021"), hash_suma("T-102"))
# 276 276 276   ← col·lisió garantida, tant li fa la capacitat
print(hash_poli("T-012"), hash_poli("T-021"), hash_poli("T-102"))
# 78964056 78964086 78964986   ← tres valors diferents

En una taula amb hash_suma, cercar a la cubeta de 10 claus costa el doble que la mitjana ideal, i les cubetes buides són capacitat malbaratada. La uniformitat no és una virtut abstracta: és temps d'execució.

Les col·lisions són inevitables: el principi del colomar

I si dissenyéssim una funció hash tan bona que mai no col·lisionés? Impossible, i la demostració cap en dues línies. El principi del colomar: si n coloms es reparteixen en m nius i n > m, algun niu té almenys dos coloms. Amb claus i caselles: una taula de capacitat 64 amb 65 claus té, amb certesa matemàtica, almenys una col·lisió — tant li fa com d'exquisida sigui la funció. Les claus possibles (tots els enters, totes les cadenes) sempre superen infinitament les caselles disponibles.

I la realitat encara és més impacient: no cal omplir la taula per col·lisionar. És la paradoxa de l'aniversari: igual que en una sala amb només 23 persones ja hi ha un 50% de probabilitat de dos aniversaris coincidents (amb 365 "caselles"!), en una taula de capacitat 365 basta inserir unes 23 claus aleatòries perquè la primera col·lisió sigui més probable que improbable. Conclusió operativa: la pregunta mai no és "hi haurà col·lisions?" sinó "què farem quan arribin?". Hi ha dues grans respostes; anem amb la principal.

Estratègia curativa 1: encadenament

L'encadenament (chaining) dissol el problema canviant què és una casella: en comptes de lloc per a un parell, cada casella és una cubeta que conté una col·lecció de parells — tots els que el hash hi enviï. I quina estructura fer servir per a aquesta col·lecció de mida variable, amb inserció O(1) i esborrat per predicat? La tenim construïda i provada des del mòdul 2: la LlistaEnllacada.

graph LR
    subgraph "Array de cubetes (capacitat 8)"
        C0["0"] --> N
        C3["3"] --> A["(3, tasca 3)"] --> B["(11, tasca 11)"] --> N3["None"]
        C5["5"] --> D["(5, tasca 5)"] --> N5["None"]
    end
    N["None"]

La col·lisió de 05-01 deixa de ser una tragèdia: les claus 3 i 11 comparteixen cubeta, cadascuna amb el seu parell intacte. Cercar la clau 3 és: calcular la cubeta (O(1)) i recórrer la seva petita llista comparant claus (O(longitud de la cubeta)). Si la funció hash reparteix bé, aquesta longitud mitjana és n / capacitat — un número petit i controlat, com veurem amb el factor de càrrega.

La classe `TaulaHash` completa

Reutilitzem Node i LlistaEnllacada tal com van quedar a 02-02 (amb inserir_al_principi, cercar(condicio), esborrar(condicio) i iteració). Cada cubeta guardarà parells com a llistes [clau, valor] — mutables a propòsit, per poder actualitzar el valor sense tocar l'estructura:

class TaulaHash:
    """Diccionari clau→valor amb encadenament. La taula 'de debò' del curs."""

    FACTOR_CARREGA_MAX = 0.75        # llindar de redimensionament (secció 7)

    def __init__(self, capacitat=8):
        self.capacitat = capacitat
        self.cubetes = [LlistaEnllacada() for _ in range(capacitat)]
        self.n = 0                   # parells emmagatzemats

    def _index(self, clau):
        return hash(clau) % self.capacitat

    def inserir(self, clau, valor):
        """Insereix o actualitza. Cost mitjà: O(1)."""
        cubeta = self.cubetes[self._index(clau)]
        parell = cubeta.cercar(lambda p: p[0] == clau)
        if parell is not None:
            parell[1] = valor                        # la clau existia: actualitzar
            return
        cubeta.inserir_al_principi([clau, valor])    # nova: O(1) a la llista
        self.n += 1
        if self.n / self.capacitat > self.FACTOR_CARREGA_MAX:
            self._redimensionar()

    def obtenir(self, clau, per_defecte=None):
        """Cost mitjà: O(1) — una cubeta curta, no tota la taula."""
        parell = self.cubetes[self._index(clau)].cercar(lambda p: p[0] == clau)
        return parell[1] if parell is not None else per_defecte

    def conte(self, clau):
        parell = self.cubetes[self._index(clau)].cercar(lambda p: p[0] == clau)
        return parell is not None

    def esborrar(self, clau):
        """Esborra el parell i en retorna el valor, o None si no hi era."""
        parell = self.cubetes[self._index(clau)].esborrar(lambda p: p[0] == clau)
        if parell is None:
            return None
        self.n -= 1
        return parell[1]

    def __len__(self):
        return self.n

    def _redimensionar(self):
        """Duplica la capacitat i recol·loca TOTS els parells (rehashing)."""
        antigues = self.cubetes
        self.capacitat *= 2
        self.cubetes = [LlistaEnllacada() for _ in range(self.capacitat)]
        self.n = 0
        for cubeta in antigues:
            for clau, valor in cubeta:           # __iter__ de la LlistaEnllacada
                self.inserir(clau, valor)        # es recalcula amb la nova capacitat

Punts que mereixen lupa:

inserir primer cerca: si la clau ja existeix, actualitza el valor dins del parell (parell[1] = valor) i no toca self.n. Així es compleix el contracte de claus úniques del TAD. Només si és nova s'insereix — al principi de la cubeta, que a la LlistaEnllacada és O(1).
Totes les operacions repeteixen el mateix patró: traduir la clau a cubeta (O(1)) i delegar en la llista enllaçada del mòdul 2 (cercar o esborrar per predicat p[0] == clau). La feina O(n) que aquells mètodes feien sobre la llista sencera aquí es fa sobre una cubeta de 2 o 3 elements: mateix codi, un altre món.
Res no es perd mai: repeteix l'experiment fatal de 05-01 (inserir(3, t3), inserir(11, t11)) i veuràs que obtenir(3) i obtenir(11) retornen cadascun la seva tasca. La cubeta 3 simplement té dos parells.

Factor de càrrega i redimensionament (rehashing)

L'encadenament té un enemic lent: l'ocupació. Si en una taula de 8 cubetes inserim 800 parells, cada cubeta en tindrà ~100 — i cada obtenir recorrerà una llista de 100. Formalitzem-ho amb el factor de càrrega:

factor de càrrega = n / capacitat     (parells emmagatzemats / cubetes)

És exactament la longitud mitjana de cubeta. Amb factor 0.75, la cubeta mitjana té menys d'un parell; amb factor 100, la taula és una llista enllaçada disfressada. La defensa és vigilar-lo i, en superar un llindar (el nostre FACTOR_CARREGA_MAX = 0.75, semblant al de les taules reals), redimensionar: duplicar la capacitat i reinserir tots els parells.

Per què reinserir en comptes de copiar les cubetes? Perquè l'índex de cada clau depèn de la capacitat: hash(11) % 8 = 3, però hash(11) % 16 = 11. En canviar la capacitat, totes les adreces caduquen i cal recalcular-les — això és el rehashing (ja ho vas intuir a l'exercici 1 de 05-01). Dos matisos de cost:

Un redimensionament concret costa O(n): toca recol·locar-ho tot. L'operació d'inserció que el dispara és, puntualment, cara.
Però duplicar la capacitat (en comptes de sumar-hi una mica) espaia els redimensionaments exponencialment: per arribar a n parells s'han pagat redimensionaments de n/2 + n/4 + n/8 + ... < n reinsercions en total. Repartit entre les n insercions, surt a O(1) amortitzat per inserció — el mateix argument de l'array dinàmic que vam veure amb la list a 01-05. La simetria no és casual: la taula hash és un array per sota, i n'hereta els trucs.

Estratègia curativa 2: adreçament obert

La segona família de solucions prescindeix de llistes: tot viu dins del mateix array, un parell per casella. En l'adreçament obert, si la casella calculada està ocupada per una altra clau, es busca allotjament en una casella alternativa seguint una regla fixa. La regla més simple és el sondeig lineal (linear probing): provar la casella següent, i la següent, avançant circularment ((i + 1) % capacitat, l'aritmètica de la CuaCircular de 04-03) fins a trobar forat.

Inserir 11 quan la casella 3 està ocupada per la clau 3: provar la 4; lliure? el parell s'hi queda.
Cercar 11: calcular casella 3; hi ha un parell però d'una altra clau → seguir a la 4; clau 11 → trobada. La cerca recorre el mateix camí que la inserció i només es pot aturar en trobar la clau... o una casella buida (si hi fos, hauria aparegut abans del primer forat).
Esborrar, i aquí hi ha la trampa fina: si esborrem la clau 3 deixant la seva casella buida, la cerca de l'11 arribarà a la casella 3, veurà el forat i conclourà — erròniament — que l'11 no existeix, perquè el forat talla el camí. La solució estàndard és no buidar, sinó deixar-hi una marca especial (DELETED, una "làpida"): la cerca la travessa com si fos ocupada, la inserció la pot reutilitzar com a lliure.

No implementarem aquesta variant en detall (el concepte és l'exigible aquí; amb encadenament ja tenim la nostra taula de treball), però sí la seva idea-problema característica: l'agrupament primari. Les caselles ocupades consecutives formen "embussos" que creixen — cada col·lisió que cau a l'embús l'allarga, i allargar-lo fa més probable rebre la següent. Per això l'adreçament obert és més sensible al factor de càrrega i sol redimensionar abans (típicament cap a 0.5–0.7; el dict de CPython, que fa servir una variant sofisticada d'aquesta família, redimensiona a 2/3).

Encadenament vs adreçament obert

Criteri	Encadenament	Adreçament obert
On viuen els parells	En llistes fora de l'array (cubetes)	Dins del mateix array
Col·lisió	S'afegeix a la cubeta	Es sondeja una altra casella
Esborrat	Senzill (esborrar de la llista)	Delicat: exigeix marques `DELETED`
Factor de càrrega tolerable	Pot superar 1 (cubetes de diversos parells)	Ha de quedar per sota d'1, amb marge
Memòria	Punters extra per node	Compacta i amigable amb la memòria cau de la CPU
Risc característic	Cubetes llargues si el hash és dolent	Agrupament primari (embussos)
Qui la fa servir	Java `HashMap`, la nostra `TaulaHash`	CPython `dict`/`set` (variant avançada)

Totes dues famílies sostenen programari de producció; l'encadenament és més didàctic i robust davant càrregues altes, l'adreçament obert espreme millor la memòria moderna. Per al curs, la nostra TaulaHash d'encadenament és la referència.

El pitjor cas O(n), explicat de debò

Ja podem saldar el deute de la taula de costos de 05-01. El pitjor cas O(n) passa quan totes les claus acaben a la mateixa cubeta (o al mateix embús, en adreçament obert): la taula degenera en una llista enllaçada i cada operació la recorre sencera. Com s'hi arriba?

Funció hash dolenta: hash_suma amb claus anagramàtiques, o qualsevol funció que ressoni amb el patró de les claus. És el cas evitable — d'aquí la meitat "preventiva" d'aquesta lliçó.
Mala sort extrema: possible, astronòmicament improbable amb una funció uniforme. L'anàlisi probabilística diu que, amb hash uniforme i factor de càrrega acotat, la cubeta mitjana té O(1) parells — per això la mitjana O(1) és una promesa sòlida i no publicitat enganyosa.
Mala fe: un atacant que coneix la funció hash pot fabricar milers de claus col·lisionants i convertir cada petició en O(n) (atac hash flooding, un clàssic de denegació de servei contra servidors web). Aquesta és la raó que Python aleatoritzi el hash de les cadenes a cada execució (la nota de 05-01): sense conèixer la llavor, no es poden fabricar col·lisions a mida.

L'enginyeria completa, en una línia: bona funció hash + factor de càrrega vigilat + redimensionament = O(1) de mitjana amb pitjor cas O(n) confinat a l'improbable o el maliciós.

Errors Comuns i Consells

Oblidar el cas "la clau ja existeix" a inserir: afegir sense cercar primer crea claus duplicades dins de la cubeta; obtenir en trobarà una versió o una altra segons l'ordre i esborrar només n'eliminarà una. És l'error número u en implementar encadenament.
Redimensionar copiant cubetes en comptes de fer rehashing: si en ampliar copies les llistes tal qual, les claus queden en cubetes calculades amb la capacitat antiga i la taula "perd" parells (hi són, però _index ja no hi apunta). Tot redimensionament és una reinserció.
Actualitzar self.n a destemps: incrementar-lo en actualitzar un valor existent, o oblidar decrementar-lo en esborrar, corromp el factor de càrrega — i amb ell, la política de redimensionament. n compta parells, no crides.
En adreçament obert, esborrar deixant forat: trenca els camins de cerca de les claus que van sondejar per sobre. Si algun dia ho implementes, la làpida DELETED no és opcional.
Capacitats amb mal encaix: amb claus enteres amb patró (ids múltiples de 4) i capacitat potència de 2, % capacitat només mira els bits baixos i mitja taula queda buida. Les capacitats primeres (com el 13 o el 20 triats a consciència als exemples) o un hash que barregi bits eviten la ressonància. CPython ho resol barrejant; el nostre hash polinòmic, també.
Consell: quan una taula hash "vagi lenta", imprimeix el seu histograma d'ocupació com el de la secció 3. És la radiografia que distingeix en segons una funció hash malalta d'un factor de càrrega desbocat.

Exercicis

Diagnòstic d'anagrames. Sense executar codi: a quina cubeta cauran "T-123", "T-132", "T-213", "T-231", "T-312" i "T-321" amb hash_suma i capacitat 20? I garanteix hash_poli que no col·lisionin? Justifica totes dues respostes amb les propietats de la secció 1.
Sondeig lineal sobre paper. Taula d'adreçament obert, capacitat 7, claus enteres (hash(n) == n). Partint de la taula buida, traça casella a casella: inserir(10), inserir(17), inserir(3), esborrar(10) i després conte(17). Fes-ho dues vegades: esborrant amb forat (None) i esborrant amb làpida (DELETED). Què respon conte(17) en cada cas?
El factor de càrrega, mesurat. Afegeix a TaulaHash el mètode longitud_maxima_cubeta() que retorni la longitud de la cubeta més llarga (fes servir len(cubeta), que la LlistaEnllacada ja ofereix). Insereix els parells (i, i) per a i de 0 a 999 en dues taules de capacitat inicial 8: una de normal i una altra amb FACTOR_CARREGA_MAX = float("inf") (redimensionament desactivat). Compara capacitat, factor de càrrega i cubeta màxima de totes dues.

Solucions

Exercici 1. Les sis claus són permutacions dels mateixos caràcters, i la suma no depèn de l'ordre: totes tenen hash_suma = ord("T") + ord("-") + ord("1") + ord("2") + ord("3") = 84 + 45 + 49 + 50 + 51 = 279, per tant totes cauen a la cubeta 279 % 20 = 19. Sis claus, una cubeta: cercar qualsevol d'elles costa fins a 6 comparacions. Amb hash_poli l'ordre pesa (cada caràcter va multiplicat per una potència de 31 diferent), així que aquestes sis en concret reben hashos diferents — però no hi ha garantia general: el principi del colomar continua vigent i hash_poli també col·lisiona per a alguns parells de claus. La diferència és estadística, no absoluta: la funció bona fa les col·lisions rares i sense patró explotable; la dolenta les fabrica en sèrie.

Exercici 2. Traçat comú: inserir(10) → 10 % 7 = 3, casella 3 lliure → es queda a la 3. inserir(17) → 17 % 7 = 3, ocupada (10) → sondeig a la 4, lliure → 4. inserir(3) → 3 % 7 = 3, ocupada (10) → 4 ocupada (17) → 5 lliure → 5. Estat: [_, _, _, 10, 17, 3, _] — un embús de tres caselles nascut d'una sola col·lisió: agrupament primari en miniatura.

Esborrat amb forat: la casella 3 queda None. conte(17) → calcula 3, veu None, respon False: la clau 17 és a la casella 4, però el forat ha tallat el camí. La taula acaba de mentir.
Esborrat amb làpida: la casella 3 queda DELETED. conte(17) → casella 3 és làpida, la travessa → casella 4, clau 17 → respon True. La làpida preserva el camí; una inserció futura podrà reutilitzar la casella 3.

Exercici 3.

    def longitud_maxima_cubeta(self):
        return max(len(cubeta) for cubeta in self.cubetes)

normal = TaulaHash(capacitat=8)
congelada = TaulaHash(capacitat=8)
congelada.FACTOR_CARREGA_MAX = float("inf")     # desactiva el redimensionament

for i in range(1000):
    normal.inserir(i, i)
    congelada.inserir(i, i)

print(normal.capacitat, len(normal) / normal.capacitat,
      normal.longitud_maxima_cubeta())        # 2048  0.488  1
print(congelada.capacitat, len(congelada) / congelada.capacitat,
      congelada.longitud_maxima_cubeta())     # 8     125.0  125

La taula normal ha anat duplicant fins a capacitat 2048: factor de càrrega ~0.49 i cubetes de com a màxim 1 parell (claus enteres consecutives: repartiment perfecte) — obtenir és una comparació. La congelada manté 8 cubetes amb 125 parells cadascuna: cada obtenir recorre fins a 125 nodes. Mateixa funció hash, mateixes claus; l'única diferència és la política de redimensionament. El O(1) de mitjana no és cap regal de les matemàtiques: és factor de càrrega mantingut a ratlla.

Conclusió

Aquesta lliçó ha convertit la idea fràgil de 05-01 en una estructura de producció. En el front preventiu: una funció hash ha de ser determinista, uniforme i ràpida; el hash polinòmic aconsegueix la uniformitat fent que la posició de cada caràcter importi, i l'histograma ens ha donat una eina per veure la qualitat d'un hash. En el front curatiu: el principi del colomar garanteix col·lisions, l'encadenament les resol donant a cada cubeta una LlistaEnllacada (el mòdul 2 treballant per dins del mòdul 5), i el factor de càrrega amb redimensionament per duplicació manté les cubetes curtes a cost O(1) amortitzat — amb l'adreçament obert i les seves làpides com a família alternativa. Resultat: la TaulaHash amb inserir/obtenir/esborrar/conte en O(1) de mitjana, pitjor cas O(n) explicat i confinat. Ara bé: en el dia a dia no programaràs la teva taula — Python en porta dues de qualitat industrial, dict i set, i ara ja saps exactament què hi ha sota el seu capó. La propera lliçó els explota a fons: claus hashables, costos reals, i els patrons (agrupar, comptar, indexar) que faran volar TaskFlow. Ens veiem a 05-03.

Funcions Hash i Resolució de Col·lisions

Contingut

Què li demanem a una funció hash

Hash d'enters i hash de cadenes: una de dolenta i una de bona

Mesurant la diferència: l'histograma

Les col·lisions són inevitables: el principi del colomar

Estratègia curativa 1: encadenament

La classe `TaulaHash` completa

Factor de càrrega i redimensionament (rehashing)

Estratègia curativa 2: adreçament obert

Encadenament vs adreçament obert

El pitjor cas O(n), explicat de debò

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

Funcions Hash i Resolució de Col·lisions

Contingut

Què li demanem a una funció hash

Hash d'enters i hash de cadenes: una de dolenta i una de bona

Mesurant la diferència: l'histograma

Les col·lisions són inevitables: el principi del colomar

Estratègia curativa 1: encadenament

La classe TaulaHash completa

Factor de càrrega i redimensionament (rehashing)

Estratègia curativa 2: adreçament obert

Encadenament vs adreçament obert

El pitjor cas O(n), explicat de debò

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 classe `TaulaHash` completa