C++ Academy · Aula

Considerações de desempenho

Buckets e fator de carga

Considerações de desempenho é 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.

Como as tabelas de dispersão armazenam dados

Um contêiner não ordenado contém uma matriz de compartimentos. A dispersão de uma chave escolhe um compartimento; várias chaves em um compartimento formam uma cadeia pesquisada linearmente.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

Qual bucket

bucket(key) informa para qual índice de bucket uma chave é mapeada no momento.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

Fator de carga

O fator de carga é size / bucket_count. Uma carga maior significa cadeias mais longas e buscas mais lentas.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

Fator de carga máximo

max_load_factor() é o limite. Quando o fator de carga o excede, a tabela refaz a dispersão usando mais buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

Refazer a dispersão

Refazer a dispersão reconstrói a tabela com mais buckets e é dispendioso. Isso acontece automaticamente quando o fator de carga é excedido.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

Usar reserve para evitar novas dispersões

Se você souber o tamanho antecipadamente, chame reserve(n) para pré-alocar buckets e evitar refazer a dispersão repetidamente.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

rehash diretamente

rehash(n) define a quantidade de buckets como pelo menos n. Use reserve para quantidades de elementos e rehash para quantidades de buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

Inspecionar os tamanhos dos buckets

bucket_size(i) revela quantos elementos compartilham o bucket i, o que é útil para diagnosticar colisões.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

O pior caso é O(n)

Com uma função de dispersão ruim que causa muitas colisões, todas as chaves formam uma cadeia em um único bucket, e as operações acabam levando tempo linear. Uma boa função de dispersão mantém o desempenho em O(1).

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

Reduzir o fator de carga máximo

Definir um max_load_factor menor troca memória por velocidade: há menos colisões, mas mais buckets.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

Invalidação de iteradores

Refazer a dispersão invalida os iteradores, mas mantém válidas as referências e os ponteiros para os elementos. Planeje os percursos adequadamente.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

Verificação rápida

Teste sua compreensão sobre o desempenho de tabelas hash.

Recapitulação

Você aprendeu os detalhes internos das tabelas hash:

as chaves são mapeadas para baldes; as colisões formam cadeias
fator de carga = tamanho / quantidade_de_baldes; ultrapassar max_load_factor aciona uma reorganização da tabela
use reserve para evitar reorganizações; uma reorganização invalida os iteradores, mas não as referências

Próximo curso: leitura e escrita de arquivos com fstream.

Perguntas Frequentes

A aula “Considerações de desempenho” é grátis?

Sim — o texto completo de “Considerações de desempenho” é 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 “Considerações de desempenho”?

Buckets e fator de carga 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 “Considerações de desempenho”?

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