Карта курса: 16 понятий в шести группах

Карта метро: сначала видишь все линии, потом едешь по станциям.

Сверху — три базовые идеи: Data Structure, Trade-off и Big-O. Дальше шесть групп: формы роста Big-O, массив, хеш-таблица и множество, структуры с порядком (стек и очередь), структуры с формой (дерево и граф) и, наконец, как всё это выбирать на практике.

Как читать курс

Паспорт: одинаковые поля у всех, поэтому их легко сравнивать.

У каждого понятия одно и то же: английское название (его ты встретишь в документации и на собеседовании), образ из жизни, схема и карточка: что это, как работает, пример, цена и связи с другими структурами. Главное правило курса: лучшей структуры не бывает — бывает подходящая под твою частую операцию.

Data Structure — структура данных

Ящик с инструментами, где у каждого своё гнездо, против мешка, куда всё свалено. Инструменты те же, но из ящика нужный берёшь сразу, а в мешке каждый раз роешься.

Структура данных (data structure) — это способ расположить данные в памяти. Разные расположения делают быстрыми разные операции: одно отлично ищет по имени, другое держит порядок, третье всегда отдаёт самый свежий элемент. Вся игра — подобрать структуру под то, что ты делаешь чаще всего.

Та же задача бывает тривиальной или почти невозможной — смотря как лежат данные. Найти слово в отсортированном словаре — секунды; в тех же словах, сваленных как попало, — целый день. Поэтому удивительно много «сделай быстрее» на деле значит «храни в правильной форме». Структура и есть решение.

Trade-off — каждая структура это размен

Спорткар и грузовик для переезда — оба транспорт. Ты не спрашиваешь, какой лучше; ты спрашиваешь: лучше для чего?

Ни одна структура не лучшая во всём. Одна даёт мгновенный поиск, но без порядка; другая держит порядок, но медленно ищет; третья быстро добавляет, но медленно находит что-то внутри. Это и есть trade-off (размен): сила в одной операции оплачена слабостью в другой. Бесплатного обеда нет — твоя работа выбрать размен, который подходит твоему случаю.

Big-O notation — рост, а не секунды

Вопрос не «сколько длится одна доставка», а «как меняется общее время, когда в маршруте не десять остановок, а десять тысяч». Форма роста, а не показания секундомера.

Нотация Big-O описывает, как растёт цена операции, когда растёт объём данных — его обозначают n. Она не смотрит на миллисекунды и конкретную машину, а ловит форму: удвоили данные — работа удвоилась, учетверилась или почти не изменилась? Эта форма и решает, останется ли код быстрым на больших данных. Поэтому Big-O — способ сравнить подходы, даже не запуская их.

Complexity classes — формы от отличной до ужасной

Четыре способа, как растёт работа по дому: одна остаётся одним делом, сколько бы ни было вещей; другая растёт вместе с кучей; третья взрывается как куча в квадрате; четвёртая почти не растёт, даже когда куча растёт.

Несколько форм покрывают почти весь код:

• O(1) — константа: время одно и то же при любом размере (взять элемент по индексу).
• O(log n) — логарифм: почти не растёт, даже когда данных становится очень много (каждый шаг делит поиск пополам).
• O(n) — линейная: растёт вместе с данными (просмотреть весь список).
• O(n²) — квадратичная: взрывается (сравнить каждый элемент с каждым). Классика «в тестах нормально, в проде умирает».

Для десяти элементов любая структура кажется мгновенной — разница не видна. Big-O — про то, что будет, когда n станет большим. Поэтому код «вдруг» тормозит в проде: плохая форма была там всегда, просто пряталась, пока данные не выросли.

Array — упорядоченная нумерованная последовательность

Ряд пронумерованных шкафчиков: вещи стоят по порядку, у каждой свой номер — 0, 1, 2… — и к любому шкафчику можно подойти сразу по номеру.

Массив (array, list) хранит элементы по порядку, каждый на своей позиции — индексе (index), начиная с 0. Элементы лежат подряд, в известном месте памяти, поэтому прыгнуть к любой позиции по индексу — мгновенно, O(1). Массив — выбор по умолчанию для «кучи вещей по порядку», а доступ по позиции — его суперсила.

Но есть цена. Добавить или убрать элемент в конце — дёшево. А вставка или удаление в середине сдвигает всё, что после, чтобы сохранить порядок и нумерацию, — это O(n).

Linear search — перебор по значению

Шкафчик 500 открываешь мгновенно. Но если знаешь только, что лежит внутри, а не номер, — придётся открывать один за другим, пока не найдёшь.

Подвох массива: он быстр, только когда знаешь индекс. Чтобы найти элемент по содержимому — «есть ли этот email в списке?» — нужно проверить каждый по очереди. Это линейный поиск (linear search), O(n): на больших списках — медленно. Ровно эту дыру закрывает следующая структура.

Hash Map — пары ключ-значение

Телефонная книга: ищешь человека по имени и сразу получаешь номер. Ты не листаешь все записи — имя ведёт прямо к ответу.

Хеш-таблица (hash map; ещё dictionary, hash table или просто map) хранит данные как пары ключ-значение (key-value): даёшь ключ — получаешь значение. Пользователь по ID, настройка по имени, счётчик по слову — напрямую, по ключу. Массив заставляет знать позицию; хеш-таблица даёт искать по осмысленному имени.

Hash function — почему поиск мгновенный

Волшебный шкаф: по метке сразу открывается нужный ящик, другие он не проверяет. Сколько ящиков — неважно.

Магия хеш-таблицы в том, что поиск по ключу фактически O(1) — постоянное время, сколько бы элементов в ней ни было. Ключ прогоняют через хеш-функцию (hash function): она вычисляет, где лежит значение, и таблица прыгает прямо туда, а не ищет. Миллион записей или десять — найти одну одинаково быстро. Поэтому хеш-таблица и рабочая лошадка: «найди по имени» — то, что программы делают постоянно.

Set — есть или нет, без значений

Список гостей на входе: детали не нужны, только «да или нет» — есть это имя в списке? Проверено мгновенно, без листания.

Близкий родственник — множество (set): хеш-таблица, которая хранит только ключи, без значений, чтобы быстро отвечать на один вопрос — «это здесь есть?». Проверка присутствия и защита от дубликатов — обе O(1). Каждый раз, когда ловишь себя на переборе списка ради «я это уже видел?», множество превращает медленную O(n)-проверку в мгновенную.

Stack — последним пришёл, первым ушёл (LIFO)

Стопка тарелок: кладёшь сверху и берёшь сверху. Последняя положенная — первая, которую возьмёшь.

Стек (stack) работает по правилу LIFO — last in, first out (последним пришёл — первым ушёл). Добавляешь (push) и убираешь (pop) с одного конца, поэтому первым выходит самый свежий элемент. Это подходит всему, что вкладывается или разматывается в обратном порядке: история отмены (undo), кнопка «назад», стек вызовов программы (call stack). Обе операции — O(1).

Queue — первым пришёл, первым ушёл (FIFO)

Очередь в кассу: обслуживают в порядке прихода, новые встают в хвост, следующим идёт тот, кто впереди.

Очередь (queue) работает по правилу FIFO — first in, first out (первым пришёл — первым ушёл). Добавляешь в хвост (enqueue), забираешь спереди (dequeue), поэтому элементы обрабатываются в порядке прихода. Это структура для честности и порядка: задачи на обработку, ждущие работы, запросы по очереди — та же идея, что у очереди сообщений из курса про очереди. Как и у стека, операции — O(1).

Правило определяет поведение

Одна и та же куча работы, две двери: одна отдаёт самое свежее, другая — самое старое. Один выбор — с какого конца брать — меняет всё дальше.

Стек и очередь хранят одно и то же; вся разница — с какого конца забираешь. Выбирать между ними — значит выбирать порядок, в котором работа к тебе возвращается: обратный и вложенный (стек) или честный и последовательный (очередь). Маленькое решение с большим эффектом: угадай порядок — и остальная логика встанет на место.

Tree — иерархия

Семейное древо или оргструктура компании: одно наверху, дальше ветвится вниз на детей, у тех свои дети. Расходится веером и никогда не замыкается обратно.

Дерево (tree) хранит данные как иерархию: сверху корень (root), от него ветвятся узлы (nodes) с детьми, и так вниз. Оно моделирует всё вложенное — папки в папках, комментарии и ответы на них, меню категорий. Форма дерева повторяет реальную вложенность, поэтому оно естественный выбор, когда данные — «вещи внутри вещей». Большинство иерархий в софте — деревья под капотом.

Balanced tree — поиск за O(log n)

Ищешь имя в телефонной книге: открываешь середину, потом середину нужной половины, и снова. Каждый шаг выкидывает половину оставшегося.

Хорошо организованное, сбалансированное (balanced) дерево даёт мощное свойство: в нём можно искать за O(log n), каждый раз деля пространство пополам — как ищешь слово в словаре, не читая каждую страницу. Логарифм почти не растёт, даже когда данные взрываются: миллиард элементов — всего около тридцати шагов. Так базы данных держат поиск быстрым на огромном масштабе: упорядоченные данные в форме дерева, поиск делением пополам.

Graph — сеть связей

Карта городов, соединённых дорогами, или люди, связанные дружбой: всё связано со всем в любом узоре, без верха и низа.

Граф (graph) — самая общая форма: узлы (nodes), соединённые рёбрами (edges), в любом узоре, включая петли. Он моделирует сети — социальные связи, дороги между городами, ссылки между страницами, зависимости между задачами. Если данные по сути «вещи, связанные с другими вещами», а не иерархия и не линия, — это граф. Многие сложные задачи — кратчайший маршрут, кто с кем связан — в основе графовые.

Dominant operation — выбирай по частой операции

Кухню собирают под то, что готовят каждый вечер, а не под то, что эффектно смотрится.

Практическое решение почти всегда одно: какую операцию я делаю чаще всего, и какая структура делает именно её быстрой? Постоянный поиск по ключу — Hash Map. Порядок прихода — Queue. В основном чтение по позиции — Array. Пусть доминирующая операция (dominant operation) выбирает структуру, а с медленностью в редких операциях смирись. Оптимизируй частый случай — структура и есть способ.

Map before loop — сначала таблица, потом цикл

Прежде чем искать человека в толпе по лицам, проверь, нет ли списка гостей: список отвечает мгновенно на то, что поиск делает медленно.

Очень частый и очень полезный ход: когда ловишь себя на переборе списка, чтобы найти или сопоставить что-то, — O(n)-цикл или, хуже, O(n²)-цикл внутри цикла, — спроси, не сделает ли это мгновенным хеш-таблица или множество. Замена вложенного поиска на поиск по таблице — одно из самых частых реальных ускорений. Чинит обычно структура, а не более быстрый цикл.

Как всё связано

Генеалогия инструментов: каждый следующий закрывает слабость предыдущего.

Big-O — линейка, которой меряют все структуры. Hash Map закрывает слабость Array (поиск по значению), Set — это Hash Map без значений. Stack и Queue — последовательность с правилом «забирай только с конца». Tree даёт иерархию, а сбалансированное — поиск за O(log n); Graph снимает последнее ограничение и разрешает любые связи.