Poți oferi exemple de metode de rezolvare a coliziunilor atunci când lucrezi cu tabele de hash?

Atunci când lucrați cu tabele hash, coliziunile apar atunci când diferite chei sunt hash-ate în aceeași celulă. Principalele modalități de a rezolva coliziunile:

1. Metoda lanțurilor (chaining) — în fiecare celulă a tabelului hash se stochează o listă legată de elemente care au fost plasate în acea celulă. În cazul unei coliziuni, elementul nou este adăugat la listă.

2. Adresare deschisă (open addressing) — în cazul unei coliziuni, se caută următoarea celulă liberă conform unei reguli determinate (sondare liniară, sondare pătratică, hashing dublu).

Exemplu de metoda lanțurilor:

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))
    }
}

Prin urmare, alegerea metodei depinde de cerințele de performanță și memorie.