Tabele de Dispersie.Definiii i terminologie.

Tabelele de dispersie reprezint o modalitate foarte eficient de implementare a dicionarelor.

Acestea asigur complexitate constant O(1) n medie, pentru operaiile de inserare, tergere i cutare.

Dispersia nu presupune ordonarea informaiei pstrate. Operaiile cu arbori, care presupun ordonarea informaiei ntre elemente sunt mai puin eficiente (O(log n)).Dac:

structura de date (tabela de dispersie) e accesat prin valoarea unei chei n O(1) funcia care transform cheia ntr-o poziie ntr-un tabel are complexitate O(1)

atunci inserarea / tergerea / cutarea se vor face cu complexitate O(1)Dispersia implementeaz aceast idee folosind:

o tabel de dispersie o funcie de dispersie

Dac funcia de dispersie calculeaz pentru dou chei diferite aceeai valoare de dispersie, se produce o coliziune. Aceesul la cheile aflate n coliziune nu se mai face cu complexitate constant.

Pentru a reduce coliziunile se folosesc tabele de dimensiuni foarte mari. (eficiena temporal mai bun este anihilat de eficiena spaial mai proast).

Tabelele de dispersie pot fi deschise (sau externe) i nchise (sau interne).Funcii de dispersie.

Fie K o mulime de chei (ntregi, iruri de caractere, forme complexe de bii) i B o mulime de valori de dispersie (bini). Vom considera B={0,1,...,MAX-1}.Aplicaia hash : K B poart numele de funcie de dispersie, i asociaz mulimii cheilor o mulime de valori de dispersie.

Este de dorit ca aceast funcie s fie injectiv, adic la dou chei diferite k1k2 s corespund valori de dispersie diferite hash(k1)hash(k2), n caz contrar apare o coliziune.Funcia de dispersie trebuie s fie aleas astfel nct s asigure o dispersie ct mai uniform, care s minimizeze numrul de coliziuni.

In general numrul cheilor efectiv memorate este mult mai mic dect numrul total de chei posibile. Utilizarea adresrii directe, avnd complexitate O(1) ar conduce la folosirea neeficient a unor tablouri foarte mari care ar conine relativ puine elemente.

Cutarea n dicionar se face cu complexitate O(1) dac: se reprezint datele printr-un tabel de dispersie H se gsete o funcie de dispersie care mapeaz cheile n indici din tabelul de dispersie n

mod unic: k1k2 hash(k1)hash(k2) memoreaz elementul (k,i) n H[hash(k)]

1

Alegerea funciei de dispersie

Fie MAX dimensiunea tabelului de dispersie. Pentru valoarea de dispersie 0:MAX-1 se introduce tipul Index:typedef unsigned int Index;Pentru chei ntregi se folosesc:

1. Metoda mpririi : hash(k) = k % MAX n care MAX trebuie s fie un numr prim care s nu fie apropiat de o putere a lui 2.Index Hash(void *k, Index MAX){ return *(int*)k % nextprim(MAX);}2. Metoda nmulirii: reine o parte din biii prii fracionare a produsului k*A, n care A este o constant (Knuth recomand pentru A raportul de aur (5-1)/2) . De exemplu dac dimensiunea tabelei de dispersie este de 1024, este suficient un index de 16 bii, deci se calculeaz partea fracionar a lui A: 216*A = 40503 i se selecteaz cei mai semnificativi 10 bii, prin deplasare dreapta cu 6 poziii.Index Hash(void *k, Index MAX){ Index c=40503; return (c * *(int*)k) >> 6;}Dac cheia este un ir de caractere, typedef char *Index;se folosete una din funciile:

3. Adunarea codurilor caracterelor.Index Hash(void *k, Index MAX){ Index vd=0; while(*(char*)k != 0) vd += *(char*)k++; return ( vd % nextprim(MAX) );}4. Metoda sau-exclusiv.

Dintr-un tablou de numere generate aleator se selecteaz acele numere care au ca indici caracterele cheii i face sau-exclusiv ntre ele:unsigned char Rand8[256];Index Hash(void *k, Index MAX){ Index vd = 0; while(*(char*)k) vd = Rand8[vd ^ *(char*)k++]; return (vd % nextprim(MAX));}5. Metoda acumulrii polinomiale.

2

Se partiioneaz biii cheii n componente de lungime fix (8, 16 sau 32 de bii), fie acestea a0, a1,...,an-1.Se evalueaz polinomul p(z)=a0+a1z+...+an-1zn-1, ntr-un punct dat z (cu rezultate bune se ia z=32), ignornd depirile.

Se evalueaz polinomul cu schema lui Horner, n O(n).pi(z)=an-i-1+zpi-1(z), i=1:n-1Index Hash(void *k, Index MAX){ Index vd=0; while(*(char*)k != 0) vd = (vd

( )( ) N

11ppN/1pp

=

adic mulimea tuturor funciilor posibile este universal.

Putem da pentru orice funcie de dispersie semntura comun:Index hash(void *cheie, Index ind);Utilizatorul i poate defini propria funcie de dispersie, transmis ca pointer la funcie n lista de parametri a operaiilor primitive. n acest scop vom defini tipul pointer la funcia de dispersie:typedef Index (*PFD)(void *, Index);

Strategii de rezolvare a coliziunilor.

In cazul dispersiei deschise (cu nlnuire), coliziunile se rezolv prin punerea lor ntr-o list nlnuit asociat valorii de dispersie comune.Se creaz astfel un tablou de liste de coliziune.

n cazul dispersiei nchise: toate elementele se memoreaz n tabelul de dispersie nu se mai folosesc pointeri la producerea unei coliziuni se verific alte celule, pn cnd se gsete una

liber.Celulele verificate formeaz un lan de coliziune h0(x), h1(x),... undehi(x)=(hash(x)+F(i))%M cu F(0)=0Funcia F d strategia de rezolvare a coliziunii.ntruct toate datele se introduc n tabela de dispersie este necesar un tabel cu dimensiune mai mare.n general factorul de ncrcare ar trebui s fie sub 0.5 pentru dispersia nchis.

Dispersie deschis (sau nlnuit)

Dimensiunea tabloului listelor de coliziuni este numrul total de valori de dispersie MAX.Lista elementelor cu aceeasi valoare de dispersie

0

1

MAX-1

Inlantuirea coliziunilor in cazul dispersiei deschise

Operaiile specifice sunt:

TD TD_New (int m) -creaz un tabel de dispersie cu m liste de coliziune vide,

4

void TD_Insert (TD h, void *k, void *info, PFC comp, PFD hash) - insereaza perechea (k, info) n lista cu numrul hash(k). Compararea cheilor se face cu funcia comp.List_Iter TD_Search (TD h, void *k, PFC comp, PFD hash) - caut cheia k n lista de coliziune hash(k) i ntoarce adresa nodului din lista de coliziune care conine cheiavoid *TD_Remove (TD h, void *k, PFC comp, PFD hash) terge din lista de coliziune cu numrul hash(k) elementul cu cheia k. Funcia ntoarce adresa informaiei asociate cheii.

void *TD_Get(Lista L,List_Iter p) obine informaia asociat cheii din lista de coliziune, din nodul dat ca parametru.

int TD_Empty(TD h) test tabel de dispersie vidint TD_Size(TD h) numrul de elemente memorat n tabelul de dispersie.In cazul cel mai nefavorabil, complexitatea acestor operaii este O(n).In medie, complexitatea acestor operaii este O(1+), n care factorul de ncrcare = n/MAX, unde

n este numrul elementelor memorate MAX este dimensiunea tabelei de dispersie.

(n cazul dispersiei deschise poate fi supraunitar).Dispersia cu nlnuire separat are dezavantajul c necesit pointeri, alocare de memorie, deci este lent.

Interfa dispersie deschis.// Dispersie deschisa#ifndef TD_H#define TD_H#include list.htypedef int (*PFC)(void*, void*);typedef int (*PFD)(void*, int);struct TabDisp;typedef struct TabDisp *TD;TD TD_New (int m);List_Iter TD_Search (TD h, void *k, PFC comp, PFD hash);void TD_Insert (TD h, void *k, void *info, PFC comp, PFD hash); void *TD_Remove(TD h, void *k, PFC comp, PFD hash);void TD_Delete (TD *h);int TD_Empty (TD h);int TD_Size (TD h);#endif

Implementare dispersie deschis.

Pentru a pstra structura nodurilor TAD List, vom grupa asocierea (cheie, informaie) ntr-o structur i vom defini funcii pentru creerea acestei asocieri i pentru selectarea componentelor. Aceste funcii vor fi interne seciunii de implementare, deci inaccesibile utilizatorului.typedef struct per{

5

void *ch; //cheia elementului void *info; //informaia elementului} *pereche;//creaza perechea (cheie,informatie) intorcand adresa asocieriivoid *dublet(void *k, void *i){ pereche p =(pereche)malloc(sizeof(struct per)); p->ch = k; p->info = i; return p;}//selecteaza cheia din asocierea (cheie, informatie)void *sel_cheie(pereche p){ return p->ch; }//selecteaza informatia din asocierea (cheie, informatie)void *sel_info(pereche p){ return p->info; }Tabela de dispersie va conine dimensiunea max, numrul de elemente i tabloul listelor de coliziune.struct TabDisp{ int max; //dimensiune TD int n; //numar efectiv elemente din TD List *lcol; //tabloul de liste de coliziune};Iniializarea tabelei de dispersie presupune:

alocarea de memorie pentru structura tabel de dispersie i iniializarea ei alocarea de memorie pentru tabloul de liste de coliziune i iniializarea fiecrei liste ca

list vid

H

n

lcol

max

prim ultimn

TD TD_New (int m){ TD h; h=(TD)malloc(sizeof(struct TabDisp)); h->max=m; h->n=0; h->lcol=(Lista*)malloc(m*sizeof(Lista)); int i;

6

for(i=0; ilcol[i]=L_New(); return h;}Funcia TD_Search() ntoarce poziia nodului cu cheia k n lista de coliziune a elementelor cu aceeai valoare de dispersie sau NULL, dac elementul nu exist n tabela de dispersie.List_Iter TD_Search (TD h, void *k, PFC comp, PFD hash){ List_Iter p; p=L_Find(h->col[hash(k, h->max)], k, comp); return p;}Funcia TD_Insert()caut mai nti elementul cu cheia k n tabela de dispersie. Dac l gsete, el nu mai trebuie inserat, altfel se creaz un nod n care se pune cheia k i informaia asociat info, i se insereaz n lista selectat de funcia de dispersie.void TD_Insert (TD h, void *k, void *info, PFC comp, PFD hash){ List_Iter p; p=TD_Search (H, k, comp, hash); if(p) return; //exista, nu se mai pune void *d = dublet(k, info); L_Insert(h->lcol[hash(k,h->max)], p, d); h->n++;}Penru funcia TD_Remove() se caut mai nti elementul n tabela de dispersie, n lista corespunzoare cheii. Dac nu se gsete, nu avem ce terge, altfel se terge elementul din list i se scade numrul elementelor din list. void *TD_Remove (TD h, void *k, PFC comp, PFD hash){ List_Iter p; p=TD_Search (h, k, comp, hash); if(!p) return NULL; void *d=L_Remove(h->lcol[hash(k,h->max)],p); h->n--; return sel_info((struct per *)d);}void TD_Delete(TD *h){ int i; for(i=0; imax; i++) L_Delete(&(*h)->lcol[i]); free(*h); }

Dispersia nchis.

Dac funcia iniial de dispersie este h(x), notat h(x, 0), atunci celelalte funcii de dispersie se obin astfel:

1. Verificarea liniar adopt o funcie liniar de i, de obicei F(i)=i. Celulele alturate sunt verificate ciclic n cutarea unei celule libere. Dac tabelul este suficient de mare se va gsi o celul liber, dar timpul de cutare poate deveni foarte mare.

7

h(x,i)=(h(x)+i) % MAXLanul de coliziune poate avea dimensiunea maxim M; el se termin mai devreme, dac se ntlnete o celul marcat LIBER.Verificarea liniar favorizeaz creerea de blocuri vecine ocupate aglomerri (ciorchini) primare, care pot apare i pentru tablouri puin ocupate i degrada performanele.

2. Verificarea ptratic folosete F(i)=i2 i elimin aglomerrile primare. Dac dimensiunea tabloului este numr prim, un nou element poate fi ntotdeauna inserat dac tabelul este cel puin pe jumtate gol. h(x,i)=(h(x)+i2) % MAXMetoda verificrii ptratice genereaz cel mult o secven de MAX funcii de dispersie, dar produce aglomerri secundare

3. Dispersia dubl folosete o a doua funcie de dispersie h2(k) i trateaz coliziunile punnd elementul n prima celul liber dintre h(x,i)=(h(x)+ih2(x)) % MAX,

a doua funcie de dispersie h2(k) nu poate lua valoarea 0 dimensiunea tabelei trebuie s fie un numr prim, pentru a permite verificarea tuturor

celulelor a doua funcie de dispersie h2(k) este de forma:

h2(k)=q-k%q n care q este prim i q < M Metoda dispersiei duble genereaz cel mult o secven de MAX2 funcii de dispersie, dar nu produce nici aglomerri primare nici secundare. Factorul de ncrcare =n/MAX afecteaz performanele tabelei de dispersie.

Pentru verificarea liniar, funciile primitive sunt:TD_Search (h, k, comp, hash) caut cheia k mai nti n h[hash(k)] dac nu o gsete, continu cutarea n h[hash(k)+i] pn cnd:

o o gsete pe k - succeso d peste o poziie liber n tabelul de dispersie - eeco a efectuat MAX tentative - eec

TD_Remove (h, k, comp, hash) caut cheia k mai nti n H[hash(k)] dac gsete pe k, i pune marcajul STERS, fr a-l terge efectiv -succes. Dac nu-l gsete, continu cutare n h[hash(k)+i] pn cnd:

o l gsete n proba i i i pune marcajul STERS - succeso gsete o celul liber sau face MAX ncercri - eec

TD_Insert (h, k, i, comp, hash) caut cheia k mai nti n h[hash(k)] dac k este gsit, el nu va mai fi inserat dac poziia poziia cercetat are marcajul LIBER sau STERS este pus cheia n poziia

respectiv i marcajul pe OCUPAT dac poziia este OCUPAT se ncearc punerea elementului n poziia h[hash(k)+i]. Se

fac cel mult MAX tentative.Interfa dispersie nchis.

8

#ifndef _HT_probQ#define _HT_probQstruct TabDisp;typedef struct TabDisp *TD;typedef int (*PFC)(void*, void*);typedef int (*PFD)(void*, int);TD TD_New (int m);int TD_Search (TD h, void *k, PFC comp, PFD hash);void TD_Insert (TD h, void *k, void *inf, PFC comp, PFD hash);void TD_Remove (TD h, void *k, PFC comp, PFD hash);void TD_Delete (TD *h);int TD_Empty (TD h);int TD_Size (TD h);TD TD_ReDisp(TD h, PFC comp, PFD hash);#endif

Implementare dispersie nchis.

n cazul dispersiei nchise nu se face o tergere efectiv a elementelor din tabela de dispersie, deoarece aceasta este costisitoare, necesitnd deplasri de elemente, cu complexitate O(MAX).Poziiile din tabela de dispersie vor fi marcate cu valorile OCUPAT i LIBER. La tergerea unui element n tabela de dispersie, acesta nu va primi marcajul LIBER, deoarece s-ar ntrerupe lanul de valori aflate n coliziune, marcnd n mod fals sfritul acestora. Astfel dac am avea dou elemente n coliziune, ele ar fi memorate unul dup cellalt n tabela de dispersie. Dac se terge primul, marcndu-l ca LIBER, o cutare a celui de-al doilea element ar testa mai nti pe primul, ar gsi poziia LIBER i ar ajunge la concluzia greit c elementul cutat nu exist. Pentru tergere se va folosi o alt valoare a marcajului: STERS care permite continuarea cutrii.Un element din tabela de dispersie va fi descris aadar prin: cheie, valoare asociat i marcaj de ocupare.

Un grup de elemente aflate n coliziune poate avea lungimea cel mult MAX sau se poate termina mai repede printr-o celul marcat LIBER. Trecerea la urmtorul element din grup, n cazul verificrii ptratice se face adunnd la poziia iniial p pe i2 (sau adugnd 2*i-1 la poziia curent)enum Marcaj{OCUPAT, LIBER, STERS};struct Elem{ void *ch; void *info; enum Marcaj mark;};struct TabDisp{ int max; int n; struct Elem *TabCel;};TD TD_New(int m){ TD h; int i; h=(TD)malloc(sizeof(struct TabDisp)); h->max=nextPrim(m);

9

h->n=0; h->TabCel=(struct Elem*)malloc(sizeof(struct Elem)*h->max); for(i=0; imax; i++) h->TabCel[i].mark=LIBER; return h;}int TD_Search (TD h, void *k, PFC comp, PFD hash){ int p; int i=0; p=hash(k, h->max); while(i < h->max && h->TabCel[p].mark != LIBER && comp(h->TabCel[p].ch, k)!=0) { p += 2* ++i 1; if(p >= h->max) p -= h->max; } if(i > h->max || h->TabCel[p].mark==LIBER) return h->max; // esec - nu a gasit return p; // succes }void TD_Insert(TD h, void *k, void *inf, PFC comp, PFD hash){ int p = TD_Search (h, k, comp, hash); if(p < h->max) return; //cheia exista deja int i=0; while(i < h->max && h->TabCel[p].mark==OCUPAT) { p += 2* ++i 1; if(p >= h->max) p -= h->max; } assert(i < h->max); h->TabCel[p]->ch = k; h->TabCel[p]->info = inf; h->TabCel[p].mark = OCUPAT; h->n++;}void TD_Remove (TD h, void *k, PFC comp, PFD hash){ int p = TD_Search (H, k, comp, hash); if(p >= h->max) return; //nu exista cheia in TD int i=0; while(i < h->max && h->TabCel[p].mark!=LIBER && comp(h->TabCel[p].ch, k)!=0) { p += 2* ++i 1; if(p >= h->max) p -= h->max; } if(h->TabCel[p].mark==OCUPAT &&

10

comp(h->TabCel[p].ch, k)==0) { h->TabCel[p].mark = STERS; h->n--; }}

Redispersare.

Dac factorul de ncrcare al tabelei de dispersie depete 0.5, operaiile de inserare pot eua. n aceast situaie se prefer reconstruirea tabelei de dispersie cu dimensiune dublat. Schimbarea dimensiunii presupune recalcularea poziiei ocupate de elemente n noua tabel de dispersie. Operaia este scump, cu complexitate O(n), dar se face rar.TD TD_ReDisp(TD h, PFC comp, PFD hash){ struct Elem *TCv = h->TabCel; int n = h->n; int mv = h->max; h = TD_New (2*mv); h->n = n; int i; for(i=0; i

Probleme propuse.Dai coninutul tabelei de dispersie obinut prin inserarea caracterelor E X A M E N P A R T I A L, n aceast ordine ntr-un tabel, iniial vid cu M=5 liste, folosind nlnuire separat cu liste neordonate.

Se folosete funcia de dispersie 11 k mod M pentru a transforma litera cu numrul de ordine k din alfabet ntr-un indice n tabel , De exemplu, hash(I) = hash(9) = 99 % 5 = 4.

Dai coninutul tabelei de dispersie obinut prin inserarea caracterelor E X A M E N P A R T I A L, n aceast ordine ntr-un tabel, iniial vid de dimensiune M=16 , folosind verificarea linear.

Se folosete funcia de dispersie 11 k mod M pentru a transforma litera cu numrul de ordine k din alfabet ntr-un indice n tabel , De exemplu, hash(I) = hash(9) = 99 % 5 = 4.

Dai coninutul tabelei de dispersie obinut prin inserarea caracterelor E X A M E N P A R T I A L, n aceast ordine ntr-un tabel, iniial vid de dimensiune M=16 , folosind dispersia dubl. Use the hash function 11k mod M pentru proba iniial i funcia de dispersie secundar (k mod 3) + 1.

12