Structuri de Date 2023

Structuri de Date

Curs 8: Tabele si functii de dispersie

Cuprins:

Necesitatea tabelelor de dispersie / hashtables
Preliminarii
Implementarea tabelelor de dispersie
Functia hash
Exemple de functii hash
Strategii de rezolvare a coliziunilor

1. Necesitatea tabelelor de dispersie / hashtables

Sa presupunem ca avem de rezolvat urmatoarea problema:

La supermarket avem |K| = 3000 clienti care vor sa cumpere hartie igienica.
Fiecare client e limitat la 3 pachete.
Fiecare client e identificat prin CNP.

Restrictii:

Nu dispunem de suficienta memorie pentru un vector de frecvente.
Dorim solutii o(log |K|) -> cresterea functiei trebuie sa fie mai lenta ca log |K| -> adica mai rapid decat cautarea binara.

Ideea este ca:

Dorim o structura eficienta pentru a stoca si accesa asocieri de tipul (cheie -> valoare) cu cheile arbitrar de mari.

2. Preliminarii

Avem o multime de chei K pe care dorim s-o inseram in tabelul de dispersie.

In exemplul anterior K = {1970502301921 , 2910410250734, ...}, iar |K|=3000.

Cheile se vor insera impreuna cu niste valori arbitrare asociate (cheie1,valoare1), (cheie2,valoare2).

In exemplul anterior valoarea asociata este numarul de articole cumparate.

Se noteaza universul cheilor U (cu K ⊂ U), multimea in care se pot genera chei.

In exemplul anterior U este multimea CNPurilor corecte.

Avem la dispozitie un tabel de dimensiune n > |K|.
Putem defini un factor de umplere α = p/n, unde p este numarul de intrari ocupate, iar n este numarul maxim de intrari.

3. Implementarea tabelelor de dispersie

Pentru a implementa un tabel de dispersie avem nevoie de:

0. Un tabel T cu n > |K| intrari.

O functie H care mapeaza cheile pe setul de indici din tabelul de dispersie astfel:
- indice = H(cheie) % n, astfel incat T[indice] sa contina (cheie, valoare)
O strategie de rezolvare a conflictelor

4. Functia hash

O functie hash performanta trebuie sa respecte urmatoarele proprietati:

Sa poata fi calculata rapid.
Sa minimizeze numarul de coliziuni.
- cat mai surjectiva (dorim ca imaginea lui H(cheie)%n sa umple setul de indici)
- cat mai injectiva (dorim ca chei diferite sa produca indici diferiti)
Sa aiba imaginea cat mai mica (dorim sa minimizam dimensiunea tabelului)

Daca se cunoaste dinainte multimea de chei, se poate precalcula o functie hash fara coliziuni. O astfel de functie se numeste functie hash perfecta.

O functie hash perfecta minimala este o bijectie care minimizeaza dimensiunea imaginii astfel incat numarul de intrari n din tabelul de dispersie este egal cu numarul de chei |K|.

5. Exemple de functii hash

1. Metoda diviziunii

index = H(k) = k % d.

d este ales ca fiind un numar prim apropiat de dimensiunea tabelului (care dimensiune este de obicei putere de doi)

int hash_diviziune(long long cheie){ return cheie % 19;}

2. Metoda inmultirii

index = H(k) = floor( n * (k*A mod 1) )

A este un numar real cu care multiplicam cheia k;
luam partea fractionara a numarului real rezultat ∈ [0,1)
o inmultim cu dimensiunea tabelului n
partea intreaga a rezultatului este un indice ∈ {0,1,2, ..., n-1}

const double PHI=1.6180339887498948482045868343656;int hash_multiplicare(long long cheie, int N){ double integer_part; return (int)(N*modf(PHI*cheie,&integer_part));}

3. Metoda impachetarii

impartim cheia k in bucati de dimensiune egala
adunam/xoram bucatile

Din cauza ca dimensiunea tabelelor de dispersie este de obicei putere de doi e mai eficient sa impartim cheia in bucati de biti consecutivi.

De exemplu daca avem un tabel de dimensiune 16, observam ca indicii {0,...,15} sunt toate valorile care se pot reprezenta pe 4 biti (16=2^4).

Putem sa impartim cheia in bucati de 4 biti si sa le xor-am.

int hash_impachetare(long long cheie){ int h=0; while (cheie>0){ h=h ^ (cheie&15);//15 in binar este 1111 cheie = cheie >>4; } return h;}

6. Strategii de rezolvare a coliziunilor

Prin inlantuire (chaining)
- cu liste
- cu arbori binari de cautare
- cu arbori binari de cautare echilibrati
- cu alte tabele de dispersie 😎
Open addressing
- Linear probing: index = h(k) + i
- Quadratic probing: index = h(k) + i*i
- Double hashing: index = h(k) + i* h2(k)
Coalesced hashing
Cuckoo hashing
etc.

Exemplu

Elementul hashuit in locatia h se plaseaza la inceputul listei h

Elementul hashuit in locatia i se plaseaza in acelasi array, in urmatoarea locatie libera h+1, h+2, h+3, h+4

Elementul hashuit in locatia i se plaseaza in acelasi array, in urmatoarea locatie libera h+1, h+4, h+9, h+16

(Surse Laborator)

Rezolvare conflicte prin inlantuire:

#include <iostream>#include <cmath>using namespace std;
struct intrare{    long long CNP;    int numar;};
struct nod{    intrare info;    nod* next;};
struct lista{    nod* primul_element;//pointer la primul element    lista(){        primul_element=NULL;//initializare    }    void insert_la_inceput(long long cheie, int valoare){        nod* nou = new nod;        nou->info.CNP = cheie;        nou->info.numar = valoare;        nou->next = primul_element;        primul_element = nou;    }    intrare* cauta_dupa_cheie(long long cheie){        nod* curent = primul_element;        while (curent!=NULL && curent->info.CNP!= cheie)            curent=curent->next;        if (curent==NULL)            return NULL;        return &(curent->info);    }    void afisare(){        nod* pointer;        if (primul_element==NULL)            cout<<"prim=NULL";        else            for (pointer = primul_element; pointer !=NULL;pointer = pointer->next)                cout<<"["<<pointer->info.CNP<<", "<<pointer->info.numar<< "] -> ";        cout<<endl;    }};
int hash_diviziune(long long cheie, int N){    return cheie % 19;}const double PHI=1.6180339887498948482045868343656;int hash_multiplicare(long long cheie, int N){    double integer_part;    return (int)(N*modf(PHI*cheie,&integer_part));}int hash_impachetare(long long cheie, int N){    int h=0;    while (cheie>0){        h=h ^ (cheie&15);        cheie = cheie >>4;    }    return h;}
struct hashtable_chaining{    lista* T;//pointer la viitor array de liste    int n;    int (*hashfunc)(long long, int);    hashtable_chaining(int N, int (*H)(long long, int)){        n=N;        hashfunc = H;        T=new lista[n]; //alocam un array de n liste    }    void put(long long cheie, int valoare){        int hash = hashfunc(cheie,n);        int index = hash % n;        intrare* gasit = T[index].cauta_dupa_cheie(cheie);        if (gasit==NULL)            T[index].insert_la_inceput(cheie,valoare);        else            gasit->numar=valoare;    }    int get (long long cheie){        int hash = hashfunc(cheie,n);        int index = hash % n;        intrare* gasit = T[index].cauta_dupa_cheie(cheie);        if (gasit==NULL)            return -1;        else            return gasit->numar;    }    void afisare(){        for (int i=0;i<n;i++)            T[i].afisare();    }};
int main(){    long long CNPuri[]={2950829275196, 2980114347918, 1951011356684, 2870212513233, 1911025388691, 2990323528197, 2881128175838, 2970701258525, 1990316400901, 2911213299311, 2880402252448, 1890706180378, 1940312307684};    int N = sizeof(CNPuri)/sizeof(long long);
    hashtable_chaining H(16,hash_diviziune);    for (int i=0;i<N;i++)        H.put(CNPuri[i],i);    H.afisare();    return 0;}

Rezolvare conflicte prin open addressing (3 variante):

#include <iostream>#include <cmath>using namespace std;
struct intrare{    long long CNP;    int numar;};
int hash_diviziune(long long cheie, int N){    return cheie % 19;}const double PHI=1.6180339887498948482045868343656;int hash_multiplicare(long long cheie, int N){    double integer_part;    return (int)(N*modf(PHI*cheie,&integer_part));}int hash_impachetare(long long cheie, int N){    int h=0;    while (cheie>0){        h=h ^ (cheie&15);        cheie = cheie >>4;    }    return h;}
struct hashtable_open_addressing{    intrare* T;//pointer la viitor array de intrari    int n;    int (*hashfunc)(long long, int);    hashtable_open_addressing(int N, int (*H)(long long, int)){        n=N;        hashfunc = H;        T=new intrare[n]; //alocam un array de n intrari        for (int i=0;i<n;i++)            T[i].CNP=0;    }    void put(long long cheie, int valoare){        int hash = hashfunc(cheie,n);        int index = hash % n;        int index_final = index;        int i=0;        while (T[index_final].CNP!=0) {i++;index_final=(index+i)%n;}        //while (T[index_final].CNP!=0) {i++;index_final=(index+i*i)%n;}        //while (T[index_final].CNP!=0) {i++;index_final=(index+i*hash_impachetare(cheie,0))%n;}
        T[index_final].CNP=cheie;T[index_final].numar=valoare;    }    int get (long long cheie){        int hash = hashfunc(cheie,n);        int index = hash % n;        int index_final = index;        int i=0;        while (T[index_final].CNP!=cheie) {i++;index_final=(index+i)%n;}        //while (T[index_final].CNP!=cheie) {i++;index_final=(index+i*i)%n;}        //while (T[index_final].CNP!=cheie) {i++;index_final=(index+i*hash_impachetare(cheie,0))%n;}
        return T[index_final].numar;    }    void afisare(){        for (int i=0;i<n;i++)            if (T[i].CNP!=0)                cout<<"["<<T[i].CNP<<", "<<T[i].numar<<"]"<<endl;            else                cout<<"empty"<<endl;    }};
int main(){    long long CNPuri[]={2950829275196, 2980114347918, 1951011356684, 2870212513233, 1911025388691, 2990323528197, 2881128175838, 2970701258525, 1990316400901, 2911213299311, 2880402252448, 1890706180378, 1940312307684};    int N = sizeof(CNPuri)/sizeof(long long);
    hashtable_open_addressing H(16,hash_multiplicare);    for (int i=0;i<N;i++)        H.put(CNPuri[i],i);    H.afisare();    return 0;}

Google Sites

Report abuse