Pouvez-vous donner des exemples de méthodes pour résoudre les collisions lors de l'utilisation de tables de hachage?

Lorsqu'on travaille avec des tables de hachage, des collisions se produisent lorsque différentes clés sont hachées dans la même cellule. Les principales méthodes pour résoudre les collisions :

1. Méthode de chaînage (chaining) — chaque cellule de la table de hachage contient une liste chaînée d'éléments qui y ont été placés. En cas de collision, le nouvel élément est ajouté à la liste.

2. Adressage ouvert (open addressing) — en cas de collision, la cellule suivante libre est recherchée selon une règle déterminée (sondage linéaire, sondage quadratique, double hachage).

Exemple de la méthode de chaînage :

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

Ainsi, le choix de la méthode dépend des exigences en termes de performance et de mémoire.