¿Elegir de manera eficiente un elemento aleatorio de una tabla hash encadenada?

Question

Sólo por la práctica (y no como una tarea) He estado tratando de resolver este problema (CLRS, 3ª edición, el ejercicio 11,2-6):

Supongamos que tenemos almacenados n claves en una tabla hash de tamaño m, con colisiones resueltas por encadenamiento, y que sabemos la longitud de cada cadena , incluida la longitud L de la cadena más larga. Describa un procedimiento que selecciona una clave uniformemente al azar entre las claves en la tabla hash y la devuelve en el tiempo esperado O (L * (1 + m/n)).

Lo que pensé hasta ahora es que la probabilidad de que se devuelva cada tecla es 1/n. Si tratamos de obtener un valor aleatorio x entre 1 an, y tratamos de encontrar la clave xth en secuencia ordenada primero por cubo, entonces a lo largo de la cadena en el cubo, entonces tomará O (m) para encontrar el cubo correcto yendo a través de cubos uno por uno y O (L) tiempo para obtener la llave correcta en la cadena.

Answer 1

repita los pasos siguientes hasta que un elemento se devuelve:

• seleccionará aleatoriamente un cubo. Deje k la cantidad de elementos en el depósito.
• Seleccione p uniformemente al azar desde 1 ... L. Si p <= k devuelve el elemento p en el cubo.

Debe estar claro que el procedimiento devuelve un elemento uniformemente al azar. Estamos aplicando el muestreo de rechazo a los elementos colocados en una matriz 2D.

El número esperado de elementos por depósito es n/m. La probabilidad de que el intento de muestreo sea exitoso es (n/m)/L. El número esperado de intentos necesarios para encontrar un segmento es, por lo tanto, L * m/n. Junto con el costo O(L) de recuperar el elemento del depósito, el tiempo de ejecución esperado es O(L * (1 + m/n)).