What methods can be used to resolve conflicts in hash tables during collisions?

Hash collisions in hash tables occur when two keys hash to the same index. Main methods for resolving collisions:

1. Chaining method — each cell of the array stores a linked list (or another container) of elements with the same hash. When a collision occurs, the new element is added to the list.

2. Open addressing — upon collision, the next free cell is searched according to a certain sequence (linear probing, quadratic probing, double hashing).

3. Double hashing — a second hash function is used to compute the step size for searching for a free cell.

4. Rehashing — when a certain load factor is reached, a new larger table is created, and all elements are rehashed.

Example of chaining method:

class HashTable<Key: Hashable, Value> {
    private var buckets: [[(key: Key, value: Value)]]
    private let capacity: Int

    init(capacity: Int = 16) {
        self.capacity = capacity
        self.buckets = Array(repeating: [], count: capacity)
    }

    func hash(_ key: Key) -> Int {
        return abs(key.hashValue) % capacity
    }

    func insert(key: Key, value: Value) {
        let index = hash(key)
        for (i, element) in buckets[index].enumerated() {
            if element.key == key {
                buckets[index][i].value = value
                return
            }
        }
        buckets[index].append((key, value))
    }

    func value(for key: Key) -> Value? {
        let index = hash(key)
        return buckets[index].first { $0.key == key }?.value
    }
}