Vai vari sniegt piemērus, kā novērst sadursmes, strādājot ar haštabulām?

Darbojoties ar haštabulām, rodas sadursmes (collision), kad dažādi atslēgas tiek hašētas tajā pašā šūnā. Galvenie sadursmju risināšanas veidi:

1. Saites metode (chaining) — katrā haštabulas šūnā tiek glabāta saistīta elementu saraksts, kas tajā ir nonākuši. Sadursmes gadījumā jauns elements tiek pievienots sarakstam.

2. Atvērta adresēšana (open addressing) — sadursmes gadījumā, pēc noteikta noteikuma (līnijas meklēšana, kvadrātiska meklēšana, dubultā hašēšana) tiek meklēta nākamā brīvā šūna.

Piemērs ar saistīšanas metodi:

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

Tādējādi, metodes izvēle ir atkarīga no veiktspējas un atmiņas prasībām.