¿Cómo calcular la longitud de búsqueda promedio de una tabla hash?

Para una tabla de búsqueda con n elementos de datos, la longitud promedio de una búsqueda exitosa es: ASL=∑PiCi (i=1, 2, 3,..., n), que puede entenderse simplemente usando expectativas matemáticas. Donde: Pi es la probabilidad del elemento de datos I-ésimo en la tabla de búsqueda, Ci es el número de veces que se compara el elemento de datos I-ésimo.

El promedio de búsquedas cuando el elemento a buscar no se encuentra en la tabla de búsqueda, pero la posición donde el elemento a buscar se encuentra en la tabla donde debería existir se llama promedio longitud de la búsqueda cuando la búsqueda no tiene éxito.

Datos extendidos

El proceso de búsqueda de la tabla hash es básicamente el mismo que el proceso de creación de la tabla. Algunos códigos clave se pueden encontrar directamente a través de la dirección convertida por la función hash. Algunos códigos clave entran en conflicto en la dirección obtenida por la función hash y deben encontrarse de acuerdo con el método de manejo de conflictos. Entre los tres métodos introducidos para manejar conflictos, encontrar conflictos sigue siendo un proceso de comparar un valor dado con el código clave. Por lo tanto, la medida de la eficiencia de la búsqueda en la tabla hash sigue siendo la longitud promedio de la búsqueda.

Durante el proceso de búsqueda, el número de comparaciones de códigos clave depende del número de conflictos. Si hay pocos conflictos, la eficiencia de la búsqueda será alta; si hay muchos conflictos, la eficiencia de la búsqueda será baja. Por lo tanto, los factores que afectan la cantidad de conflictos también son factores que afectan la eficiencia de la búsqueda. Hay tres factores que afectarán la cantidad de conflictos:

1. Si la función hash es consistente

2. El método de manejo de conflictos. 3. Factor de relleno de la tabla hash.

El factor de relleno de una tabla hash se define como: α = número de elementos rellenos en la tabla/longitud de la tabla hash.

α es el factor de signo del grado de llenado de la tabla hash. Debido a que la longitud de la tabla es un valor fijo, α es proporcional al número de elementos completados en la tabla, por lo que cuanto mayor es α, más elementos se completan en la tabla y mayor es la posibilidad de conflicto, cuanto menor es α; es decir, cuantos más elementos se completen en la tabla, cuanto menos elementos haya, es menos probable que entren en conflicto.

De hecho, la longitud de búsqueda promedio de la tabla hash es una función del factor de llenado α, pero los métodos para manejar conflictos son diferentes y los efectos son diferentes.

Enciclopedia Baidu: longitud promedio de búsqueda

Enciclopedia Baidu: tabla hash