Welke methoden bestaan er voor het oplossen van…

Separate Chaining (Gescheiden ketting):
- Elk element in het array van de hashtabel (bucket) is een pointer naar een gekoppelde lijst (of een andere datastructuur, bijvoorbeeld een boom).
- Alle elementen die naar dezelfde bucket worden gehasht, worden aan deze lijst toegevoegd.
```
// Voorbeeld: knoop van een gekoppelde lijst voor chaining
struct Node {
    int key;
    int value;
    Node* next;
};

// In de bucket wordt een pointer naar de kop van de lijst opgeslagen
Node* buckets[TABLE_SIZE];
```

Methoden van open adressering (Open Addressing):

Alle elementen worden direct in het array van de hashtabel opgeslagen.
Bij een collision wordt gezocht naar de volgende vrije plek in het array.

Ze verschillen in de manier waarop de volgende plek wordt bepaald:

Lineair probing: Controleer de cellen in volgorde met een vaste stap i, i+1, i+2, ... mod TABLE_SIZE.

// Voorbeeld van lineair probing
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;
}
// Nu is table[i] of leeg of bevat het gezochte element

Quadratisch probing: Controleer de cellen met een stap die afhankelijk is van het kwadraat van de poging i, i+1², i+2², ... mod TABLE_SIZE.

// Voorbeeld van quadratisch probing
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;
}
// Nu is table[i] of leeg of bevat het gezochte element (of de tabel is vol)

Double hashing: Er wordt een tweede hashfunctie gebruikt om de stapgrootte te bepalen i, i + step, i + 2*step, ... mod TABLE_SIZE, waarbij step wordt berekend met de tweede hashfunctie van de sleutel.

// Voorbeeld van double hashing
int hash1(int key) { return key % TABLE_SIZE; }
int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // Tweede hashfunctie

int i = hash1(key);
int step = hash2(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + step) % TABLE_SIZE;
}
// Nu is table[i] of leeg of bevat het gezochte element

Dynamische resizing:

Wanneer een bepaald laadfactor wordt bereikt, wordt een nieuwe, grotere hashtabel gemaakt.
Alle elementen uit de oude tabel worden opnieuw gehasht en in de nieuwe geplaatst.

// Voorbeeld van logica bij resizing
if (current_size / (double)table_size > max_load_factor) {
    // Maak een nieuwe tabel met dubbele grootte
    // Herhasht en voeg alle elementen uit de oude tabel toe
    // Verwijder de oude tabel
}

De keuze van methode hangt af van de prestatie-eisen, geheugen, implementatiecomplexiteit en de verwachte laadfactor. Separate chaining is meestal eenvoudiger te implementeren en werkt goed bij hoge laadfactoren, maar vereist extra geheugen voor pointers. Open adresseringsmethoden kunnen geheugen efficiënter gebruiken, maar zijn gevoeliger voor de hashfunctie en problemen zoals "clustering". Resizing is nodig om de efficiëntie te behouden naarmate het aantal elementen toeneemt.

Welke methoden bestaan er voor het oplossen van hash-collisies?