Milliste meetoditega saab vähendada kokkupõrke tõenäosust kasutades hajutustabeleid?

Selleks, et vähendada kokkupõrke (kollisioonide) tõenäosust hajutustabelites, kasutatakse järgmisi meetodeid:

1. Hea hajufunktsiooni valimine — funktsioon peaks ühtlaselt jaotama võtmed hajutustabelis, minimeerides kokkupõrke tõenäosust.

2. Tabeli suuruse suurendamine — mida suurem on massiiv, seda väiksem on tõenäosus, et kaks võtit satuvad samasse lahtrisse.

3. Kollisioonide lahendamise meetodite kasutamine:

   • Ava aadressimine (jooneline otsing, kvadratiivne otsing, topelt hajutamine) — kollisiooni korral otsitakse järgmine vaba lahter.
   • Kettimine (chaining) — igas lahtris hoitakse seotud nimekiri või muu konteiner kõigi samasse hash-i kuuluvate elementide jaoks.

4. Rehashing (suurendamine) — kui saavutatakse teatud laadimistegur, suurendatakse suurust ja elemente ümber jaotatakse.

Näide Kotlinis (kettimine):

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