Akými metódami je možné znížiť pravdepodobnosť kolízií pri používaní hash tabuliek?

Na zníženie pravdepodobnosti kolízií v hash tabuľkách sa používajú nasledujúce metódy:

1. Výber dobrej hashovacej funkcie — funkcia by mala rovnomerne rozdeľovať kľúče do hash tabuľky, minimalizujúc pravdepodobnosť kolízií.

2. Zväčšenie veľkosti tabuľky — čím väčší je poľ, tým menšia je pravdepodobnosť, že dva kľúče skončia v rovnakej bunke.

3. Použitie metód riešenia kolízií:

   • Otvárané adresovanie (lineárne sondovanie, kvadratické sondovanie, dvojité hashovanie) — pri kolízii sa hľadá nasledujúca voľná bunka.
   • Reťazenie (chaining) — v každej bunke sa uchováva spojený zoznam alebo iný kontajner pre všetky prvky s rovnakým hashom.

4. Rehashing (zmena veľkosti) — keď sa dosiahne určitý faktor zaťaženia, veľkosť sa zväčší a prvky sa znovu rozdistribuujú.

Príklad v Kotlin (reťazenie):

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