Milyen módszerekkel lehet csökkenteni az ütközések valószínűségét a hash-táblák használata során?

A hash-táblákban az ütközések (ütközések) valószínűségének csökkentése érdekében a következő módszereket alkalmazzák:

1. Jó hash-függvény kiválasztása — a függvénynek egyenletesen kell elosztania a kulcsokat a hash-táblában, minimalizálva az ütközések valószínűségét.

2. A tábla méretének növelése — minél nagyobb a tömb mérete, annál kisebb az esély arra, hogy két kulcs ugyanabba a cellába kerüljön.

3. Az ütközések feloldására szolgáló módszerek alkalmazása:

   • Nyitott címzés (lineáris keresés, kvadratikus keresés, dupla hash) — ütközés esetén a következő szabad cellát keresik.
   • Láncolás (chaining) — minden cellában egy összekapcsolt lista vagy más konténer tárolja azonos hash-sel rendelkező összes elemet.

4. Rehashing (átméretezés) — amikor egy meghatározott töltési tényező eléri a határt, a méret növelése és az elemek újraelosztása történik.

Kotlin példában láncolással:

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