Kun je voorbeelden geven van methoden om botsingen op te lossen bij het werken met hash-tabellen?

Bij het werken met hashtabellen ontstaan botsingen (collisies) wanneer verschillende sleutels in dezelfde cel worden gehasht. De belangrijkste manieren om botsingen op te lossen:

1. Kettingmethode (chaining) — in elke cel van de hashtabel wordt een gekoppelde lijst van elementen opgeslagen die in die cel terecht zijn gekomen. Bij een botsing wordt het nieuwe element aan de lijst toegevoegd.

2. Open adressering (open addressing) — bij een botsing wordt volgens een bepaalde regel (lineair zoeken, kwadratisch zoeken, dubbele hashing) de volgende vrije cel gezocht.

Voorbeeld van de kettingmethode:

class HashTable {
    var buckets: [[(key: String, value: Int)]]
    
    init(size: Int) {
        buckets = Array(repeating: [], count: size)
    }
    
    func hash(_ key: String) -> Int {
        return abs(key.hashValue) % buckets.count
    }
    
    func insert(key: String, value: Int) {
        let index = hash(key)
        buckets[index].append((key, value))
    }
}

Dus, de keuze van de methode hangt af van de prestatie- en geheideisen.