Как выбрать структуру данных под задачу?

Структуру выбирают от доминирующих операций: что чаще — поиск, вставка, порядковая обработка или диапазонные запросы — под ту операцию и берут структуру; универсальной не существует.

Шпаргалка по операциям

• Частый contains и поиск по ключу — хеш-таблица, средний O(1).
• Отсортированный порядок и диапазоны «все от 5 до 10» — сбалансированное дерево, O(log n).
• Минимум или максимум на лету — куча; строгий порядок обработки — очередь или стек.
• Строковые префиксные запросы — trie; взаимосвязи объектов — граф.

Вопросы себе при выборе

1. Каких операций больше и какова целевая сложность каждой?
2. Нужен порядок ключей или достаточно проверки равенства?
3. Сколько данных и сколько памяти доступно?
4. Важны ли константы и локальность кеша? Часто простой массив бьёт «умные» структуры.

Пример рассуждения

«Хранить последние N запросов с быстрой проверкой дубликата» — кольцевой буфер плюс хеш-множество: и порядок, и O(1) на contains.

Коротко для собеседования

Сначала выписываешь, какие операции доминируют и с какой сложностью они нужны, и только потом выбираешь структуру: хеш для поиска по ключу, дерево для порядка и диапазонов, куча для минимума. Хеш-таблица проигрывает дереву на range-запросах и упорядоченном обходе, а на малых данных простой массив часто быстрее всех.