Saltar al contenido

Modelo por capas

Factor de carga

El factor de carga es la cantidad de claves dividida entre la cantidad de cubetas:

Texto
carga ← n / capacidad

Con encadenamiento, es la longitud media de una cadena. Para que buscar siga siendo O(1) esperado, la carga tiene que mantenerse acotada por una constante.

Factor de carga de una tabla con encadenamientoTabla de 8 cubetas. La cubeta 2 tiene la clave 2; la cubeta 5 tiene 5, 13 y 21; las otras seis están vacías. Hay 4 claves en 8 cubetas: la carga es 4 dividido entre 8, es decir 0,5, que también es la longitud media de las 8 cadenas.cubetas (capacidad 8)01223455132167n = 4 clavescapacidad = 8 cubetascarga = 4 / 8 = 0,5longitud de cada cadena:0, 0, 1, 0, 0, 3, 0, 0 → media 0,5
Cuatro claves en ocho cubetas: la carga es 0,5, aunque una cadena tenga tres claves y varias cubetas ninguna.

Por eso la tabla fija un límite de carga (por ejemplo, 1 con encadenamiento, o menos con direccionamiento abierto). Cuando una inserción lo supera, la tabla crece: normalmente duplica sus cubetas.

Una tabla con 16 cubetas y límite de carga 0,75 ya tiene 12 claves. Insertas la 13.ª. ¿Qué pasa?