Как хранят данные: обзор структур данных и зачем их так много

В прошлых статьях трека мы прошли путь снизу: биты, вентили, процессор, память, ОС. К этому моменту у нас есть важный факт из статьи про иерархию памяти: память для программы — это один огромный плоский массив пронумерованных ячеек-байтов. У ячейки есть адрес (число) и содержимое (число). Больше там ничего нет. Ни «списков», ни «таблиц», ни «деревьев» — только нумерованная лента байтов.

А думаем мы совсем не байтами. Мы думаем «список задач», «телефонная книга», «дерево каталогов», «очередь на печать», «граф друзей». Структуры данных — это мост между тем, как мы думаем о данных, и тем, как их на самом деле хранит машина. Структура данных — это договорённость: как разложить объекты по плоской ленте памяти и какими операциями с ними работать, чтобы важные для нас действия были быстрыми, а не мучительными.

И тут возникает главный вопрос статьи: если задача всего лишь «хранить набор элементов», почему структур данных десятки? Почему нет одной, самой лучшей? Ответ короткий и он — стержень всей темы: потому что нет операции „вообще“. Есть конкретные операции — найти по номеру, найти по имени, вставить в начало, взять минимум, пройти по порядку — и структура, идеальная для одной из них, посредственна для другой. Выбор структуры — это выбор, что вы хотите делать быстро, ценой того, что станет медленным. Разберём эту мысль по слоям.

Это обзорная статья: она даёт карту и интуицию. За полными доказательствами, реализациями всех операций и тонкостями каждой структуры — отдельный глубокий трек Структуры данных. Про то, что означает загадочное «O(1)» и «O(n)», которыми мы будем сыпать, — соседняя статья этого трека (Алгоритмы и сложность); здесь берите их как «дёшево, не зависит от размера» и «дорого, растёт с размером».

Два физических примитива: подряд или по ссылкам

Всё многообразие структур собрано из двух способов положить элементы в плоскую память. Это фундамент, и его стоит прочувствовать физически.

Способ первый — подряд (contiguous). Кладём элементы вплотную, ячейка за ячейкой. Это массив. Раз элементы одинакового размера и лежат встык, адрес i-го вычисляется одной формулой: адрес = база + i × размер. Значит, прыжок к любому элементу по его номеру — мгновенный, за одну арифметику, O(1), независимо от того, миллион элементов или три. Расплата — за жёсткость раскладки: чтобы вставить элемент в середину, надо сдвинуть весь хвост на одну ячейку (O(n)), а чтобы вырасти за пределы выделенного куска — попросить у ОС новый, больший, и всё туда скопировать.

Способ второй — по ссылкам (linked). Разрешаем элементам лежать где угодно, вразброс, а порядок задаём явно: в каждом элементе (узле) рядом со значением храним указатель — адрес следующего узла. Это связный список. Теперь вставка — это переписать пару указателей, не двигая ничего: O(1). Зато «дай мне i-й элемент» превращается в «иди по стрелкам от начала i раз» — O(n), прямого доступа по номеру нет.

Один и тот же список чисел [17, 42, 8, 99] в этих двух раскладках живёт в памяти совершенно по-разному, и это различие определяет, что с ним быстро, а что медленно. Запомните противопоставление — оно повторится в каждой структуре ниже:

Последняя строка — не мелочь, к ней мы вернёмся в конце: она про то, где красивая теория «O(1) против O(n)» протекает об реальное железо из статьи про иерархию памяти.

Карта структур данных

Из этих двух примитивов (и их скрещивания) вырастает весь зоопарк. Разложим его по семьям — не как список для зубрёжки, а как карту с ответом на вопрос «что эта структура делает быстро».

Пройдёмся по ключевым семьям. Для каждой — одна фраза «в чём суть», один убийственный сценарий применения и главный компромисс. Это интуиция, а не спецификация; спецификация — в глубоком треке.

Динамический массив — рабочая лошадь

Обычный массив имеет фиксированный размер. Динамический массив (это list в Python, ArrayList в Java, vector в C++, срез в Go) прячет фокус: когда место кончается, он выделяет вдвое больший кусок и копирует туда всё. Копирование — дорого, O(n), но случается редко, и если «размазать» его на все добавления, добавление в конец стоит в среднем O(1) (это называют амортизированной сложностью). Отсюда правило: динамический массив бесподобен, когда вы читаете по индексу и дописываете в конец, и плох, когда часто вставляете в начало или середину. В 90% повседневного кода вам нужен именно он — это структура по умолчанию.

Стек и очередь — дисциплина доступа

Иногда сила структуры не в скорости, а в ограничении. Стек и очередь — это списки, к которым разрешён доступ только с концов, и это ограничение и есть их смысл.

• Стек (stack, LIFO — last in, first out) — «кто последним вошёл, первым выйдет». Кладём и берём только с одного конца (вершины). Стопка тарелок. На стеке держится вся вложенность в вычислениях: вызовы функций (тот самый «стек вызовов» и его переполнение — stack overflow), разбор скобок, отмена действий (undo), обход в глубину. Процессор аппаратно поддерживает стек регистром SP из статьи про устройство процессора.
• Очередь (queue, FIFO — first in, first out) — «первым пришёл, первым обслужен». Кладём с одного конца, берём с другого. Живая очередь. На очередях держатся буферы, планировщики задач, очереди печати и сообщений, обход в ширину.

Важно: стек и очередь — это не про то, из чего они сделаны, а про то, как ими пользуются. Реализовать их можно и на массиве, и на связном списке. Это первый намёк на различие «интерфейс против реализации», к которому мы придём отдельно.

Хеш-таблица — поиск по ключу почти даром

Пока что мы искали элементы по номеру. Но чаще нужно искать по ключу: по имени — телефон, по слову — перевод, по id пользователя — его профиль. Наивно это O(n): перебирай всё, пока не найдёшь. Хеш-таблица (dict в Python, HashMap в Java, Map в JS, map в Go) делает это в среднем за O(1) — и это, пожалуй, самая недооценённо-волшебная структура в информатике.

Идея: пропустить ключ через хеш-функцию — она превращает ключ любой природы (строку, число, объект) в число, — и по этому числу вычислить номер ячейки (корзины) в обычном массиве. Кладём и ищем прямо по вычисленному номеру, не перебирая.

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

Деревья — иерархия и упорядоченный поиск

Дерево — узлы, где у каждого есть родитель и несколько детей, без циклов. Иерархия буквально повсюду: файловая система, HTML-документ (DOM), синтаксическое дерево кода в компиляторе (статья От кода к исполнению), организационная структура.

Отдельная звезда — двоичное дерево поиска (BST): у каждого узла максимум двое детей, слева всё меньше значения узла, справа — больше. Такой порядок позволяет искать, отсекая на каждом шаге половину оставшихся элементов, — за O(log n). Логарифм — это очень мало: в миллионе элементов путь до любого около 20 шагов. Это компромисс между массивом (быстрый доступ по номеру, но медленная вставка) и хеш-таблицей (быстрый поиск по ключу, но нет порядка): дерево держит элементы отсортированными и при этом даёт быстрые поиск и вставку. Плата — за то, чтобы дерево не выродилось в тот же связный список: его приходится балансировать (красно-чёрные деревья, AVL, B-деревья), и это заметно сложнее в реализации. Кстати, индексы в базах данных — это почти всегда сбалансированные деревья (B-деревья); подробнее — в статье Базы данных.

Куча — быстрый доступ к минимуму

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

Граф — сеть связей

Когда связи между объектами перестают быть иерархией (у элемента может быть много «соседей», возможны циклы), это граф: вершины и рёбра. Социальные сети, карты дорог, зависимости пакетов, интернет-маршруты, состояния программы. Граф — это не столько «как хранить» (обычно хранят списком смежности — массив, где у каждой вершины список соседей — или матрицей), сколько целый мир алгоритмов поверх: поиск пути, обнаружение циклов, кратчайшие маршруты. Это уже территория трека Алгоритмы.

Почему их так много: «бесплатных обедов не бывает»

Теперь соберём разрозненные наблюдения в один принцип. Посмотрите на сводную таблицу средней стоимости операций (усреднённо, «типичный случай»; худшие случаи и точные условия — в глубоком треке):

Вглядитесь в столбцы: в каждой строке жирные (быстрые) клетки соседствуют с медленными, и ни одна строка не выделена жирным целиком. Это не случайность и не недоработка инженеров — это фундаментальный закон. Ускоряя одну операцию, вы принимаете раскладку данных, которая замедляет другую. Хеш-таблица платит за мгновенный поиск по ключу отказом от порядка. Массив платит за мгновенный доступ по индексу дорогой вставкой. Дерево — золотая середина по скорости, но платит сложностью и логарифмом вместо единицы. Идеальной структуры нет, потому что «быстро» без уточнения «что именно» — бессмысленно.

Отсюда — рабочий способ выбирать структуру: не «какая лучшая?», а «какие операции я делаю чаще всего и на горячем пути?». Ответ на этот вопрос и есть ваша структура.

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

Интерфейс против реализации: абстрактный тип данных

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

• Что структура умеет делать — набор операций и их смысл. Это абстрактный тип данных (АТД): контракт. «Стек — это push, pop, peek, работающие по правилу LIFO».
• Как она это делает — конкретная раскладка в памяти. Это реализация.

Один и тот же АТД можно реализовать по-разному, с разными компромиссами. Стек — это идея (LIFO); построить его можно и на динамическом массиве, и на связном списке, и снаружи разницы не видно.

Практический вывод: в коде вы работаете с интерфейсом, а реализацию выбираете под нагрузку. Именно поэтому в стандартных библиотеках Stack, Queue, Map, Set, List — это часто интерфейсы с несколькими реализациями (HashMap против TreeMap, ArrayList против LinkedList). Меняете реализацию — меняется профиль скорости, но не логика программы. Это прямое проявление принципа абстракции, на котором стоит весь наш трек: пользуйся контрактом, не завися от внутренностей.

Вы уже пользуетесь ими каждый день

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

# Задача: по мере поступления имён быстро отвечать «видели такое имя?»

# ПЛОХО: список — проверка принадлежности перебирает всё, O(n) на каждый запрос.
seen = []
if name not in seen:        # O(n) — линейный перебор всего списка
    seen.append(name)

# ХОРОШО: множество (хеш-таблица под капотом) — проверка в среднем O(1).
seen = set()
if name not in seen:        # O(1) — один хеш, одна корзина
    seen.add(name)

На тысяче имён разницу не заметить. На миллионе первый вариант — это триллион сравнений, минуты работы; второй — доли секунды. Ни одной «умной» строчки, только выбор структуры. Карта соответствий, которую полезно держать в голове:

Правило большого пальца для 95% кода: по умолчанию берите динамический массив; как только ловите себя на поиске элемента через перебор — переходите на словарь или множество. Этого знания хватает, чтобы не писать случайно квадратичный код.

Где абстракция протекает

Big-O — мощная, но нарочно грубая линза: она считает число операций и полностью игнорирует, что́ одна операция стоит на реальном железе. А на реальном железе, как мы видели в статье про иерархию памяти, обращение к соседней ячейке и прыжок в случайное место памяти отличаются по цене в сотни раз. Здесь теория протекает — и знать об этом важно.

• Локальность бьёт асимптотику на малых данных. У массива и связного списка обход — оба O(n). Но массив лежит вплотную, процессор тянет его кэш-линиями и угадывает наперёд; список разбросан, каждый переход по указателю — потенциальный промах кэша ценой в сотни тактов. На практике проход по массиву часто в разы быстрее прохода по списку с той же O(n), и ArrayList обыгрывает LinkedList даже на вставках, где у списка «лучше» асимптотика. Big-O этого не видит.
• Константы и «мелкий n». O(log n) дерева асимптотически лучше O(n) перебора, но у дерева большие константы (прыжки по указателям, балансировка). На десятке элементов тупой линейный поиск по массиву обгонит любое дерево. Асимптотика — про поведение на большом росте, а не на всех размерах.
• Хеш-таблица — это «в среднем». Её O(1) — про удачное распределение. В худшем случае (много коллизий, атака) она становится O(n), и в системах на открытом входе это учитывают (рандомизируют хеш, ограничивают нагрузку).
• Накладной расход памяти. Каждый узел списка или дерева тащит указатели (8 байт каждый на 64-битной машине), а хеш-таблица держит корзины с запасом. Хранить миллион чисел в связном списке против плотного массива — это кратная разница по памяти, а память — это тоже скорость (из-за того же кэша).

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

Типичные заблуждения

• «Есть лучшая структура данных». Нет. Есть лучшая структура под конкретный профиль операций. Смена профиля меняет ответ.
• «Связный список быстрее массива, у него же вставка O(1)». Только если узел уже на руках и вам не важна локальность. На современном железе плотный массив выигрывает чаще, чем подсказывает асимптотика.
• „dict и list — просто разные способы записать одно и то же“. Нет: за ними разные структуры с разной сложностью. Поиск x in list — O(n), x in dict/set — O(1). Путаница здесь — типовая причина внезапно тормозящих программ.
• «O(1) значит быстро всегда». O(1) значит «не растёт с размером», а не «мгновенно». У операции могут быть большие константы; на маленьких данных «медленная» O(n) обгонит.
• «Раз всё встроено, устройство знать необязательно». Встроено — да, но выбирать между встроенным всё равно вам, и без модели «подряд против ссылок, порядок против хеша» этот выбор превращается в гадание.

Мини-итог

Память — плоская лента байтов; структуры данных раскладывают по ней объекты так, чтобы нужные операции были дешёвыми. Всё собрано из двух примитивов: подряд (массив — мгновенный доступ по индексу, дорогая вставка) и по ссылкам (список — дешёвая вставка, нет прямого доступа). Скрещивая их и добавляя правила, получаем стеки и очереди (сила в ограничении доступа), хеш-таблицы (поиск по ключу за O(1) ценой порядка), деревья (упорядоченный поиск за O(log n) ценой сложности), кучи (быстрый минимум) и графы (сети связей). Структур много, потому что быстро сразу всё — невозможно: ускоряя одну операцию, замедляешь другую, и выбор структуры — это выбор, что делать быстро. Различайте контракт (АТД) и реализацию, выбирайте встроенную структуру по профилю горячих операций — и помните, что Big-O задаёт направление, но на горячем пути последнее слово за кэшем и реальными замерами.

Что дальше

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

Что такое алгоритм и сложность: интуиция Big-O для всех