Hash cədvəlləri ilə işləyərkən toqquşmaları aradan qaldırma üsullarına nümunələr göstərə bilərsinizmi?

Hash cədvəlləri ilə işləyərkən, müxtəlif açarlar eyni hüceyrəyə hash olunduqda toqquşmalar (kollisionlar) baş verir. Toqquşmaları həll etməyin əsas yolları:

1. Zəncir metodu (chaining) — hər hash cədvəlinin hüceyrəsində, həmin hüceyrəyə düşən elementlərin əlaqəli siyahısı saxlanılır. Toqquşma baş verdikdə, yeni element siyahıya əlavə olunur.

2. Açıq ünvanlama (open addressing) — toqquşma zamanı, müəyyən bir qaydaya əsasən (xəttsiz axtarış, kvadrat axtarış, cüt hash) növbəti boş hüceyrə axtarılır.

Zəncir metodunun nümunəsi:

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

Buna görə, metodun seçimi performans və yaddaş tələblərinə əsaslanır.