C++ Academy · Урок

Вопросы производительности

Корзины и коэффициент загрузки

«Вопросы производительности» — бесплатный урок C++ Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C++ Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C++ Academy содержит 4 уроков всего.

Как хеш-таблицы хранят данные

Неупорядоченный контейнер содержит массив корзин. Хеш ключа выбирает корзину; несколько ключей в одной корзине образуют цепочку, которая просматривается линейно.

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

Какая корзина

bucket(key) сообщает, в какую корзину сейчас отображается ключ.

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

Коэффициент заполнения

Коэффициент заполнения вычисляется как size / bucket_count. При большем коэффициенте цепочки становятся длиннее, а поиск — медленнее.

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

Максимальный коэффициент заполнения

max_load_factor() задаёт порог. Когда коэффициент заполнения превышает его, таблица выполняет перехеширование и увеличивает количество корзин.

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

Перехеширование

Перехеширование перестраивает таблицу с большим количеством корзин и является затратной операцией. Оно происходит автоматически, когда превышен коэффициент заполнения.

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

Резервирование для предотвращения перехеширования

Если размер заранее известен, вызовите reserve(n), чтобы предварительно выделить корзины и избежать повторного перехеширования.

#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

rehash(n) устанавливает количество корзин не меньше n. Используйте reserve для количества элементов, а rehash — для количества корзин.

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

Проверка размеров корзин

bucket_size(i) показывает, сколько элементов находится в корзине i. Это полезно для диагностики коллизий.

#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(n)

При плохом хеше с большим количеством коллизий все ключи выстраиваются в одну корзину, и сложность операций ухудшается до линейного времени. Хороший хеш сохраняет сложность 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;
}

Уменьшение максимального коэффициента заполнения

Установка меньшего значения max_load_factor позволяет обменять память на скорость: коллизий становится меньше, но корзин — больше.

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

Инвалидация итераторов

Перехеширование делает итераторы недействительными, но сохраняет действительность ссылок и указателей на элементы. Планируйте циклы с учётом этого.

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

Быстрая проверка

Проверьте, насколько хорошо Вы понимаете производительность хеш-таблиц.

Итоги

Вы изучили внутреннее устройство хеш-таблиц:

ключи сопоставляются с корзинами; при коллизиях образуются цепочки
коэффициент заполнения = размер / количество корзин; при превышении max_load_factor выполняется перехеширование
используйте reserve, чтобы избежать перехеширования; перехеширование делает итераторы недействительными, но не влияет на ссылки

Следующий курс: чтение и запись файлов с помощью fstream.

Часто задаваемые вопросы

Урок «Вопросы производительности» бесплатный?

Да — полный текст урока «Вопросы производительности» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C++ Academy, подпишись на CoddyKit PRO. Курс C++ Academy содержит 4 уроков всего.

Чему я научусь в уроке «Вопросы производительности»?

Корзины и коэффициент загрузки Ты практикуешь C++ Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C++ Academy?

Предыдущий опыт не требуется. C++ Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Вопросы производительности»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C++ Academy?

Да. Каждый урок C++ Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C++ Academy