Koje metode možete koristiti da smanjite verovatnoću sudara pri korišćenju hash tabela?

Za smanjenje verovatnoće sudara (kolizija) u hash tabelama koriste se sledeće metode:

1. Izbor dobre hash funkcije — funkcija treba ravnomerno da raspoređuje ključeve po hash tabeli, minimizirajući verovatnoću kolizija.

2. Povećanje veličine tabele — što je veći niz, to je manja verovatnoća da će dva ključa pasti u istu ćeliju.

3. Korišćenje metoda za rešavanje kolizija:

   • Otvorena adresacija (linearno sondiranje, kvadratno sondiranje, dvostruko hashiranje) — pri koliziji traži se sledeća slobodna ćelija.
   • Lančano povezivanje (chaining) — u svakoj ćeliji se čuva povezani spisak ili drugi kontejner za sve elemente sa istim hash-om.

4. Rehashing (povećanje veličine) — kada se dostigne određeni faktor opterećenja, veličina se povećava i elementi se redistribuiraju.

Primer u Kotlinu (lančano povezivanje):

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