Kokiais metodais galima sumažinti susidūrimų tikimybę naudojant maišos lenteles?

Siekiant sumažinti susidūrimo (kolidijų) tikimybę žemėlapiuose naudojami šie metodai:

1. Pasirinkti gerą maišos funkciją — funkcija turi tolygiai paskirstyti raktus žemėlapyje, sumažindama kolizijų tikimybę.

2. Padidinti lentelės dydį — kuo didesnė masyvo dydis, tuo mažesnė tikimybė, kad du raktai pateks į tą pačią langelį.

3. Naudoti kolizijų sprendimo metodus:

   • Atvira adresacija (linijinis ieškojimas, kvadratinis ieškojimas, dvigubas maišymas) — kolizijos atveju ieškoma kitos laisvos langelio.
   • Grandinimas (chaining) — kiekviename langelyje saugomas susietas sąrašas arba kitas konteineris visiems elementams su tuo pačiu maišos reikšme.

4. Rehashing (perdarymas) — pasiekus tam tikrą apkrovos koeficientą, dydis didinamas ir elementai perdalinami.

Pavyzdys Kotlin kalba (grandinimas):

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