Структуры данных: карта трека и как выбирать структуру под задачу

Есть распространённое заблуждение, что структуры данных — это школьная тема «для собеседований»: выучил, что у хеш-таблицы вставка O(1), а у списка поиск O(n), и свободен. На практике всё наоборот. Структура данных — это самое дешёвое инженерное решение, которое вы принимаете, и одновременно самое дорогое, если принять его неверно. Дешёвое, потому что смена list на set — это три строки диффа. Дорогое, потому что через полгода вокруг этого list вырастет двадцать тысяч строк кода, а профилировщик покажет, что 70 % CPU уходит на линейный поиск в горячем цикле.

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

Часть 1. Что такое структура данных на самом деле

Абстрактный тип данных ≠ структура данных

Первое разделение, без которого дальше будет каша. Есть два разных уровня:

• Абстрактный тип данных (АТД, ADT) — это контракт: набор операций и их семантика, без единого слова о том, как это реализовано. «Множество» — это АТД: add, contains, remove, и обещание, что дубликатов не будет. «Очередь» — это АТД: push, pop, и обещание FIFO.
• Структура данных — это реализация контракта: конкретная раскладка байтов в памяти плюс алгоритмы операций над ней. Множество можно реализовать хеш-таблицей, красно-чёрным деревом, отсортированным массивом, битовой маской или фильтром Блума — и это будут пять принципиально разных инженерных объектов с одинаковым интерфейсом.

Эта разница — не педантизм. Она объясняет, почему в Java есть и HashSet, и TreeSet, а в C++ — и unordered_map, и map: контракт почти один, характеристики радикально разные.

Обратите внимание на BloomFilter: он реализует контракт с ослаблением — contains может соврать «да» там, где элемента нет. Это законный инженерный ход: мы платим корректностью в одну сторону и получаем на порядок меньше памяти. Подробно — в статье про вероятностные структуры.

Структура данных — это способ заранее заплатить за будущие вопросы

Полезная интуиция: любая структура данных — это предвычисленный ответ на класс вопросов.

Неотсортированный массив не знает про свои данные ничего, поэтому вопрос «есть ли здесь 42?» стоит O(n). Отсортированный массив уже несёт в себе инвариант порядка — за него заплатили при построении, — и тот же вопрос стоит O(log n). Хеш-таблица хранит предвычисленное отображение «значение → корзина», и вопрос стоит O(1). Дерево отрезков хранит предвычисленные агрегаты подотрезков, и вопрос «сумма на [l, r]» стоит O(log n) вместо O(n).

Отсюда главный закон жанра: не бывает бесплатных структур, бывают удачно распределённые расходы. Каждый инвариант, который вы поддерживаете, ускоряет одни операции и замедляет другие. Отсортированный массив дал быстрый поиск — и отобрал быструю вставку в середину. Индекс в базе данных ускорил SELECT ... WHERE — и замедлил INSERT. Ровно ту же мысль в другой формулировке вы встретите в треке по алгоритмам как «предобработка против запроса».

Часть 2. Пять вопросов к задаче

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

Вопрос 1. Какие операции реально горячие и в какой пропорции? Не «какие бывают», а какие вызываются миллион раз в секунду. Кэш конфигурации, который читают 10⁶ раз и пишут раз в час, и очередь задач с соотношением 1:1 — это разные миры. Выпишите буквально: lookup 95 %, insert 4 %, delete 1 %.

Вопрос 2. Нужен ли порядок? Три разных ответа, которые часто путают: (а) порядок не нужен вообще; (б) нужен порядок вставки (FIFO/LIFO/история); (в) нужен порядок по ключу (диапазонные запросы, «следующий больший», сортированный вывод). Ответ «в» немедленно вычёркивает хеш-таблицы и приводит вас к деревьям и сбалансированным деревьям.

Вопрос 3. Что известно о ключах и объёмах? Целые числа в диапазоне 0…10⁶ — это битовая маска или массив прямого доступа, а не хеш-таблица. Строки с общими префиксами — это префиксное дерево. Миллиард элементов, которые не влезают в RAM, — это B-дерево или LSM, а не AVL. Размер данных меняет ответ качественно, а не количественно.

Вопрос 4. Какие гарантии нужны: средние или худшего случая? Хеш-таблица даёт O(1) в среднем и O(n) в худшем. Для батч-джобы это неважно. Для сервиса с SLA «p99 < 10 мс» — критично: один неудачный ресайз на 50 миллионов записей выест весь бюджет задержки. Здесь выигрывают структуры с гарантиями худшего случая или с инкрементальным рехешированием (так делает Redis).

Вопрос 5. Кто ещё трогает эти данные? Один поток, много читателей и один писатель, или полноценная многопоточная запись? Нужны ли снимки прошлых версий (undo, MVCC, «покажи состояние на вчера»)? Ответ «да» отправляет вас в статью про персистентные и конкурентные структуры, где привычные ответы перестают работать.

Есть и нулевой вопрос, который стоит задавать первым: а нужна ли вообще нетривиальная структура? Если n = 50 и вызывается это раз в минуту — берите массив, он выиграет у любого дерева по константе, по памяти и по количеству багов. Экзотика оправдана масштабом.

Часть 3. Карта трека

Весь трек — это разворачивание одной оси: от того, как данные лежат в памяти, к тому, как они лежат на диске и в распределённой системе.

Рекомендуемый порядок и зачем нужна каждая статья:

Статьи 01–05 читать строго по порядку — это фундамент. Дальше можно прыгать по потребности, но 06 нужна перед 07, 08 и 12.

Часть 4. Оси, по которым различаются структуры

Ось 1: контракт порядка

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

• Без порядка — хеш-таблицы, множества на хеше, фильтр Блума. Отвечают только на «есть/нет» и «дай по ключу». Зато отвечают за O(1).
• Порядок вставки — массивы, списки, очереди, деки. Помнят «когда», не помнят «больше/меньше».
• Порядок по ключу — BST, B-деревья, кучи (частичный порядок), skip lists, отсортированные массивы. Умеют «дай все ключи от 100 до 200», «дай минимум», «дай следующий за x».

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

Ось 2: стабильность структуры

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

Это ровно то, что делают аналитические СУБД: ClickHouse хранит колонки в отсортированных иммутабельных кусках, а «изменения» реализует через слияние новых кусков. См. также трек по data engineering.

Ось 3: где живут данные

RAM и диск — это разные вселенные, и структура должна знать, в какой она живёт. В RAM единица обмена — кэш-линия 64 байта, и оптимизируем мы количество промахов кэша. На диске (даже NVMe) единица обмена — страница 4–16 КБ, и оптимизируем мы количество обращений к устройству. Именно поэтому в памяти живут бинарные деревья с ветвлением 2, а на диске — B-деревья с ветвлением в сотни: высота дерева при том же n падает с 30 до 3, и это ровно 3 обращения к диску вместо 30.

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

Часть 5. Асимптотика — необходимая, но недостаточная модель

Классический анализ сложности исходит из модели RAM-машины: любое обращение к памяти стоит одну единицу. Эта модель была реалистичной примерно до 1990 года. Сегодня разрыв между скоростью процессора и скоростью памяти — два порядка, и модель систематически врёт.

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

Проверим на измерении. Задача учебная, но эффект честный:

"""Обход массива против обхода связного списка при одинаковой асимптотике O(n)."""
import time, random

N = 2_000_000
array = list(range(N))                                   # непрерывный блок

nodes = [{"value": i, "next": None} for i in range(N)]   # узлы разбросаны по куче
shuffled = nodes[:]
random.shuffle(shuffled)
for i in range(N - 1):
    shuffled[i]["next"] = shuffled[i + 1]
head = shuffled[0]

def sum_array(a):
    total = 0
    for x in a:              # последовательный доступ, префетчер работает
        total += x
    return total

def sum_list(node):
    total = 0
    while node is not None:  # pointer chasing: адрес известен только после загрузки
        total += node["value"]
        node = node["next"]
    return total

for name, fn, arg in (("массив", sum_array, array), ("список", sum_list, head)):
    t0 = time.perf_counter()
    fn(arg)
    print(f"{name}: {time.perf_counter() - t0:.3f} с")

# Типичный результат на CPython: массив 0.09 с, список 1.40 с.
# Разница ~15x при формально одинаковой сложности O(n).

В Python часть разницы объясняется накладными расходами интерпретатора, но эффект воспроизводится и на C, и на Go, и на Rust — просто с коэффициентом 5–10 вместо 15. Подробный разбор — в статье про асимптотику и модель памяти.

Вывод, который стоит вбить в привычку: асимптотика отвечает на вопрос «как поведение меняется при росте n». Она не отвечает на вопрос «сколько это займёт миллисекунд при моём n». Для второго нужны замеры и понимание иерархии памяти.

Часть 6. Дерево решений

Формализуем процедуру выбора. Это не догма, но хороший чек-лист, который ловит 90 % типовых случаев.

Часть 7. Одна задача — четыре решения

Абстракции запоминаются на конкретике. Задача: идёт поток событий (id, вес), часть id повторяется. Нужно вернуть топ-K по весу среди уникальных id. Классика для аналитики, антифрода и лидербордов.

Наивное решение

def top_k_naive(events, k):
    """Список для дедупликации + пересортировка на каждом шаге."""
    seen = []          # линейный поиск: O(n) на проверку
    best = []          # держим отсортированным вручную
    for eid, weight in events:
        if eid in seen:            # O(len(seen)) — вот она, квадратичность
            continue
        seen.append(eid)
        best.append((weight, eid))
        best.sort(reverse=True)    # O(k log k) на каждом новом элементе
        del best[k:]
    return best

Сложность: O(n²) на дедупликации плюс O(n · k log k) на поддержании топа. Память O(n). При n = 10⁶ это часы.

Правильное решение

import heapq


def top_k_fast(events, k):
    """Хеш-множество для дедупликации + min-heap фиксированного размера k."""
    seen = set()       # O(1) в среднем на проверку и вставку
    heap = []          # min-heap: в корне — самый слабый из текущего топа
    for eid, weight in events:
        if eid in seen:
            continue
        seen.add(eid)
        if len(heap) < k:
            heapq.heappush(heap, (weight, eid))          # O(log k)
        elif weight > heap[0][0]:
            heapq.heapreplace(heap, (weight, eid))       # O(log k), одна перестройка
        # иначе элемент заведомо не попадёт в топ — выбрасываем за O(1)
    return sorted(heap, reverse=True)

Сложность: O(n) ожидаемо на дедупликации плюс O(n log k) на топе. Память O(n + k). При n = 10⁶ и k = 100 — доли секунды.

Ключевой приём здесь — min-heap для max-top-K. Он контринтуитивен ровно один раз: чтобы держать K наибольших, нужен доступ к наименьшему из них, потому что именно его вытесняют. Разбор — в статье про кучи.

Решение, когда n не влезает в память

Если уникальных id миллиарды, set не влезет. Тогда меняем точность на память:

# Псевдокод потокового варианта
#
# 1) Дедупликация без хранения всех id:
#      seen = BloomFilter(ожидаемое_n, вероятность_ошибки=0.01)
#      если seen.contains(id): пропустить    # ~1% ложных пропусков
#      иначе: seen.add(id)                   # ~10 бит на элемент вместо ~50 байт
#
# 2) Топ-K на потоке: sketch = CountMinSketch(ширина, глубина)
#      sketch.add(id, weight); heap.push_or_replace(id, sketch.estimate(id))
#
# Гарантия: с вероятностью 1-δ ошибка оценки не превышает ε * суммарный_вес.
# Память: O(1/ε * log(1/δ)) — не зависит от числа уникальных ключей.

Это ровно то, что делают Redis (PFCOUNT на HyperLogLog), Kafka Streams и большинство систем реального времени. Детали — в статье про вероятностные структуры.

Решение, когда нужны диапазоны

Если помимо топ-K нужно «сколько событий с весом от 100 до 500» и веса меняются — куча не подойдёт, потому что она не хранит полный порядок. Нужно дерево Фенвика по весам: обновление и диапазонный запрос за O(log W).

Одна формулировка задачи, четыре структуры, различие в производительности — на порядки. Именно поэтому вопрос «какая структура правильная» без описания профиля нагрузки не имеет ответа.

Часть 8. Шпаргалка по сложности

Средние значения; худший случай указан отдельно там, где он принципиально отличается.

L — длина ключа-строки, B — ветвление узла B-дерева, α — обратная функция Аккермана (для любых практических n не превышает 4).

Колонка «Память» — самая недооценённая. Разница между «~1×» и «~3×» означает, что одна структура влезет в L3-кэш, а другая нет, и это перевесит всю разницу в асимптотике.

Часть 9. Типичные ошибки

Список там, где нужен массив. Самая частая. Связный список выигрывает только при частых вставках/удалениях по уже известному узлу и при отсутствии обходов. Если вы ищете узел перед удалением — вы уже платите O(n) с промахами кэша, и массив выиграет. Bjarne Stroustrup демонстрировал это в докладе «Why you should avoid Linked Lists» — даже вставка с сохранением сортировки быстрее на vector, чем на list, вплоть до сотен тысяч элементов.

Линейный поиск в цикле. if x in some_list внутри цикла по n элементам — мгновенный O(n²). Проверяется грепом по кодовой базе, чинится заменой на set. Классический источник инцидентов вида «работало на тестовых данных, легло на проде».

Оптимизация не той операции. Выбрали структуру с идеальной вставкой, а в проде 99 % — чтения. Всегда начинайте с профиля нагрузки, а не с интуиции. Смежная ошибка — игнорирование худшего случая при наличии SLA: хеш-таблица с O(1) в среднем даёт паузу на ресайзе, которая пробивает p99. Лечится резервированием ёмкости, инкрементальным рехешем или структурой с гарантией худшего случая.

Забытая устойчивость к атакам. Если ключи хеш-таблицы приходят от пользователя (заголовки HTTP, параметры формы, JSON-поля), детерминированная хеш-функция открывает HashDoS: атакующий подбирает ключи в одну корзину и превращает O(1) в O(n). Отсюда рандомизированное сидирование хешей в Python (PYTHONHASHSEED), Ruby, Go и Rust (SipHash). Разбор — в статье про хеш-таблицы.

Преждевременная экзотика. Дерево отрезков на 40 элементов, которое вызывается раз в час, — это не оптимизация, а долг сопровождения. Правило: сначала простейшая корректная структура, потом профилировщик, потом замена.

Изобретение структуры при наличии готовой. Стандартные библиотеки вылизаны годами: std::vector, HashMap в Rust с SwissTable-раскладкой, dict в CPython с compact-представлением. Своя реализация оправдана, когда вы точно знаете, какое именно ограничение стандартной вы снимаете.

Часть 10. Как это выглядит в проде

Полезно видеть, что все эти структуры — не абстракции из учебника, а буквально то, что крутится под нагрузкой.

• PostgreSQL: индексы по умолчанию — B-дерево (nbtree), плюс GiST, GIN (инвертированный индекс на основе B-дерева для полнотекстового поиска и JSONB), BRIN, SP-GiST (radix-деревья). Выбор типа индекса — прямое применение оси «порядок + размер страницы». Документация по типам индексов.
• Redis: почти учебник структур данных, оформленный как сетевой сервис. Списки — quicklist (список массивов, компромисс между списком и массивом), sorted set — skip list плюс хеш-таблица одновременно, HyperLogLog — вероятностный счётчик уникальных на 12 КБ. См. redis.io/docs/data-types.
• Kafka: лог — это append-only массив на диске, а индекс смещений — разреженный отсортированный массив с бинарным поиском. Максимально простые структуры, выбранные под последовательный доступ.
• RocksDB / LevelDB / Cassandra: LSM-дерево — memtable (skip list в RAM) плюс иммутабельные отсортированные SSTable на диске плюс Bloom filter перед каждой таблицей, чтобы не читать её зря. Три структуры из этого трека в одной конструкции.
• Linux-ядро: красно-чёрные деревья в планировщике CFS (struct rb_node), radix tree / XArray для page cache, хеш-таблицы для dentry-кэша.
• Git: контентно-адресуемое хранилище на хеше плюс персистентное дерево объектов — каждый коммит переиспользует неизменившиеся поддеревья предыдущего. Живой пример structural sharing из статьи 14.
• Компиляторы и JIT: интернирование строк через хеш-таблицы, DSU для алгоритмов вывода типов (унификация), графы для анализа потока данных.

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

Часть 11. Немного истории — чтобы понимать, почему всё так

Смысл этой хронологии не в датах. Он в том, что почти каждый скачок был ответом на смену «железа»: B-деревья появились, когда узким местом стал диск; cache-oblivious структуры — когда узким местом стал кэш; SIMD-хеш-таблицы — когда появились широкие векторные регистры. Структуры данных всегда проектируются под физику носителя, и это лучший индикатор того, какие структуры будут актуальны завтра.

Мини-итог

• АТД — это контракт, структура данных — реализация. Один контракт может иметь пять реализаций с несопоставимыми характеристиками.
• Структура данных — это заранее оплаченный ответ на класс вопросов. Инвариант, который вы поддерживаете, ускоряет одни операции ровно за счёт замедления других.
• Выбор начинается с профиля нагрузки, а не со справочника: пропорция операций, нужен ли порядок, что известно о ключах, средние гарантии или худшего случая, кто ещё пишет.
• Асимптотика — необходимая, но недостаточная модель. Локальность в памяти регулярно перевешивает разницу в порядке сложности на реальных n.
• Начинайте с простого. Массив и хеш-таблица покрывают большую часть задач. Экзотика — по результатам профилирования, а не по вдохновению.

Источники

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

• Кормен, Лейзерсон, Ривест, Штайн. «Алгоритмы: построение и анализ» (CLRS) — эталонная строгость, части III–VI. MIT Press.
• Sedgewick, Wayne. «Algorithms», 4-е издание — лучшая визуальная подача, полный код на Java, бесплатные материалы на algs4.cs.princeton.edu.
• Skiena. «The Algorithm Design Manual» — «каталог» задач и подходящих структур, самая практическая часть — вторая. Сайт книги.
• Okasaki. «Purely Functional Data Structures» — обязательное чтение перед статьёй 14. PDF диссертации.
• Ulrich Drepper. «What Every Programmer Should Know About Memory» — то, чего нет в CLRS: кэши, TLB, префетч. PDF на akkadia.org.
• Bjarne Stroustrup. «Why you should avoid Linked Lists» — короткое видео с замерами, снимающее вопросы про списки. YouTube.
• Peter Bailis et al. «Readings in Database Systems» (Red Book) — как структуры данных живут в СУБД. redbook.io.
• Визуализация структур данных — интерактивные анимации операций: visualgo.net, cs.usfca.edu/~galles/visualization, сводная таблица сложностей bigocheatsheet.com.

Что дальше

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

→ Асимптотика, амортизация и модель памяти: как на самом деле считать стоимость