se eliminan las entradas contadas en el factor de carga de una tabla hash utilizando direccionamiento abierto

Question

Al calcular el factor de carga de un hashtable con una implementación de matriz de dirección abierta, estoy usando:

numberOfKeysInArray/sizeOfArray

Sin embargo, se me ocurrió que, dado que las entradas eliminadas deben marcarse como tales (para distinguirlos de los espacios vacíos), podría tener sentido incluirlas en el número de claves.

Mi pensamiento es que en cuanto a estimar el número promedio de sondas para encontrar una entrada, las entradas eliminadas deben contar para el factor de carga, pero en cuanto a insertar una nueva clave, no deberían.

¿Cuál es el cálculo adecuado: incluyendo claves eliminadas o no?

Answer 1

No, por definición, el factor de carga es la relación entre el número de elementos y el tamaño de la matriz de deseos. Ver EG Wikipedia o esta conferencia.

También habría un problema práctico con el recuento de entradas eliminadas en el factor de carga. La mayoría de las implementaciones tienen un factor de carga máximo. Si realiza el máximo de superar el máximo permitido, se incrementa el tamaño de la matriz de respaldo. Si las entradas eliminadas se cuentan para un factor de carga más alto, esto podría causar un aumento innecesario del tamaño de la matriz para una tabla de contenido casi vacía pero alta en los escombros.