Calculadora del Factor de Carga de una Tabla Hash (Sondeos Esperados: Lineal, Doble, Encadenamiento)
El factor de carga de una tabla hash y el número medio de sondeos de una búsqueda —en sondeo lineal, doble hash y encadenamiento— más el tamaño de tabla que la mantiene por debajo de una carga elegida.
Resultados
La línea discontinua marca el valor que ha escrito.
Qué hace esta herramienta
Una tabla hash solo es rápida mientras no está demasiado llena. Con sondeo lineal, buscar una clave que no existe cuesta de media 2,5 sondeos con factor de carga 0,5, pero 50,5 con 0,9; el doble hash es más suave (10 a 0,9) y el encadenamiento se degrada poco a poco, pues una carga superior a 1 solo significa cadenas más largas. Las tablas de direccionamiento abierto se redimensionan por eso mucho antes de llenarse, a menudo entre el 50 % y el 75 % de carga. Son los promedios de Knuth para una buena función hash.
Fórmula
α = n ÷ m · linear probing: hit ½(1 + 1/(1−α)), miss ½(1 + 1/(1−α)²) · double hashing: hit (1/α) ln(1/(1−α)), miss 1/(1−α) · chaining: hit 1 + α/2, miss α
Variables
| Símbolo | Significado | Unidad |
|---|---|---|
n | Elementos almacenados | — |
m | Tamaño de la tabla (posiciones o cubos) | — |
ml | Mayor factor de carga que quiere permitir | — |
LU | Sondeo lineal: sondeos si el elemento no existe | — |
LF | Factor de carga α (elementos ÷ posiciones) | — |
LS | Sondeo lineal: sondeos para encontrar un elemento | — |
DS | Doble hash: sondeos para encontrar un elemento | — |
DU | Doble hash: sondeos si el elemento no existe | — |
CS | Encadenamiento: comparaciones para encontrar un elemento | — |
CU | Encadenamiento: comparaciones si el elemento no existe | — |
SZ | Tamaño de la tabla que mantiene la carga en su límite | — |
Ejemplo resuelto
- Elementos almacenados700
- Tamaño de la tabla (posiciones o cubos)1000
- Mayor factor de carga que quiere permitir0,7
- Sondeo lineal: sondeos si el elemento no existe6,06
- Factor de carga α (elementos ÷ posiciones)0,700
- Sondeo lineal: sondeos para encontrar un elemento2,17
- Doble hash: sondeos para encontrar un elemento1,72
- Doble hash: sondeos si el elemento no existe3,33
- Encadenamiento: comparaciones para encontrar un elemento1,35
- Encadenamiento: comparaciones si el elemento no existe0,70
- Tamaño de la tabla que mantiene la carga en su límite1000
Limitaciones
- La fórmula supone condiciones ideales: sin pérdidas por fricción, sin resistencia del aire y sin pérdidas de rendimiento salvo que las introduzca.
- El resultado es una estimación basada solo en los valores introducidos. Las situaciones reales suelen incluir factores que esta calculadora desconoce.