Ar galite pateikti pavyzdžių, kaip spręsti susidūrimus dirbant su žemėlapių lentelėmis?

Dirbant su maišos lentelėmis, susidaro susidūrimai (collision), kai skirtingi raktai yra maišomi į tą pačią langelį. Pagrindiniai būdai spręsti susidūrimus:

1. Grandinimo metodas (chaining) — kiekvienoje maišos lentelės langelyje saugoma susietoji sąrašas elementų, kurie ten pateko. Susidūrus, naujas elementas pridedamas prie sąrašo.

2. Atvira adresacija (open addressing) — susidūrus, ieškoma kitos laisvos langelio pagal tam tikrą taisyklę (linijinis paieška, kvadratinė paieška, dviguba maišos funkcija).

Pavyzdys su grandinimo metodu:

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

Taigi, metodo pasirinkimas priklauso nuo našumo ir atminties reikalavimų.