C++ Academy · Lección

Consideraciones de rendimiento

Buckets y factor de carga

Consideraciones de rendimiento 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.

Cómo almacenan datos las tablas hash

Un contenedor no ordenado contiene un array de buckets. El hash de una clave selecciona un bucket; varias claves en un mismo bucket forman una cadena que se busca linealmente.

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

¿Qué bucket?

bucket(key) indica en qué índice de bucket se encuentra actualmente una clave.

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

Factor de carga

El factor de carga es size / bucket_count. Una carga mayor implica cadenas más largas y búsquedas más 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;
}

Factor de carga máximo

max_load_factor() es el umbral. Cuando el factor de carga lo supera, la tabla hace un rehash usando más 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;
}

Rehashing

El rehashing reconstruye la tabla con más buckets y es costoso. Se produce automáticamente cuando se supera el factor de carga.

#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 rehashes

Si conoce de antemano el tamaño, llame a reserve(n) para preasignar buckets y evitar rehashes repetidos.

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

Usar rehash directamente

rehash(n) establece el número de buckets en al menos n. Use reserve para las cantidades de elementos y rehash para las cantidades 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;
}

Inspeccionar los tamaños de los buckets

bucket_size(i) muestra cuántos elementos comparten el bucket i, lo que resulta útil para diagnosticar colisiones.

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

El peor caso es O(n)

Con un hash deficiente que produce muchas colisiones, todas las claves forman una cadena en un solo bucket y las operaciones se degradan a un tiempo lineal. Un buen hash mantiene el rendimiento en 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;
}

Reducir el factor de carga máximo

Establecer un max_load_factor menor intercambia memoria por velocidad: hay menos colisiones, pero más 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;
}

Invalidación de iteradores

Un rehash invalida los iteradores, pero mantiene válidas las referencias y los punteros a los elementos. Planifique los bucles en consecuencia.

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

Comprobación rápida

Compruebe su comprensión del rendimiento de las tablas hash.

Resumen

Ha aprendido los detalles internos de las tablas hash:

las claves se asignan a cubetas; las colisiones forman cadenas
el factor de carga = size / bucket_count; al superar max_load_factor se activa un rehash
use reserve para evitar el rehashing; un rehash invalida los iteradores, pero no las referencias

Siguiente curso: lectura y escritura de archivos con fstream.

Preguntas frecuentes

¿La lección «Consideraciones de rendimiento» es gratis?

Sí — el texto completo de «Consideraciones de rendimiento» 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 «Consideraciones de rendimiento»?

Buckets y factor de carga 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 «Consideraciones de rendimiento»?

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