¿Qué métodos se pueden usar para reducir la probabilidad de colisiones al usar tablas hash?

Para reducir la probabilidad de colisiones en las tablas hash se utilizan los siguientes métodos:

1. Elegir una buena función hash — la función debe distribuir uniformemente las claves en la tabla hash, minimizando la probabilidad de colisiones.

2. Aumentar el tamaño de la tabla — cuanto mayor sea el tamaño del array, menor será la probabilidad de que dos claves caigan en la misma celda.

3. Utilizar métodos de resolución de colisiones:

   • Dirección abierta (sondeo lineal, sondeo cuadrático, doble hashing) — en caso de colisión, se busca la siguiente celda libre.
   • Encadenamiento — en cada celda se almacena una lista enlazada u otro contenedor para todos los elementos con el mismo hash.

4. Rehashing (redimensionamiento) — cuando se alcanza un cierto factor de carga, se aumenta el tamaño y se redistribuyen los elementos.

Ejemplo en Kotlin (encadenamiento):

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