Quais métodos podem ser usados para reduzir a probabilidade de colisões ao usar tabelas de hash?

Para reduzir a probabilidade de colisões em tabelas de hash, utilizam-se os seguintes métodos:

1. Escolher uma boa função de hash — a função deve distribuir uniformemente as chaves na tabela de hash, minimizando a probabilidade de colisões.

2. Aumentar o tamanho da tabela — quanto maior for o tamanho do array, menor será a probabilidade de duas chaves caírem na mesma célula.

3. Utilizar métodos de resolução de colisões:

   • Endereçamento aberto (sondagem linear, sondagem quadrática, hashing duplo) — em caso de colisão, procura-se a próxima célula livre.
   • Encadeamento — cada célula armazena uma lista ligada ou outro contêiner para todos os elementos com o mesmo hash.

4. Rehashing (redimensionamento) — quando se atinge um determinado fator de carga, o tamanho é aumentado e os elementos são redistribuídos.

Exemplo em Kotlin (encadeamento):

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