Care sunt metodele de rezolvare a coliziunilor de…

Metoda lanțurilor (Separate Chaining):
- Fiecare element din array-ul tabelului hash (bucket) este un pointer către o listă înlănțuită (sau altă structură de date, de exemplu, un copac).
- Toate elementele hash-ate în același bucket sunt adăugate în această listă.
```
// Exemplu: nodul unei liste înlănțuite pentru lanțuri
struct Node {
    int key;
    int value;
    Node* next;
};

// În bucket se stochează un pointer către capul listei
Node* buckets[TABLE_SIZE];
```

Metode de adresare deschisă (Open Addressing):

Toate elementele sunt stocate direct în array-ul tabelului hash.
În cazul coliziunii, se caută următoarea poziție liberă în array.

Se diferențiază după modul de determinare a următoarei poziții:

Probing liniar (Linear Probing): Se verifică celulele în ordine cu un pas fix i, i+1, i+2, ... mod TABLE_SIZE.

// Exemplu de probing liniar
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + 1) % TABLE_SIZE;
}
// Acum table[i] este gol sau conține elementul căutat

Probing pătratic (Quadratic Probing): Se verifică celulele cu un pas care depinde de pătratul încercării i, i+1², i+2², ... mod TABLE_SIZE.

// Exemplu de probing pătratic
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
int attempt = 0;
while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
    attempt++;
    i = (hash(key) + attempt * attempt) % TABLE_SIZE;
}
// Acum table[i] este gol sau conține elementul căutat (sau tabelul este plin)

Hashing dublu (Double Hashing): Se folosește o a doua funcție hash pentru a determina pasul de probing i, i + step, i + 2*step, ... mod TABLE_SIZE, unde step se calculează cu a doua funcție hash a cheii.

// Exemplu de double hashing
int hash1(int key) { return key % TABLE_SIZE; }
int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // A doua funcție hash

int i = hash1(key);
int step = hash2(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + step) % TABLE_SIZE;
}
// Acum table[i] este gol sau conține elementul căutat

Redimensionarea dinamică (Resizing):

Când se atinge un anumit coeficient de încărcare (load factor), se creează o nouă tabelă hash mai mare.
Toate elementele din tabela veche sunt recalculare și inserate în cea nouă.

// Exemplu de logică pentru resize
if (current_size / (double)table_size > max_load_factor) {
    // Crează o nouă tabelă de dimensiune dublă
    // Rehash și inserează toate elementele din tabela veche
    // Șterge tabela veche
}

Alegerea metodei depinde de cerințele de performanță, memorie, complexitatea implementării și factorul de încărcare așteptat. Metoda lanțurilor este de obicei mai simplu de implementat și funcționează bine cu factori de încărcare mari, dar necesită memorie suplimentară pentru pointeri. Metodele de adresare deschisă pot utiliza memoria mai compact, dar sunt mai sensibile la funcția hash și la problemele de "clusterizare". Resize-ul este necesar pentru a menține eficiența pe măsură ce numărul de elemente crește.

Care sunt metodele de rezolvare a coliziunilor de hash?