Puoi fornire esempi di metodi per risolvere le collisioni quando si lavora con tabelle hash?

Quando si lavora con le tabelle hash, si verificano collisioni (collisioni) quando chiavi diverse vengono hashate nella stessa cella. I principali metodi per risolvere le collisioni:

1. Metodo di chaining (catena) — in ogni cella della tabella hash viene memorizzata una lista collegata di elementi che sono caduti in quella cella. In caso di collisione, il nuovo elemento viene aggiunto alla lista.

2. Indirizzamento aperto (open addressing) — in caso di collisione, si cerca la cella libera successiva secondo una regola determinata (sondaggio lineare, sondaggio quadratico, doppio hashing).

Esempio del metodo di chaining:

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

Pertanto, la scelta del metodo dipende dai requisiti di prestazioni e memoria.