Jakými metodami lze snížit pravděpodobnost kolizí při používání hash tabulek?

Pro snížení pravděpodobnosti kolizí v hash tabulkách se používají následující metody:

1. Výběr dobré hashovací funkce — funkce by měla rovnoměrně rozdělovat klíče do hash tabulky, minimalizujíc pravděpodobnost kolizí.

2. Zvětšení velikosti tabulky — čím větší je pole, tím menší je pravděpodobnost, že dva klíče skončí ve stejné buňce.

3. Použití metod řešení kolizí:

   • Otevřená adresace (lineární sondování, kvadratické sondování, dvojité hashování) — při kolizi se hledá následující volná buňka.
   • Řetězení (chaining) — v každé buňce je uložen spojový seznam nebo jiný kontejner pro všechny prvky se stejným hashem.

4. Rehashing (přerozdělení) — při dosažení určitého zatížení se zvětší velikost a prvky se znovu rozdistribuují.

Příklad v Kotlinu (řetězení):

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