FUNCTIA DE DISPERSIE

Pana acum am folosit metode de cautare, in care comparam o cheie ca

cheile existe intr-un tabel de date.
Vom construi o functie h cu ajutorul careia facem intai un calcul asupra
cheii K , astfel reducem cautarea doar in fisierul h(k)
Fie U multimea cheilor functia de dispersie este o functie
Spunem ca K disperseaza in fisierul h(K) si ca h(K) este valoarea functiei h inK.
Daca cheile sunt distribuite uniform in cele m fisiere cautarea se reduce de
la |U| la |U|/m.
. Doua chei distincte Ki si Kj care au aceeasi functie de dispersare,adica
h(Ki)=h(Kj) se spune ca au o coliziune si vom studia algoritmi efectivi pentru rezolvarea
coliziunilor
Deci ideea cautarii prin dispersare este aceea de a neglija anumite aspecte ale
cheii si sa utilizam aceasta informatie partiala, exprimata prin h(K),drept baza a
[Link] functiei de dispersare h(K) determina adresa de unde incepe cautarea
efectiva a cheii K.
Pentru a utiliza aceasta metoda,trebuie sa luam in considerare doua decizii
independente:mai intai trebuie sa alegem o functie de dispersare h(K) si apoi sa gasim o
metoda de rezolvare a coliziunilor.
Functia de dispersare trebuie desigur sa fie determinista,adica o aceeasi intrare K
trebuie sa determine intotdeauna aceeasi iesire h(K).
Daca |U|>m nu putem evita coliziunile,iar alegerea unei functii de dispersare bune
poate sa echilibreze numerele de chei care disperseaza la aceeasi adresa.
Exista doua metode simple pentru definirea functiilor de dispersare: prin impartire
si prin [Link] cheile sunt numere reale pozitive si subunitare,0 ≤ K <1,putem
defini functia de dispersare ca fiind partea intreaga din Km,adica f(K)=[Km].
In cazul cand cheile sunt numere naturale,definirea unei functii de dispersare h
prin impartire se poate face cu formula h(K)=K (mod m),unde de obicei m este un numar
prim.
In cazul definirii prin inmultire,mai intai se alege o constanta subunitara, 0<A<1
si se extrage partea fractionara a lui KA. Apoi se inmulteste acest numar cu m si se
considera partea intreaga a rezultatului,deci h(K)=[m(KA mod 1)],unde KA mod 1 este
partea fractionara a lui KA,adica KA-[KA].
Exista si metode pentru calcularea functiei de dispersare care se bazeaza pe teoria
algebrica a codurilor ; ideea este similara cu metoda impartirii expusa mai inainte,numai
ca impartirea se face cu un polinom modulo 2,in loc sa se imparta cu un [Link]
aceasta se considera m=2^s si se foloseste un polinom fixat de gradul s in variabila x :
P(x)=xs+ps-1xs-1+ … +p0.O cheie K se transforma in numar binar K=(kn-1…k1 k0) 2 si
acestuia i se asociaza polinomul K(x)=kn-1xn-1+ … +k1x+k0. Apoi se calculeaza restul
impartirii polinomului K(x) la polinomul P(x),adica K(x) mod P(x)= hs-1xs-1+ …+h1x+h0
folosind aritmetica polinomiala modulo [Link] final se defineste h(K)=(hs-1…h1h0)[Link]
polinomul P(x) este bine ales,aceasta functie de dispersare poate garanta evitarea
coliziunilor intre chei care difera pe putine pozitii ca numere [Link] exmplu,daca
n=15,s=10 si P(x)=x10+x8+x5+x4+x2+x+1,se poate arata ca h(K1) este diferit de h(K2) cand
K1si K2sunt chei distincte care difera pe mai putin de sapte biti.

1
Algoritm de cautare si insertie in tabele dispersate si inlantuite

In cazul rezolvarii coliziunilor prin inlantuire se depun toate inregistrarile ale caror chei
disperseaza la aceeasi adresa intr-o lista inlantuita. Subtabelul j (0 ≤ j ≤ m-1) contine un pointer
catre capul de lista al elementelor pentru care cheia K verifica h(K)=[Link] sunt n chei si m liste
inlantuite umplute uniform,lungimea medie a unei liste in care trebuie sa facem cautarea este
n/m,deci dispersarea poate reduce numarul de comparatii secventiale de chei cu un factor de
ordinul lui m.
Pentru a accesa o cheie x calculam mai intai h(x),apoi cautam cheia x in lista T(h(x)).Operatiile
de insertie sau stergere ale cheii x se implementeaza la fel ca aceste operatii in listele inlantuite
folosind legaturile de [Link] liste se pot pastra ca arbori binari de cautare
indexati,astfel incat sa putem regasi rapid o cheie sau putem folosi ideea de fisiere cu
autoorganizare.
Urmatorul algoritm propune o rezolvare posibila acestei probleme, permitand listelor inlantuite
ale inregistrarilor ale caror chei disperseaza la aceeasi adresa sa se [Link] acest algoritm
se lucreaza numai cu cheile inregistrarilor.
Se cauta intr-un tabel cu m noduri o cheie [Link] aceasta cheie nu este in tabel si tabelul nu este
plin,ea se insereaza.
Nodurile tabelului se noteaza cu TABLE[i] pentru 0 ≤ i ≤ m si ele sunt de doua feluri : libere si
[Link] nod ocupat contine campul KEY[i],campul LINK[i] si eventual si alte
[Link] foloseste o functie de dispersare h(K) si o variabila auxiliara R pentru a gasi
spatiile [Link] cand tabelul este vid avem R=m+[Link] ce se vor face insertii,TABLE[j]
este ocupat pentru toti j care verifica inegalitatile R ≤ j ≤ [Link] mai presupune ca TABLE[0] este
intotdeauna liber.

Algoritmul de cautare si insertie in tabele

dispersate si inlantuite.

1. i ← h(K)+1.
2. Daca pozitia TABLE[i] este libera,se merge la 6.
3. Daca K=KEY[i] algoritmul se termina cu succes.
4. Daca LINK(i) ≠ lambda,se face i ← LINK(i) si se
merge la pasul 3 .
5. (Cautarea a fost fara succes si se cauta sa se
insereze cheia K in tabel). Se descreste R pana cand

2
 se gaseste o valoare astfel incat TABLE[R] este
[Link] R=0,algoritmul se termina cu
depasire,altfel LINK[i] ← R,
i ← R.
6. (Se insereaza o noua cheie) Se marcheaza
TABLE[i] nod ocupat ; KEY[i] ← K si LINK[i] ←
lambda.

Complexitatea algoritmilor de dispersarea memoriei se evalueaza in urmatoarele ipoteze :

Functia de dispersare h:U → {0,1,…,m-1} distribuie universul in mod uniform,adica
pentru orice i,j din {0,1,…,m-1} avem |h-1 (i)|=|h-1(j)|;
Toate elementele din U sunt egal probabile ca argumente ale operatiilor luate in
considerare (cautari,inserari,suprimari de elemente),adica argumentul operatiei de ordin k
este egal cu x din U cu o probabilitate egala cu 1/|U|,adica probabilitatea P(h(x k)=i)=1/m
pentru orice 1 ≤ k ≤ n si 0 ≤ i ≤ [Link] tip de dispersare se numeste dispersare simpla
[Link] acestor ipoteze in aplicatiile practice este discutabila.

Dispersarea cu adresare deschisa

O alta cale de rezolvarea problemei coliziunilor este aceea de a renunta definitiv la

legaturi,cercetand diferitele pozitii ale tabelului una cate una si fie gasind cheia K sau
gasind o pozitie libera
Ideea de baza este formularea unei reguli dupa care pentru fiecare cheie K se determina
un sir de verificari,adica un sir de pozitii din tabel unde cheia K este [Link] se
intalneste o pozitie libera la cautarea cheii K,folosind sirul de verificari determinat de
K,ajungem la concluzia ca cheia K nu se afla in tabel,deoarece acelasi sir de verificari va
fi facut de fiecare data cand se cauta cheia K
Aceasta clasa generala de metode s-a numit adresare deschisa
Cea mai simpla schema de adresare deschisa se numeste numeste cautare liniara si
ea foloseste urmatorul sir ciclic de cautari : h(K),h(K)-1,…,0,m-1,m-2,…,h(K)+1.
Urmatorul algoritm cauta o cheie K intr-un tabel cu m noduri.
Daca cheia K nu se gaseste in tabel si tabelul nu este plin,atunci K se insereaza.
Nodurile tabelului se noteaza prin TABLE[i] pentru 0 ≤ i ≤ m-1 si ele sunt de doua
feluri : libere si ocupate.
Un nod ocupat are un camp KEY[i] care contine o cheie si posibil si alte campuri.
Pentru evidenta numarului de noduri ocupate din tabel se foloseste o variabila auxiliara
n ; ea se mareste cu o unitate de fiecare data cand se insereaza un nou nod.
Algoritmul foloseste o functie de dispersare h(K).
Algoritmul de cautare si insertie in tabele
dispersate deschise.

1. i ← h(K)
2. Daca TABLE[i] este liber se merge la 4.

3
 In caz contrar daca KEY[i]=K,algoritmul se
termina cu succes (s-a gasit cheia K).
3. i ← i-1 ;
daca i<0,atunci i ← i+m.
Se merge la 2.
4. Cautarea a fost fara succes.
Daca n=m-1, avem depasire si
nu mai este loc pentru inserarea cheii K (Algoritmul
considera tabelul plin cand n=m-1,nu cand n=m).
In caz contrar n ← n+1,se marcheaza TABLE[i] ocupat
si KEY[i]← K.

Experienta dincolo de cercetarea liniara arata ca algoritmul lucreaza(functioneaza) bine

pana in momentul in care tabelul devine complet; dar in eventualitatea in care procesul
incetineste, cu trasee lungi – cautarile din afara vor deveni din ce in ce mai frecvente.
Prin urmare, performantele cercetarii liniare degradeaza rapid cand n abordeaza m,
deoarece listele separate sunt combinate in liste lungi in cazul in care cautarea este lenta.
De fapt, atunci cand n = m-1, exista doar un singur spatiu liber in tabel, astfel incat
numarul mediu de probe intr-o cautare nereusita este (m+1)/2 .
O modalitate de a proteja impotriva problemei codul consecutive hash este de a utiliza
urmatoarea idee: in loc sa fie stabilite in ordine (l), implicand pozitii consecutive din
tabel, secventa de pozitii probate depinde de cheia ce urmeaza a fi inserata.
Pentru a determina care sunt pozitii de proba, putem extinde functia hash pentru a
include numarul probei. ( incepand de la zero ) ca o a doua intrare. Astfel, functia hash
devine :
h : U x { 0,1,…,m-1} → {0,1,…,m-1}
Cu o adresare directa, ne cere ca pentru fiecare cheie K, secventa de proba < h(K,0),
h(K,1),…,h(K,m-1) > sa fie o permutare de < 0,1,…,m-1>, astfel incat fiecare pozitie
hash din tabel sa fie in cele din urma considerata ca fiind un slot pentru o noua cheie,
astfel incat tabelul sa poata fi complet. Urmarind aceasta strategie pentru inserare si
cautare algoritmul L devine :

Algoritmul L1: ( Se deschide tabelul imprastiere cautare si inserare folosind doua

variabile ale functiei hash ).
1. Setati i ← 0
2. Setati j ← h(K,i)
3. Daca TABLE[j] este liber , du-te la 5.

Pe de alta parte, daca KEY[j]=K, algoritmul se termina cu success.

4. Daca i = m-1, algoritmul se termina cu o depasire a memoriei. Pe de alta parte,
setati i ←i+1 si mergi inapoi la pasul 2.
5. Marcheaza TABLE[j] ca fiind ocupat si seteaza KEY[j] ← K. (Cheia K a fost
inserata in tabel ).

4
Deoarece algoritmul pentru cautarea cheii K propune aceeasi ordine de sloturi in care
algoritmul de insertie este examinat cand cheia K va fi inserata(introdusa); cautarea se
poate finaliza(fara succes) cand se constata un slot liber, deoarece K ar trebui introdus
acolo si nu mai tarziu in secventa sa de proba. ( Retineti ca acest argument presupune ca
aceste chei nu sunt sterse din tabelul hash).
Stergerea unui tabel hash cu adresare directa este dificil. Cand stergem o cheie din
slotul i, pur si simplu nu putem marca acel slot ca fiind unul gol(liber). Acest lucru ar
putea face imposibil de a regasi orice cheie K a carei inserare a fost probate in slotul i si
am regasit ca este ocupat. Din acest motiv, inlantuirea este mai frecvent selectata ca fiind
o tehnica de rezolutie de coliziune atunci cand cheile trebuiesc sterse.
Trei tehnici sunt utilizate pentru a calcula secventele de proba, necesare pentru adresarea
directa: cercetarea liniara, cercetare cuadrata si dubla insertie. Aceste tehnici garanteaza
ca:

< h(K,0), h(K,1),…,h(K,m-1) > este o permutare a <0,1,…,m-1 > pt. fiecare(orice)
cheie K

Cercetarea liniara.

Avand in vedere o functie hash obisnuita h’:U →{0,1,…,m-1}, metoda de cercetare

liniara utilizeaza functia hash :

h(K,i) = h’(K)+i (mod m ) pentru i=0,1,…,m-1 . Retineti ca (l) corespunde lui h(K,i) =
h’(K) – i (mod m).
Dandu-i cheii K, primul slot probat este :
T[h’(K)]

Ni se da slotul de proba T[h’(K)+1] si asa mai departe pana la slotul T[m-1]. Apoi vom
incheia in jurul sloturilor T[0], T[1],…, pana cand in cele din urma vom ajunge la slotul
de proba T[h’(K)-1].
Cautarea liniara este usor de implementat, insa aceasta sufera de o problema numita :
cluster primar. Seriile lungi de sloturi construite ocupate, cresc durata medie de cautare.

Ecuatia de gradul 2 probeaza folosirea unei functii de dispersare (hash) de forma

, unde h’ este o functie hash auxiliara,c1,c2 0 sunt
constante auxiliare, si i=0,1,2,....,m-1.
Pozitia initiala cautata este T[h’(K)] , urmatoarele pozitii cautate sunt echilibrate de
valorile ce depind in ec de gradul 2 la cautarea numarul i. aceasta metoda functioneaza
mai bine decat cautarea liniara, dar ptr a utiliza tot tabelul de dispersie, valorile c 1,c2 si m
sunt constante.

5
De asemenea, daca doua chei au aceeasi pozitie cautata, atunci secventele lor de cautare
sunt aceleasi, intre timp h(k1,0)= h(k2,0) implica h(k1,0)= h(k2,0) , pentru orice i.
Aceasta duce la o forma mai usoara de cluster , numita cluster secundar.
Ca la cautarea liniara, cautarea initiala determina secventa de intrare, deci sunt folosite
doar m secvente de cautare.
Un mod de a selecta parametrii c1 si c2 este de a impune ca c1i+c2i2=1+2+...+i, adica
c1i+c2i2= rezulta ca .

Lema 1. Daca m=2s pentru un intreg si , unde h’(k)

este o functie auxiliara de dispersie, atunci pentru orice cheie k,
<h(k,0),h(k,1),...,h(k,m-1)> este o permutare a <0,1…m-1>.
Demonstratie
Trebuie sa demonstram ca pentru orice i=0,1,….m-1 toate valorile
au perechi diferite, care va demonstra presupunerea.
Presupunem, prin reducere la absurd, ca exista doi indici i,j astfel incat .

Aceasta implica ca aici exista un intreg p>0 astfel incat

, sau
Dar i-j si i+j+1 au paritati diferite.
Caz 1
Daca i-j par si i+j impar cum (1)
Dar (2)
din inegaliatatile (1) si (2) rezulta contradictie
Caz 1
Daca i-j impar si i+j par cum (3)
Dar (4)
din inegaliatatile (3) si (4) rezulta contradictie
deci lema e dem

Disperia dubla.
Este una din cele mai bune metode disponibile pentru adresarea directa deoarece
permutarile produse au multe dintre caracteristicile permutarilor alese aleator.
Dispersia dubla foloseste o functie de dispersie de forma
Unde h1 si h2 sunt functii de dispersie auxiliare si h2(k) pentru orice K.
prima pozitie verificata este T[h1(k)], pozitiile successive de verificat sunt compensate de
pozitiile anterioare, de valoare h2(k) modulo n .

6
Astfel, spre deosebire de cazul verificarii liniare sau patratice, secventa de verificare de
aici depinde pe doua cai de cheia K, inca de la pozitia initiala de verificare, echilibrarea,
sau ambele, putand varia.
Figura 2, da un exemplu de inserare prin dispersie dubla.

Valoarea lui h2(k) trebuie sa fie relativ prima in tabelul dispersiei de lungime m pentru tot
tabelul de dispersie pentru a fi cautata. Altfel, daca m si h2(k) au cel mai mare divizor
comun d>1 pentru cateva chei K, atunci o cautare dupa cheia K va examina doar 1/d din
tabelul de disperie.

Lema 2. Daca unde pentru fiecare cheie K si cel mai

mare divizor comun (h2(k),m)=1, atunci pentru fiecare cheie K, <h(K,0), h(K,1), ….,
h(K, m-1)> este o permutare a lui <0,1,…,m-1>
Demonstratie :
La fel ca la lema 1 trebuie sa aratam ca pentru fiecare i=0,1,..,m-1, toate valorile au
[Link]. Daca exista doi indici i,j i>j, astfel incat

Atunci exista un intreg p>0 astfel incat (3)

Un mod convenabil de a garanta aceste conditii pe h2 este sa il lasam pe m sa fie o putere
a lui 2 si s ail construim pe h2 sa produca intotdeauna un numar impar. Alt mod este s ail
lasam pe m sa fie prim si sa il construim pe h2 astfel încât să întoarcă întotdeauna un
număr întreg pozitiv mai mic decat m. De exemplu, putem alege m prim si fie

, unde m’este ales un pic mai mic decat m (m-1 sau m-2).
In concluzie, dispersarea cu adresare directa nu are nevoie de niciun spatiu suplimentar.
Cu toate acestea, performanta ei devine slaba cand factorul de incarcare este aproape unu
si aceasta nu suporta stergerea.