Czy możesz podać przykłady sposobów rozwiązywania kolizji podczas pracy z tablicami haszującymi?

Przy pracy z tablicami haszującymi kolizje występują, gdy różne klucze są haszowane do tego samego miejsca. Główne sposoby rozwiązywania kolizji:

1. Metoda łańcuchowa (chaining) — w każdej komórce tablicy haszującej przechowywana jest lista powiązana elementów, które trafiły do tej komórki. W przypadku kolizji nowy element jest dodawany do listy.

2. Otwarte adresowanie (open addressing) — w przypadku kolizji szukana jest następna wolna komórka według określonej reguły (sondowanie liniowe, kwadratowe, podwójne haszowanie).

Przykład metody łańcuchowej:

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

W związku z tym wybór metody zależy od wymagań dotyczących wydajności i pamięci.