Структуры данных — итоги
Play ITЗагрузка интерактивного демо…
Кратко — что стоит унести из раздела "Структуры данных". Если пункт кажется туманным — откройте указанную главу или оглавление.
FAQ — Часто задаваемые вопросы
Типичные ошибки выбора структуры и симптомы на практике. Здесь — что делать и где копать в главах; определения для зачёта — в чек-листе.
Вопрос. Вставка в середину списка из миллиона элементов "зависает" на секунды.
Ответ. В динамическом массиве вставка в середину — O(n) из-за сдвига элементов. Для частых вставок в середину — связный список или balanced tree; для append в конец — массив достаточен. Подробнее здесь — Реализация и O(·).
Вопрос. list.pop(0) в Python на большом списке стал катастрофически медленным.
Ответ. list — массив; удаление с начала сдвигает все элементы — O(n). Для очереди используйте collections.deque. Подробнее здесь — Реализация и O(·).
Вопрос. Рекурсивная функция упала с StackOverflowError на "небольшом" дереве.
Ответ. Каждый вызов кладёт кадр в стек — глубина ограничена (обычно тысячи). Перепишите на итерацию с явным стеком или увеличьте лимит только осознанно. Подробнее здесь — Структуры данных.
Вопрос. Хеш-таблица внезапно стала в 100 раз медленнее на том же объёме данных.
Ответ. Вероятна деградация до O(n) из-за коллизий (плохая хеш-функция, атака на hash-flooding, переполненные корзины). Проверьте load factor, rehash, качество hashCode/__hash__. Подробнее здесь — Реализация и O(·).
Вопрос. Объект в HashMap изменили после вставки — ключ "пропал" из map.
Ответ. Индекс корзины зависит от hash ключа; мутация полей, участвующих в hash, ломает контракт. Ключи делайте immutable или не меняйте их после put. Подробнее здесь — Реализация и O(·).
Вопрос. "Нужен словарь" — поставил массив пар и поиск стал O(n).
Ответ. Модель "ключ–значение" требует индекса по ключу — хеш-таблица или дерево. Линейный список пар годится только для десятков элементов. Подробнее здесь — Структуры данных.
Вопрос. Отсортировал массив, а потом ищу бинарным поиском — иногда "не находит".
Ответ. Бинарный поиск работает только на отсортированном массиве с тем же компаратором, что и сортировка. После вставки нового элемента порядок нарушен — нужна пересортировка или дерево поиска. Подробнее здесь — Реализация и O(·).
Вопрос. BFS по графу "застревает" или ест гигабайты памяти.
Ответ. Очередь BFS хранит все вершины текущего уровня; на плотном графе это дорого. Проверьте представление графа (список смежности vs матрица), лимит глубины, visited-множество. Подробнее здесь — Структуры данных, Реализация и O(·).
Вопрос. DFS рекурсией на графе с циклом ушёл в бесконечность.
Ответ. Без множества посещённых или маркировки "в процессе" цикл заставит обход повторять вершины. Для поиска циклов — цвета white/gray/black или union-find. Подробнее здесь — Структуры данных.
Вопрос. Матрица смежности 50 000 × 50 000 "не влезает" в RAM.
Ответ. Плотная матрица — O(V²) памяти. Для разрежённого графа — список смежности или CSR. Подробнее здесь — Реализация и O(·).
Вопрос. Приоритетная очередь на отсортированном массиве тормозит при каждой вставке.
Ответ. Вставка в отсортированный массив — O(n). Используйте бинарную кучу — O(log n) на insert/extract. Подробнее здесь — Реализация и O(·).
Вопрос. Фильтр Блума говорит "элемент есть", а в базе его нет.
Ответ. Ложноположительные срабатывания — нормальное свойство Bloom filter; ложноотрицательных нет. Подтверждайте попадание полным поиском в хранилище. Подробнее здесь — Реализация и O(·).
Вопрос. Кэш LRU на LinkedHashMap вытесняет "нужные" ключи после деплоя.
Ответ. Проверьте ёмкость и политику доступа (access-order vs insertion-order). Холодный старт после рестарта — все промахи; прогрейте кэш или увеличьте TTL. Подробнее здесь — Реализация и O(·).
Вопрос. Дерево поиска выродилось в "палку" — поиск O(n) вместо O(log n).
Ответ. Вставка отсортированных ключей в простое BST даёт цепочку. Нужно AVL, красно-чёрное дерево или случайный порядок вставки / treap. Подробнее здесь — Реализация и O(·).
Вопрос. Индекс БД "не используется", хотя я создал B-tree на столбце.
Ответ. Оптимизатор может выбрать seq scan при низкой селективности, функции на столбце (WHERE UPPER(name)), неактуальной статистике. Смотрите EXPLAIN. Подробнее здесь — §11.2 — индексы СУБД, Как СУБД выполняет запрос.
Вопрос. R-дерево в GIS возвращает лишние объекты при запросе "внутри прямоугольника".
Ответ. R-tree даёт кандидатов по ограничивающим прямоугольникам; точный фильтр — вторым этапом. Это ожидаемо; без второго шага будут false positives. Подробнее здесь — Геометрия.
Вопрос. Путаю "стек" в алгоритмах и "стек вызовов" в отладчике.
Ответ. Структура данных стек (LIFO) — абстракция; стек вызовов ОС — её применение для return-адресов. Оба работают "последним вошёл — первым вышел", но это разные уровни. Подробнее здесь — Структуры данных.
Вопрос. Set удаляет дубликаты, но порядок элементов "прыгает".
Ответ. Хеш-множество не гарантирует порядок обхода. Нужен порядок вставки — LinkedHashSet; сортировка — TreeSet. Подробнее здесь — Коллекции в разделах языков.
Вопрос. Динамический массив "дёргается" по памяти при каждом push.
Ответ. При переполнении capacity массив реаллоцируется с запасом (обычно ×2) — редкие дорогие копии, частые дешёвые append. Резервируйте reserve() заранее, если размер известен. Подробнее здесь — Реализация и O(·).
Вопрос. Skip list в Redis ZSET — зачем, если есть деревья?
Ответ. Skip list проще для конкурентной записи и диапазонных запросов с предсказуемой latency; сравним с balanced tree по асимптотике. В LSM memtable — та же идея уровней указателей. Подробнее здесь — Реализация и O(·).
Вопрос. Выбрал ArrayList для частого удаления из середины — код стал неприемлемым на проде.
Ответ. Сначала составьте список операций и частоту, затем сверьтесь с таблицей O(·). "Универсального лучшего" массива нет — есть подходящий под нагрузку. Подробнее здесь — Структуры данных, Реализация и O(·).
Вопрос. Union-Find "не находит" компоненту связности после merge.
Ответ. Проверьте path compression и union by rank; без них структура деградирует. Убедитесь, что find и union используют одну и ту же родительскую таблицу. Подробнее здесь — Реализация и O(·).
Вопрос. Trie "съел" память на коротких ключах из случайных UUID.
Ответ. Префиксное дерево выгодно при общих префиксах; случайные длинные ключи дают глубокое разреженное дерево. Для UUID — хеш-таблица. Подробнее здесь — Структуры данных.
Вопрос. На собеседовании просят "реализовать hash map" — с чего начать новичку?
Ответ. Массив корзин + linked list в корзине + hash + equals + rehash при load factor. Сначала алгоритмический справочник, затем код на знакомом языке. Подробнее здесь — Реализация и O(·).
Вопрос. Count-Min Sketch показывает частоту выше реальной — баг?
Ответ. Оценка всегда завышена (или равна) из-за коллизий в sketch — это компромисс памяти. Для точного счёта нужен полный hash map. Подробнее здесь — Реализация и O(·).
Вопрос. Двумерный массив array[i][j] тормозит при обходе j во внешнем цикле.
Ответ. У jagged-массива строки не непрерывны в памяти; у прямоугольного — обход по строкам cache-friendly. Меняйте порядок циклов или используйте flat buffer. Подробнее здесь — Реализация и O(·).
Вопрос. "Граф микросервисов" в архитектуре — это то же, что граф в коде?
Ответ. Одна абстракция связей, разная инженерия: в памяти — указатели и O(·); в сети — latency, retries, circuit breaker. Алгоритмы обхода переносятся, метрики — другие. Подробнее здесь — Структуры данных.
Вопрос. Кольцевой буфер перезаписал старые данные — потребитель "пропустил" сообщения.
Ответ. При переполнении без блокировки producer затирает head — by design для real-time. Нужна backpressure, больший буфер или отдельная очередь с ACK. Подробнее здесь — Реализация и O(·).
Вопрос. HyperLogLog в аналитике показывает 1,2 млн уников, точный count — 1,05 млн.
Ответ. HLL — приближённая оценка с фиксированной памятью (~1–2 % ошибки). Для биллинга нужен точный distinct; для дашборда — достаточно. Подробнее здесь — Реализация и O(·).
Вопрос. Что такое структура данных простыми словами?
Ответ. Способ организовать данные в памяти, чтобы нужные операции (поиск, вставка, обход) были быстрыми. Массив, список, дерево и хеш-таблица — разные компромиссы. Подробнее здесь — Структуры данных.
Вопрос. Массив или связный список — что выбрать?
Ответ. Массив — O(1) доступ по индексу, дорогая вставка в середину. Список — O(1) вставка при известном узле, O(n) доступ. Частый append — динамический массив; частые вставки в середину — список или дерево. Подробнее здесь — Реализация и O(·).
Вопрос. Что такое хеш-таблица (hash map) и как она работает?
Ответ. Ключ прогоняют через хеш-функцию → индекс корзины → значение. В среднем поиск O(1); при коллизиях — цепочки или открытая адресация. Подробнее здесь — Реализация и O(·).
Вопрос. Stack и Queue — в чём разница?
Ответ. Стек (LIFO) — последний вошёл, первый вышел (undo, вызовы функций). Очередь (FIFO) — первый вошёл, первый вышел (задачи, BFS). Подробнее здесь — Структуры данных.
Вопрос. Что такое Big O notation и зачем она программисту?
Ответ. O(·) описывает, как растёт время или память при увеличении n. O(1), O(log n), O(n) — язык сравнения алгоритмов и структур. Подробнее здесь — Реализация и O(·), Нотация Большое O, Lab / Big-O — 1128.
Вопрос. Бинарное дерево поиска (BST) — что это?
Ответ. У каждого узла левые потомки меньше, правые больше; поиск в сбалансированном дереве — O(log n). Несбалансированное BST вырождается в список. Подробнее здесь — Реализация и O(·).
Вопрос. B-tree и B+ tree — зачем они в PostgreSQL и MySQL?
Ответ. Широкие узлы под размер страницы диска; мало обращений к диску на поиск и диапазон. B⁺-дерево хранит данные в листьях со связным списком — быстрые range scan. Подробнее здесь — §7 — B- и B⁺-дерево, Как СУБД выполняет запрос.
Вопрос. Что такое очередь с приоритетом (priority queue)?
Ответ. Структура, где каждый раз извлекают элемент с наивысшим приоритетом. Обычно реализуют бинарной кучей — O(log n) на insert/extract. Подробнее здесь — Реализация и O(·).
Вопрос. Dictionary vs Set в Python — когда что использовать?
Ответ. dict — ключ → значение (хеш-таблица). set — только уникальные ключи без значений; быстрая проверка принадлежности O(1) в среднем. Подробнее здесь — Коллекции Python, Структуры данных.
Вопрос. Граф: список смежности или матрица смежности?
Ответ. Матрица — O(1) проверка ребра, O(V²) памяти. Список смежности — O(deg) обход соседей, экономия на разреженных графах. Подробнее здесь — Реализация и O(·).
Вопрос. Алгоритм Дейкстры — какая структура данных нужна?
Ответ. Кратчайшие пути от источника: приоритетная очередь (куча) + список смежности взвешенного графа. Без отрицательных весов. Подробнее здесь — Реализация и O(·), Алгоритмы.
Вопрос. Что такое коллизия в хеш-таблице?
Ответ. Два разных ключа дали один индекс корзины. Решают цепочками (список в bucket) или пробированием (linear/quadratic probing). Подробнее здесь — Реализация и O(·).
Вопрос. Фильтр Блума — что это и где применяют?
Ответ. Компактная вероятностная структура: "точно нет" или "возможно да". Используют в кэшах, БД, CDN перед дорогим поиском. Подробнее здесь — Реализация и O(·).
Вопрос. Skip list — почему Redis использует его в ZSET?
Ответ. Skip list даёт O(log n) поиск и диапазон с проще конкурентной записью, чем у balanced tree. Уровни указателей — как "экспресс-лестницы". Подробнее здесь — §10 — skip list.
Вопрос. ArrayList vs LinkedList в Java — что быстрее?
Ответ. ArrayList — быстрый get/set по индексу; LinkedList — вставки в середину при итераторе. Для большинства задач достаточно ArrayList. Подробнее здесь — Коллекции Java, Реализация и O(·).
Вопрос. Что такое deque (дек) и чем он отличается от очереди?
Ответ. Двусторонняя очередь: push/pop с обоих концов. Обобщает стек и FIFO; в Python — collections.deque. Подробнее здесь — Реализация и O(·).
Вопрос. LSM-tree — что это и зачем в Cassandra и RocksDB?
Ответ. Log-Structured Merge: быстрая запись в memtable + WAL, фоновое слияние SSTable на диске. Оптимально для write-heavy нагрузок. Подробнее здесь — §11.2 — индексы СУБД.
Вопрос. R-tree — для каких задач нужен?
Ответ. Индекс пространственных объектов (GIS, карты, игры): запрос "что внутри прямоугольника", ближайший сосед. Подробнее здесь — Геометрия.
Вопрос. Почему индексация массива с нуля, а не с единицы?
Ответ. Индекс — смещение от начала блока памяти: base + index * size. С нуля формула проще; в некоторых языках (MATLAB, Lua) — с 1 по историческим причинам. Подробнее здесь — Структуры данных.
Вопрос. Что такое абстрактный тип данных (АТД)?
Ответ. Контракт операций без привязки к реализации: стек, очередь, словарь. Stack можно сделать на массиве или списке — семантика одна. Подробнее здесь — Структуры данных.
Вопрос. Как выбрать структуру данных для задачи на собеседовании?
Ответ. Сначала перечислите операции и частоту, затем сверьтесь с таблицей сложностей. Частые паттерны: hash map для подсчёта, heap для top-K, BFS/DFS для графов. Подробнее здесь — Структуры данных, Реализация и O(·).
Вопрос. Trie (префиксное дерево) — где используется?
Ответ. Автодополнение, маршрутизация IP, поиск по префиксу строк. Эффективно при общих префиксах ключей. Подробнее здесь — Структуры данных.
Вопрос. Union-Find (DSU) — для каких задач?
Ответ. Динамические компоненты связности в графе: "в одной ли группе A и B?", слияние множеств. Почти O(1) с path compression. Подробнее здесь — Реализация и O(·).
Что запомнить
Структуры данных — это формализованные способы организации информации в памяти, определяющие не только форму хранения, но и допустимые операции, их семантику и вычислительные характеристики. Выбор структуры данных напрямую влияет на корректность, производительность, масштабируемость и сопровождаемость программного решения.
Три принципа при выборе структуры:
- Операции важнее названия — сначала список действий (поиск по ключу, вставка в середину, обход соседей), потом массив, хеш, дерево или граф.
- АТД отдельно от реализации — стек/очередь/словарь задают правила; массив и связный список — способы их выполнить.
- Учитывайте масштаб и среду — объём данных, диск vs RAM, однопоточность vs распределённость (индексы B⁺, LSM, CSR).
Краткие опорные утверждения:
- Одна задача допускает несколько структур; "лучшая" — та, что укладывается в требуемую сложность и память.
- Среднее
O(1)у хеш-таблицы не отменяет худшегоO(n)при плохих коллизиях. - Граф в памяти (список смежности) и "сеть" микросервисов — одна идея связей, разная инженерия (задержки, протоколы).
Структуры данных делятся на несколько базовых классов:
Линейные структуры — массивы, списки, стеки, очереди — обеспечивают последовательный или прямой доступ к элементам. Массивы предоставляют O(1) доступ по индексу, но неэффективны при вставке в середину. Связные списки позволяют вставлять и удалять за O(1) при наличии ссылки, но требуют O(n) для доступа. Стеки и очереди — это абстрактные типы данных, реализуемые поверх массивов или списков, с чёткой дисциплиной доступа: LIFO и FIFO соответственно.
Древовидные структуры — деревья поиска, кучи, B-деревья — моделируют иерархические отношения и обеспечивают логарифмическое время поиска при сбалансированности. AVL- и красно-чёрные деревья поддерживают баланс через вращения. B⁺-деревья оптимизированы под блочное чтение с диска и используются в СУБД. Кучи реализуют приоритетные очереди и лежат в основе алгоритмов вроде Heapsort и Дейкстры.
Хеш-структуры — хеш-таблицы, фильтры Блума, Count-Min Sketch — обеспечивают среднее O(1) время доступа за счёт хеш-функций и вероятностных методов. Они чувствительны к качеству хеширования и требуют стратегий разрешения коллизий: цепочки или открытая адресация. Вероятностные структуры жертвуют точностью ради компактности и применяются в потоковой обработке и распределённых системах.
Графовые структуры — матрицы смежности, списки смежности, CSR — описывают произвольные связи между сущностями. Выбор представления зависит от плотности графа и типа операций — матрица даёт O(1) проверку ребра, список — O(deg(v)) обход соседей, CSR — высокую кэш-локальность для аналитических нагрузок.
Геометрические и пространственные структуры — R-деревья, октодеревья, Z-кривые — индексируют многомерные данные и оптимизируют запросы по области, ближайшему соседу или пересечению. Они критичны для ГИС, игр, робототехники и компьютерного зрения.
Куда идти дальше
| Тема | Раздел |
|---|---|
| Псевдокод операций (массив, стек, хеш) | Реализация, справочник |
| Коллекции в коде | О разделе → таблица языков |
| Продвинутые операции с данными | 3-01 — о разделе |
| Алгоритмы | 4-01 — о разделе |