Quali metodi possono essere usati per ridurre la probabilità di collisioni nell'uso di tabelle hash?

Per ridurre la probabilità di collisioni nelle tabelle hash vengono utilizzati i seguenti metodi:

1. Scegliere una buona funzione di hash — la funzione deve distribuire uniformemente le chiavi sulla tabella hash, minimizzando la probabilità di collisioni.

2. Aumentare la dimensione della tabella — più grande è l'array, minore è la probabilità che due chiavi cadano nella stessa cella.

3. Utilizzare metodi di risoluzione delle collisioni:

   • Indirizzamento aperto (sondaggio lineare, sondaggio quadratico, hashing doppio) — in caso di collisione, si cerca la prossima cella libera.
   • Chaining (catene) — in ogni cella si memorizza una lista collegata o altro contenitore per tutti gli elementi con lo stesso hash.

4. Rehashing (ridimensionamento) — quando si raggiunge un certo fattore di carico, si aumenta la dimensione e si ridistribuiscono gli elementi.

Esempio in Kotlin (chaining):

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