Tema
Algoritmos aleatorizados y hashing
- Algoritmos
- Nivel intermedio
Un algoritmo aleatorizado toma decisiones al azar para garantizar un buen rendimiento esperado sea cual sea la entrada, y el hashing universal aplica esa idea a las tablas de dispersión.
Nombre en inglés
Randomized algorithms and hashing
Intuición
La aleatoriedad no mejora el caso peor, sino que impide que un adversario lo provoque: Al elegir la función de dispersión al azar dentro de una familia, ninguna entrada fija puede estar preparada para colisionar. La misma idea explica que la ordenación rápida con pivote aleatorio cueste n log n en promedio pese a tener caso peor cuadrático.
Fórmula
familia universal: P(h(x) = h(y)) <= 1/m para x distinto de y ; ordenacion rapida con pivote aleatorio: E[T(n)] = O(n log n)
Ejemplo resuelto
Una tabla con 1000 posiciones y 1000 claves repartidas por una función universal deja una carga media de 1 clave por posición, y la longitud esperada de cada lista de colisiones también vale 1. Si en cambio la función toma los tres últimos dígitos de un identificador que siempre termina en tres ceros, todas las claves caen en la misma posición y la búsqueda pasa de constante a lineal.
Errores frecuentes
- Confundir el tiempo esperado con el caso peor: La ordenación rápida aleatorizada sigue teniendo caso peor cuadrático, aunque su probabilidad sea despreciable.
- Reutilizar una función de dispersión predecible en un servicio público: Un atacante que la conoce puede fabricar colisiones y degradar el servicio.
- Mezclar los dos tipos de algoritmo aleatorizado: Los de Las Vegas siempre aciertan y varían en tiempo, mientras que los de Monte Carlo tardan lo previsto y se equivocan con probabilidad pequeña.
Ejercicio
Una tabla de dispersión con 500 posiciones guarda 2000 claves bien repartidas. ¿Cuál es la longitud media de cada lista de colisiones?
Ver la solución
El factor de carga es el número de claves dividido entre el número de posiciones, es decir 2000 entre 500.
Respuesta: 4