C Academy · Lección

Redimensionamiento y factor de carga

Ajuste del rendimiento

Redimensionamiento y factor de carga es una lección gratuita de C Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.

Qué es el factor de carga

El factor de carga es la proporción entre las entradas almacenadas y las cubetas: alpha = size / capacity. Mide cuánto se ha llenado la tabla y afecta directamente al rendimiento.

Por qué importa el factor de carga

A medida que aumenta el factor de carga, las cubetas contienen cadenas más largas (o los sondeos se agrupan), por lo que las operaciones se ralentizan.

Alpha bajo: rápido, pero desperdicia memoria
Alpha alto: compacto, pero lento

Un objetivo habitual para el encadenamiento es 0.75.

Cálculo del factor de carga

Calcúlelo como una proporción de punto flotante para poder compararlo con un umbral.

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

Cuándo cambiar el tamaño

Después de cada inserción, compruebe si el factor de carga supera el umbral. Si es así, amplíe la tabla (normalmente duplicando su capacidad) y vuelva a calcular los hashes.

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

Explicación del rehashing

No puede copiar las cubetas directamente, porque el índice de cada clave depende de la capacidad. El rehashing vuelve a calcular la cubeta de cada clave con la nueva capacidad y la inserta de nuevo.

Una función para cambiar el tamaño

Asigne un nuevo arreglo de cubetas más grande; recorra cada nodo antiguo y muévalo al nuevo arreglo usando la nueva capacidad; después, intercambie los arreglos. Aquí se muestra el recálculo principal del índice.

#include <stdio.h>

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    const char *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

Mover nodos sin reasignar memoria

Con el encadenamiento puede mover los nodos existentes al nuevo arreglo en lugar de asignar otros nuevos. Separe cada nodo, vuelva a calcular su cubeta y antepóngalo.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

Estrategia de crecimiento

Duplicar la capacidad mantiene en O(1) el coste amortizado de las inserciones: aunque cambiar el tamaño cuesta O(n), ocurre con la suficiente poca frecuencia para que el coste medio por inserción permanezca constante.

Las potencias de dos también permiten utilizar la máscara AND rápida.

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

Reducción de tamaño

Opcionalmente, reduzca el tamaño cuando el factor de carga baje demasiado (por ejemplo, por debajo de 0.1) después de muchas eliminaciones. Reducir el tamaño recupera memoria, pero añade el coste de volver a calcular los hashes; hágalo con prudencia para evitar cambios de tamaño constantes.

Direccionamiento abierto y factor de carga

Las tablas con direccionamiento abierto son mucho más sensibles al factor de carga. El rendimiento se desploma cuando alpha se aproxima a 1, por lo que normalmente cambian de tamaño con valores entre 0.5 y 0.7, inferiores al 0.75 del encadenamiento.

Demostración del coste amortizado

Simule inserciones que duplican la capacidad al alcanzar 0.75 y cuente el trabajo total para mostrar que el promedio se mantiene bajo.

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

Comprobación rápida

Compruebe su comprensión del cambio de tamaño.

Resumen

Ha aprendido a ajustar el rendimiento de las tablas hash.

Factor de carga = tamaño / capacidad
Cambie el tamaño cuando supere un umbral (aproximadamente 0.75 para el encadenamiento)
Vuelva a calcular los hashes porque los índices dependen de la capacidad
Duplicar la capacidad proporciona inserciones O(1) amortizadas

Preguntas frecuentes

¿La lección «Redimensionamiento y factor de carga» es gratis?

Sí — el texto completo de «Redimensionamiento y factor de carga» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Redimensionamiento y factor de carga»?

Ajuste del rendimiento Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar C Academy?

No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «Redimensionamiento y factor de carga»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de C Academy?

Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a C Academy