Ответ
Плюсы:
- Средняя сложность O(1): Вставка, удаление и поиск выполняются за константное время при хорошей хеш-функции и отсутствии переполнения.
- Гибкость: Может хранить пары ключ-значение практически любых типов.
- Эффективность для несортированных данных: Идеальна для задач, где важен быстрый доступ, а не порядок элементов.
Минусы:
- Коллизии: Плохая хеш-функция или высокая заполненность ведут к коллизиям, что деградирует производительность до O(n) в худшем случае.
- Отсутствие порядка: Элементы не упорядочены по ключу. Для обхода в отсортированном порядке требуется дополнительная сортировка.
- Непредсказуемость производительности: Зависит от качества хеш-функции и стратегии разрешения коллизий (цепочки, открытая адресация).
- Больший расход памяти: По сравнению с массивами, часто требуется резервирование буфера для минимизации коллизий.
Пример на C++ (std::unordered_map):
#include <unordered_map>
#include <iostream>
#include <string>
int main() {
// Хеш-таблица для хранения рейтингов игроков
std::unordered_map<std::string, int> player_scores;
// Вставка (в среднем O(1))
player_scores["Alice"] = 2500;
player_scores["Bob"] = 1800;
player_scores.emplace("Charlie", 2100);
// Поиск (в среднем O(1))
auto it = player_scores.find("Alice");
if (it != player_scores.end()) {
std::cout << "Alice's score: " << it->second << 'n'; // 2500
}
// Обход (элементы в произвольном порядке)
for (const auto& [name, score] : player_scores) {
std::cout << name << ": " << score << 'n';
}
return 0;
}