Tudnál példákat adni arra, hogyan lehet elkerülni az ütközéseket a hash-táblákkal való munkában?

Hash táblákkal dolgozva ütközések (kollisionek) fordulnak elő, amikor különböző kulcsokat ugyanabba a cellába hash-elnek. A fő módszerek az ütközések kezelésére:

1. Láncolási módszer (chaining) — minden hash tábla cellájában egy összekapcsolt lista tárolódik az abba a cellába eső elemekről. Ütközés esetén az új elem hozzáadódik a listához.

2. Nyitott címzés (open addressing) — ütközés esetén a következő szabad cellát keressük egy meghatározott szabály szerint (lineáris keresés, kvadratikus keresés, dupla hash).

A láncolási módszer példája:

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

Így a módszer kiválasztása a teljesítmény és memóriaigények függvénye.