C Academy · Aula

Redimensionamento e fator de carga

Ajuste de desempenho.

Redimensionamento e fator de carga é uma aula grátis de C Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.

O que é o fator de carga

O fator de carga é a proporção entre as entradas armazenadas e os compartimentos: alpha = size / capacity. Ele mede o grau de ocupação da tabela e afeta diretamente o desempenho.

Por que o fator de carga é importante

À medida que o fator de carga aumenta, os compartimentos contêm cadeias mais longas (ou as sondagens ficam agrupadas), fazendo as operações ficarem mais lentas.

Alpha baixo: rápido, mas desperdiça memória
Alpha alto: compacto, mas lento

Um alvo comum para o encadeamento é 0.75.

Calculando o fator de carga

Calcule-o como uma proporção de ponto flutuante para poder compará-lo com um limite.

#include <stdio.h>

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

Quando redimensionar

Após cada inserção, verifique se o fator de carga excede o limite. Em caso afirmativo, aumente a tabela (geralmente dobrando a capacidade) e refaça o hash.

#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;
}

Explicando o refazimento do hash

Você não pode copiar os compartimentos às cegas, pois o índice de cada chave depende da capacidade. O refazimento do hash recalcula o compartimento de cada chave com base na nova capacidade e a reinsere.

Uma função de redimensionamento

Alocamos um novo vetor de compartimentos maior; percorremos cada nó antigo e o movemos para o novo vetor usando a nova capacidade; depois trocamos os vetores. Aqui está o recálculo principal do í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;
}

Movendo nós sem realocá-los

Com encadeamento, você pode mover os nós existentes para o novo vetor em vez de alocar novos nós. Separe cada nó, recalcule seu compartimento e anteponha-o.

#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;
}

Estratégia de crescimento

Dobrar a capacidade mantém o custo amortizado de inserção em O(1): embora um redimensionamento custe O(n), ele ocorre com frequência suficientemente baixa para que o custo médio por inserção permaneça constante.

Potências de dois também permitem usar a 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;
}

Redução

Opcionalmente, reduza a tabela quando o fator de carga ficar baixo demais (por exemplo, abaixo de 0.1) após muitas exclusões. A redução recupera memória, mas acrescenta o custo de refazer o hash; portanto, faça-a com cautela para evitar redimensionamentos repetidos.

Endereçamento aberto e fator de carga

Tabelas com endereçamento aberto são muito mais sensíveis ao fator de carga. O desempenho desaba à medida que alpha se aproxima de 1; por isso, elas normalmente são redimensionadas entre 0.5 e 0.7, abaixo de 0.75 no encadeamento.

Demonstração do custo amortizado

Simule inserções que dobram a capacidade em 0.75 e conte o trabalho total, mostrando que a média permanece baixa.

#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;
}

Verificação rápida

Teste sua compreensão sobre redimensionamento.

Recapitulação

Você aprendeu a ajustar o desempenho de tabelas hash.

Fator de carga = tamanho / capacidade
Redimensione quando ele exceder um limite (cerca de 0.75 para encadeamento)
Refaça o hash porque os índices dependem da capacidade
Dobrar a capacidade proporciona inserções amortizadas em O(1)

Perguntas Frequentes

A aula “Redimensionamento e fator de carga” é grátis?

Sim — o texto completo de “Redimensionamento e fator de carga” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.

O que vou aprender em “Redimensionamento e fator de carga”?

Ajuste de desempenho. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar C Academy?

Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.

Quanto tempo leva a aula “Redimensionamento e fator de carga”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de C Academy?

Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

← Voltar para C Academy