Jakimi metodami można zmniejszyć prawdopodobieństwo kolizji podczas korzystania z tablic haszujących?

Aby zmniejszyć prawdopodobieństwo kolizji w tablicach haszujących, stosuje się następujące metody:

1. Wybór dobrej funkcji haszującej — funkcja powinna równomiernie rozkładać klucze po tablicy, minimalizując prawdopodobieństwo kolizji.

2. Zwiększenie rozmiaru tablicy — im większa tablica, tym mniejsze prawdopodobieństwo, że dwa klucze trafią do tego samego miejsca.

3. Użycie metod rozwiązywania kolizji:

   • Adresowanie otwarte (sondowanie liniowe, kwadratowe, podwójne haszowanie) — przy kolizji szuka się następnej wolnej komórki.
   • Łańcuchowanie — w każdej komórce przechowuje się listę powiązaną lub inny kontener dla elementów z tym samym hashem.

4. Rehaszowanie (resize) — gdy osiągnięty zostanie określony współczynnik obciążenia, rozmiar jest zwiększany, a elementy są ponownie rozkładane.

Przykład w Kotlinie (łańcuchowanie):

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