¿Cuál es la explicación rigurosa de por qué n / m es el factor de carga en una tabla hash?

La forma en que entendí es la siguiente:

El factor de carga es cuánto puede ser la longitud de una ranura mientras se realiza el hashing. El peor de los casos que conocemos sería n (todos los números en esa ranura) y el mínimo es 1 número. Queremos saber qué puede ser en promedio.

Suposición: Suponemos que cualquier número de n puede asignarse a la ranura m. 1 / m de probabilidad de que se asigne a un espacio determinado

Suponemos que cualquier número de n puede asignarse a la ranura m. Y las asignaciones entre n números son independientes. Ahora el factor de carga, que es la longitud promedio de una ranura que puede ser, es

Diga SLOT 1, si se le asigna un número, la variable aleatoria es 1, y si no es cero. P (Éxito) = p = 1 / m, P (Fracaso) = q = (m-1) / m

Esto forma una distribución binomial sobre cuál podría ser la longitud de una ranura, y esa expectativa de distribución binomial es np, donde p aquí es 1 / m, por lo tanto n / m.

Una mejor explicación podría ser la prueba del Teorema 11.2 del libro CLRS en el capítulo Hash Tables.

El factor de carga de una tabla hash indica qué tan lleno está. Entonces, si [math] n [/ math] es el número actual de entradas y [math] m [/ math] es el tamaño actual, entonces, sí, [math] \ frac {n} {m} [/ math] es El factor de carga. En Java se puede especificar el factor de carga cuando se construye la tabla hast. Lo que esto significa es que la tabla crecerá si el factor de carga se vuelve más alto que el factor de carga. ¿Por qué? porque a medida que la tabla se llena, hay una mayor probabilidad de colisiones (es decir, que cuando inserte una nueva entrada, ya habrá una con el mismo código hash). Las colisiones deben resolverse (esto podría ser, por ejemplo, mediante encadenamiento, o simplemente buscando desde donde se realizó la inserción hasta que haya un espacio vacío). Básicamente, existe una compensación entre el gasto de colisiones (tiempo y posible costo de memoria), asignando una tabla grande para comenzar (costo de memoria) y expansión (costo de tiempo).

Si no tiene limitaciones de memoria, una buena estrategia general es asignar una tabla que sea al menos dos veces mayor que la cantidad de elementos esperados. Si eso es demasiado grande, haga una suposición razonable.

Debe definir sus términos en términos inequívocos, alguna notación. Una tabla hash genérica puede cubrir todas las implementaciones. Luego, con una exigencia verbal, muestra la “carga”. ¿Cómo se sigue la carga de las definiciones?