Hash tabloları kullanırken çakışma olasılığını azaltmak için hangi yöntemler kullanılabilir?

Hash tablolarında çakışma olasılığını azaltmak için aşağıdaki yöntemler kullanılır:

1. İyi bir hash fonksiyonu seçmek — fonksiyon, anahtarları hash tablosuna eşit şekilde dağıtmalı ve çakışma olasılığını en aza indirmelidir.

2. Tablo boyutunu artırmak — dizinin boyutu ne kadar büyükse, iki anahtarın aynı hücreye düşme olasılığı o kadar düşük olur.

3. Çakışma çözüm yöntemleri kullanmak:

   • Açık adresleme (doğrusal sondalama, kuadratik sondalama, çift hashing) — çakışma durumunda, bir sonraki boş hücre aranır.
   • Zincirleme (chaining) — her hücrede, aynı hash'e sahip tüm öğeleri tutan bağlı liste veya başka bir konteyner bulunur.

4. Yeniden hashleme (resize) — belirli bir yük faktörüne ulaşıldığında, boyut artırılır ve öğeler yeniden dağıtılır.

Kotlin'de zincirleme örneği:

class HashTable<K, V>(val size: Int) {
    private val buckets = Array<MutableList<Pair<K, V>>>(size) { mutableListOf() }

    private fun hash(key: K): Int = key.hashCode().absoluteValue % size

    fun put(key: K, value: V) {
        val index = hash(key)
        val bucket = buckets[index]
        val existing = bucket.indexOfFirst { it.first == key }
        if (existing >= 0) bucket[existing] = key to value
        else bucket.add(key to value)
    }

    fun get(key: K): V? {
        val index = hash(key)
        return buckets[index].firstOrNull { it.first == key }?.second
    }
}