Ce metode pot fi utilizate pentru a reduce probabilitatea coliziunilor la utilizarea tabelelor de hash?

Pentru a reduce probabilitatea de coliziuni în tabelele hash, se aplică următoarele metode:

1. Alegerea unei funcții hash bune — funcția trebuie să distribuie uniform cheile în tabelul hash, minimizând probabilitatea de coliziuni.

2. Creșterea dimensiunii tabelului — cu cât dimensiunea array-ului este mai mare, cu atât mai mică este probabilitatea ca două chei să cadă în aceeași celulă.

3. Utilizarea metodelor de rezolvare a coliziunilor:

   • Adresare deschisă (sondare liniară, sondare pătratică, hashing dublu) — în cazul unei coliziuni, se caută următoarea celulă liberă.
   • Împletire (chaining) — în fiecare celulă se păstrează o listă legată sau alt container pentru toate elementele cu același hash.

4. Rehashing (redimensionare) — când se atinge un anumit factor de încărcare, dimensiunea este mărită și elementele sunt redistribuite.

Exemplu în Kotlin (împletire):

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