SDA Lucrarea 6

În acest laborator se vor implementa structuri de date asociative (map) cu arbori binari și funcții hash.

Structura de date asociativă - Map

Structura de date asociativă (map) este o structură de date abstractă care stochează perechi de elemente cheie-valoare, 
într-o ordine arbitrară stabilită de structură, astfel încât nu pot exista două perechi cu aceeași cheie în map.

În esență, un map este o mulțime (set) de chei care sunt întotdeauna stocate împreună cu o valoare.

Map-ul are următoarele proprietăți:

1. Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
2. Numărul de elemente ce poate fi stocat de structură este nelimitat.
3. Elementele stocate în map sunt de același fel.
4. Tipul de date al cheii și tipul de date al valorii pot fi diferite.
5. Map-ul poate conține doar chei unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două chei sunt egale din punctul de vedere al map-ului, ele nu pot fi ambele prezente în perechi cheie-valoare în map.

Map-ul suportă următoarele operații de bază:

1. Interogarea numărului de elemente din map.
2. Verificarea dacă map-ul este gol.
3. Adăugarea perechi cheie-valoare (insert) - dacă cheia există deja în map, aceasta nu se înlocuiește.
4. Verificarea dacă o cheie există în map (count).
5. Căutarea unei valori după o cheie dată (at);
6. Eliminarea unei chei din map (erase).

Implementarea de structuri asociative cu funcții hash

Definirea funcțiilor hash și a proprietăților lor s-a făcut în laboratorul 5 (SDA Lucrarea 5#Implementarea de mulțimi cu funcții hash).

Tipul de date și funcțiile de bază

În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip Person (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:

struct Person {
    std::string firstName;
    std::string lastName;
    std::string idNumber; // seria si numarul de buletin
    std::string address;
    std::string birthday;
    std::string cnp;
};

Funcțiile de hash și de egalitate pentru clasa std::string sunt deja implementate în STL. Dacă totuși aveți nevoie de a folosi niste funcții proprii, acestea se scriu în același fel ca cele pentru mulțimi împlementate cu funcții hash (vezi SDA Lucrarea 5).

Clasa std::unordered_map

Pentru stocarea datelor necesare map-ului, În STL se definește clasa std::unordered_map în header-ul unordered_map. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap; // un map de la string la Person
    return 0;
}

Crearea unui std::unordered_map

Pentru crearea unui std::unordered_map, se definește următorul constructor:

/**
 * Constructorul creeaza un map nou și inițializează structurile de date interne.
 */
unordered_map();

Exemplu:

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    return 0;
}

Interogarea numărului de elemente din map

Pentru interogarea numărului de elemente din map definim:

/**
 * Functia intoarce numarul de elemente din map.
 * @param map map-ul pentru care se cere dimensiunea.
 * @return numarul de elemente din map.
 */
unsigned hashMapSize(struct HashMap * map);

Funcția va întoarce valoarea din câmpul size din structură.

• Complexitate în timp: O(1)
• Complexitate în spațiu: O(1)

Pentru a afla dacă map-ul este gol definim:

/**
 * Functia intoarce 1 dacă map-ul nu conține nici un element.
 * @param map map-ul de interes.
 * @return 1 dacă map-ul este gol, 0 în rest.
 */
char hashMapIsEmpty(struct HashMap * map);

Funcția va întoarce 1 dacă valoarea din câmpul size este 0.

• Complexitate în timp: O(1)
• Complexitate în spațiu: O(1)

Adăugarea unei perechi cheie-valoare în map

Pentru operația de adăugare se definește următoarea funcție:

/**
 * Functia adauga perechea data in map daca cheia nu exista. Daca
 *  cheia exista deja, valoarea si cheia sunt actualizate.
 * @param map map-ul in care trebuie adaugata perechea.
 * @param key cnp-ul folosit pe post de cheie.
 * @param value persoana asociata CNP-ului.
 */
void hashMapPut(struct HashMap * map, char * key, struct Person value);

Adăugarea se realizează în felul următor:

1. Se aplică funcția hash pe variabila key.
2. Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
3. Se iterează peste nodurile listei căutând cheia key în pereche, folosind funcția equals. Dacă cheia este găsită, atunci cheia și valoarea din pereche sunt actualizate cu valorile argumentelor key și value și funcția se încheie; altfel, se crează un nod nou care se adaugă listei care va conține perechea key - value, dimensiunea listei și dimensiunea map-ului se incrementează.

• Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
• Complexitate în spațiu: O(1)

Atenție: Deoarece vectorul array conține variabile de tip struct LinkedList și nu pointeri, pentru a folosi funcțiile definite în hashMapLinkedList.h e necesară obținerea adresei variabilei de tip struct LinkedList folosind operatorul &.

Eliminarea unei chei din map

Pentru operația de eliminare se definește următoarea funcție:

/**
 * Functia elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param map map-ul din care trebuie eliminat elementul.
 * @param key cheia (CNP-ul) ce trebuie eliminata.
 */
void hashMapRemove(struct HashMap * map, char * key);

Eliminarea se realizează în felul următor:

1. Se aplică funcția hash pe variabila key.
2. Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
3. Se folosește funcția linkedListSearch pentru a verifica dacă person există în listă.
4. Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția linkedListDelete pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.

• Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
• Complexitate în spațiu: O(1)

Verificarea dacă o cheie există în map

Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:

/**
 * Functia intoarce 1 daca cheia specificata exista in map.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
char hashMapHasKey(struct HashMap * map, char * key);

Verificarea unei chei dacă este sau nu în map se realizează în felul următor:

1. Se aplică funcția hash pe variabila key.
2. Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
3. Se folosește funcția linkedListSearch pentru a verifica dacă key există în listă.
4. Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.

• Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
• Complexitate în spațiu: O(1)

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definește urmtoarea funcție:

/**
 * Functia intoarce valoarea asociată cheii key.
 * @param map map-ul in care se cauta cheia.
 * @param key cheia (CNP-ul) cautata.
 * @return valoarea asociată cheii.
 */
struct Person hashMapGet(struct HashMap * map, char * key);

Căutarea unei valori după cheie se realizează în felul următor:

1. Se aplică funcția hash pe variabila key.
2. Folosind valoarea obținută se accesează lista de pe poziția hash-ului din array.
3. Se iterează peste nodurile din listă și se caută cheia folosind funcția equals.
4. Dacă cheia a fost găsită, se întoarce valoarea asociată; dacă s-a ajuns la sfârșitul listei fără a se găsi cheia, se întoarce o structură de tip Person, indiferent cu ce valori (comportament nedefinit).

• Complexitate în timp: O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
• Complexitate în spațiu: O(1)

Ștergerea unui HashMap

Pentru dezalocarea unui HashMap, se definește următoarea funcție:

/**
 * Functia sterge hash map-ul specificat.
 * @param map hash map-ul ce trebuie sters.
 */
void deleteHashMap(struct HashMap * map);

Pentru ștergerea unui HashMap se urmează următorii pași:

1. Se iterează peste tot array-ul, ștergându-se toate nodurile din toate listele.
2. Se șterge memoria alocată pentru structura de tip HashMap.

• Complexitate în timp: O(MAX_HASH)
• Complexitate în spațiu: O(1)