Structuri de Date 2023 - L5: Hashtable

Structuri de Date

Laborator 5: Hashtable

Laborator 5: Tabele de dispersie

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;}

Alegerea temei de laborator (link).

MAXIM ~3 STUDENTI PER SEMIGRUPA LA ACEEASI TEMA

🙂 Folosind un tabel de dispersie pentru multimea mai mare, implementati intersectia a doua multimi. Cealalta multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din intersectie. O(n + m + coliziuni)
🙂 Folosind un tabel de dispersie pentru multimea mai mare, implementati diferenta a doua multimi. Cealalta multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din diferenta. O(n + m + coliziuni)
🙂 Folosind un tabel de dispersie pentru multimea mai mare, implementati diferenta simetrica a doua multimi. Cealalta multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din diferenta simetrica. O(n + m + coliziuni)
🙂 Folosind un tabel de dispersie pentru multisetul mai mare, implementati reuniunea a doua multiseturi. Celalalt multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din reuniune. O(n + m + coliziuni) 4a 2b 7c ∪ 2a 4b 3c = 4a 4b 7c -> luam maximum
🙂 Folosind un tabel de dispersie pentru multisetul mai mare, implementati intersectia a doua multiseturi. Celalalt multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din intersectie. O(n + m + coliziuni) 4a 2b 7c ∩ 2a 4b 3c = 2a 2b 3c -> luam minimum
🙂🔨👑 Folosind un tabel de dispersie pentru multisetul mai mare, implementati diferenta a doua multiseturi. Celalalt multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din diferenta. O(n + m + coliziuni) 4a 2b 7c \ 2a 4b 3c = 2a 4c -> luam diferenta
🙂🔨👑 Folosind un tabel de dispersie pentru multisetul mai mare, implementati diferenta simetrica a doua multiseturi. Celalalt multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din diferenta simetrica. O(n + m + coliziuni) 4a 2b 7c ∆ 2a 4b 3c = 2a 2b 4c -> (A\B)∪(B\A)

🙂🔨👑 Probleme pentru smecheri:

A.(3p) Implementati tabele de dispersie folosind strategia de rezolvare a conflictelor: coalesced hashing varianta cu cellar (wikipedia).

B.(3p) Implementati tabele de dispersie folosind strategia de rezolvare a conflictelor: cuckoo hashing (wikipedia).

C.(3p) Fie un set de date compus din 20000 hash-uri SHA1, distincte, ale unor stringuri alese arbitrar. Construiti o functie hash perfecta pentru set-ul ales.