Junior — Middle

Можеш ли дати примерe начина решавања судара при раду са хеш табелама?

sobes.tech АИ

Одговор од АИ

Када радите са хеш табелама, сукоби (collision) се јављају када различити кључеви буду хеширани у исту ћелију. Главни начини за решавање сукоба су:

Метод ланца (chaining) — у свакој ћелији хеш табеле се чува повезана листа елемената који су у њу ушли. У случају сукоба, нови елемент се додаје у листу.
Отворено адресирање (open addressing) — у случају сукоба, по одређеном правилу се тражи следећа слободна ћелија (линеарно претраживање, квадратно претраживање, дупло хеширање).

Пример метода ланца:

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

Избор метода зависи од захтева за перформансом и меморијом.

Претходно Следеће