Millised on viisid hash-kollisioonide lahendamiseks…

Eraldus ahelate meetod (Separate Chaining):
- Iga element hash-tabelis (kasti) on viide seotud ühendatud nimekirjale (või muule andmestruktuurile, näiteks puule).
- Kõik elemendid, mis on hashitud sama kasti, lisatakse sellele nimekirjale.
```
// Näide: ühendatud nimekirja sõlm ahelate jaoks
struct Node {
    int key;
    int value;
    Node* next;
};

// Kastis hoitakse viidet nimekirja algusele
Node* buckets[TABLE_SIZE];
```

Avatud aadressimise meetodid (Open Addressing):

Kõik elemendid on otse hash-tabelis.
Kohtumise korral otsitakse järgmist vaba kohta massiivis.

Erinevad meetodid määravad järgmise koha:

Lineaarne otsing (Linear Probing): Kontrollitakse lahtrid järjestikuselt fikseeritud sammuga i, i+1, i+2, ... mod TABLE_SIZE.

// Lineaarse otsingu näide
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;
}
// Nüüd on table[i] kas tühi või sisaldab otsitavat elementi

Kvadraatne otsing (Quadratic Probing): Kontrollitakse lahtrid sammuga, mis sõltub katse ruudust i, i+1², i+2², ... mod TABLE_SIZE.

// Kvadraatse otsingu näide
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;
}
// Nüüd on table[i] kas tühi või sisaldab otsitavat elementi (või on tabel üle täidetud)

Kaheksakordne hashimine (Double Hashing): Kasutatakse teine hash-funktsioon, et määrata samm i, i + step, i + 2*step, ... mod TABLE_SIZE, kus step arvutatakse teise hash-funktsiooniga.

// Kaheksakordse hashimise näide
int hash1(int key) { return key % TABLE_SIZE; }
int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // Teine hash-funktsioon

int i = hash1(key);
int step = hash2(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + step) % TABLE_SIZE;
}
// Nüüd on table[i] kas tühi või sisaldab otsitavat elementi

Dünaamiline suuruse muutmine (Resizing):

Kui täituvusmäär jõuab teatud tasemeni, luuakse uus, suurem hash-tabel.
Kõik elemendid vanast tabelist ümberhashitakse ja sisestatakse uude.

// Näide loogikast, kui on vaja suurendada
if (current_size / (double)table_size > max_load_factor) {
    // Loo uus kahekordse suurusega tabel
    // Uuendage ja sisestage kõik elemendid vanast tabelist
    // Kustutage vana tabel
}

Valitud meetod sõltub jõudlusest, mälust, teostamise keerukusest ja oodatavast täituvuse määrast.

Millised on viisid hash-kollisioonide lahendamiseks?