3.02. Фундаментальные структуры данных и их реализация

В РАЗРАБОТКЕНЕ ДЛЯ НОВИЧКОВНЕ ОБЯЗАТЕЛЬНО

Разработчику Архитектору Инженеру

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

1. Массивы

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

1.1 Статические массивы

Статический массив выделяется в памяти во время компиляции или при входе в область видимости (в зависимости от языка). Его размер фиксирован и не может быть изменён в ходе выполнения программы. Доступ к элементу по индексу осуществляется за константное время O(1), поскольку адрес элемента вычисляется по формуле:

адрес_элемента = базовый_адрес + индекс × размер_элемента

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

Однако статические массивы не поддерживают динамический рост. Попытка выйти за пределы выделенной памяти вызывает поведение, неопределённое на уровне языка (в C/C++), либо исключение (в Java, C#, Python). В языках с управляемой памятью (например, C#) такие массивы инкапсулируются в типы, предоставляющие дополнительную безопасность.

1.2 Динамические массивы

Динамические массивы (в C++ — std::vector, в C# — List<T>, в Python — list) имитируют поведение бесконечно расширяемой последовательности, скрывая от программиста механизм реаллокации. Внутренне такая структура поддерживает буфер фиксированного размера. При добавлении элемента, если буфер заполнен, выделяется новый блок памяти большего размера (обычно в 1.5–2 раза больше), и все существующие элементы копируются в него.

Амортизированная сложность операции добавления в конец составляет O(1), несмотря на то, что отдельные операции могут быть O(n). Выбор коэффициента роста — компромисс между временем копирования и фрагментацией памяти. В C# List<T> использует удвоение ёмкости, в Python — более сложную стратегию, включающую деление с остатком от предыдущего размера, чтобы уменьшить избыточное выделение.

Динамические массивы обеспечивают быстрый прямой доступ и эффективный кэш-локальный обход, но неэффективны при вставке/удалении в середине: такие операции требуют сдвига всех последующих элементов, что даёт O(n).

1.3 Разрежённые массивы

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

Реализуется разрежённый массив, как правило, на основе хеш-таблицы или сбалансированного дерева, обеспечивая компромисс между временем доступа и объёмом памяти.

1.4 Зигзагообразные (jagged) массивы

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

В языках вроде C# различие между int[,] (прямоугольный) и int[][] (зигзагообразный) проявляется и в производительности, и в семантике. Прямоугольные массивы имеют лучшее поведение кэширования и меньший оверхед памяти, но менее гибки.

---

2. Списки

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

2.1 Односвязный список

Каждый узел односвязного списка содержит полезные данные и указатель на следующий узел. Последний узел указывает на null. Основные операции:

• Вставка в начало: O(1)
• Удаление по ссылке на предыдущий: O(1)
• Поиск по значению: O(n)
• Доступ по индексу: O(n)

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

2.2 Двусвязный список

Двусвязный список содержит два указателя в каждом узле: на предыдущий и следующий элементы. Это позволяет обходить список в обоих направлениях и реализовывать операции удаления без знания предыдущего узла. Стандартные реализации (например, LinkedList<T> в .NET или std::list в C++) обычно используют двусвязный вариант.

Недостаток — увеличенный объём памяти на узел и снижение эффективности кэширования из-за несмежного размещения.

2.3 Циклические списки

Циклический список — это связный список, в котором последний узел указывает не на null, а на первый (в односвязном случае) или на первый и последний соответственно (в двусвязном). Такая структура удобна при реализации кольцевых буферов, планировщиков задач или в сценариях, где требуется бесконечное вращение по набору элементов без явной проверки границ.

Важно при работе с циклическими списками избегать бесконечных циклов обхода: условие завершения должно быть логическим, а не основанным на достижении null.

3. Стеки и очереди

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

3.1 Стек (LIFO — Last In, First Out)

Стек поддерживает две основные операции:

• push(x) — добавление элемента на вершину стека;
• pop() — извлечение и удаление верхнего элемента.

Дополнительно может присутствовать peek() или top() — просмотр верхнего элемента без удаления.

Реализация на динамическом массиве.
Этот подход обеспечивает O(1) амортизированное время для push и pop, отличную кэш-локальность и компактное представление в памяти. Большинство стандартных библиотек (например, Stack<T> в .NET или ArrayDeque в Java как стек) предпочитают именно такую реализацию. Однако при интенсивном росте возможны паузы из-за реаллокации.

Реализация на односвязном списке.
Каждый push создаёт новый узел, указывающий на предыдущий; pop освобождает голову списка. Преимущества — отсутствие реаллокации, гарантированный O(1) без амортизации. Недостатки — фрагментация памяти, плохая кэш-локальность, накладные расходы на узлы.

Инженерные соображения.
Стек часто используется в системах с жёсткими требованиями к предсказуемости (real-time systems). В таких случаях предпочтение отдаётся статическому массиву фиксированного размера, чтобы избежать динамических аллокаций. Переполнение стека в этом случае обрабатывается как критическая ошибка. Пример — стек вызовов в embedded-системах или виртуальных машинах с ограниченной памятью.

3.2 Очередь (FIFO — First In, First Out)

Очередь поддерживает:

• enqueue(x) — добавление в конец;
• dequeue() — извлечение из начала.

Реализация на связном списке.
Наиболее прямолинейна: поддерживается указатель на голову (для dequeue) и хвост (для enqueue). Обе операции — O(1). Однако, как и в случае со стеком на списке, страдает эффективность кэширования.

Реализация на массиве: кольцевой буфер (circular buffer).
Используется фиксированный массив и два индекса: head (начало) и tail (конец). При достижении конца массива индексы «зацикливаются» с помощью операции по модулю:

tail = (tail + 1) % capacity;

Такой подход устраняет необходимость перемещения данных при dequeue, обеспечивает O(1) для обеих операций и отличную кэш-локальность. Однако требует заранее известного максимального размера или механизма роста (что усложняет логику, так как при росте элементы нужно копировать в новую область с сохранением порядка).

Динамические очереди на основе двух стеков.
Теоретически возможна реализация очереди через два стека: один для входа, второй — для выхода. При dequeue, если выходной стек пуст, все элементы из входного переносятся в выходной (что инвертирует порядок). Амортизированная сложность остаётся O(1). На практике этот метод редко используется из-за высокой константы и неэффективного использования памяти, но он полезен в функциональных языках, где изменяемые структуры недоступны.

Дек (двусторонняя очередь).
Расширение очереди, допускающее вставку и удаление с обоих концов. В Java — ArrayDeque, в C++ — std::deque. Реализуется либо как кольцевой буфер с возможностью роста в обе стороны, либо как массив указателей на фиксированные блоки («буфер блоков»), что позволяет избегать частых реаллокаций и сохранять близость к O(1) для всех операций.

---

4. Хеш-таблицы

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

4.1 Принцип работы

Хеш-таблица отображает ключи в индексы массива («корзины») с помощью хеш-функции h(key). Идеальная хеш-функция равномерно распределяет ключи, минимизируя коллизии — ситуации, когда разные ключи отображаются в одну и ту же ячейку.

4.2 Методы разрешения коллизий

4.2.1 Цепочки (chaining)
Каждая ячейка массива содержит список (или дерево) пар «ключ–значение». При коллизии новый элемент добавляется в список. Преимущества:

• Простота реализации;
• Устойчивость к плохому распределению хешей;
• Поддержка неограниченного числа элементов (теоретически).

Недостатки:

• Выделение дополнительных узлов для списка;
• Потеря кэш-локальности при обходе цепочки.

В современных реализациях (например, в Java 8+) при превышении порога длины цепочки (обычно 8 элементов) она преобразуется в сбалансированное дерево (красно-чёрное), что снижает асимптотику поиска в худшей ситуации с O(n) до O(log n).

4.2.2 Открытая адресация (open addressing)
Все элементы хранятся непосредственно в массиве. При коллизии применяется функция пробирования для поиска следующей свободной ячейки. Распространённые стратегии:

• Линейное пробирование: h_i(key) = (h(key) + i) mod m;
• Квадратичное пробирование: h_i(key) = (h(key) + c1·i + c2·i²) mod m;
• Двойное хеширование: h_i(key) = (h1(key) + i·h2(key)) mod m.

Преимущества:

• Высокая кэш-локальность (все данные в одном массиве);
• Отсутствие дополнительных аллокаций.

Недостатки:

• Чувствительность к загрузке (load factor). При α > 0.7 производительность резко падает;
• Удаление требует пометки ячеек как «удалённых» (tombstone), чтобы не нарушить цепочку пробирования;
• Сложность масштабирования: при росте таблицы требуется полная перестройка.

Python (словари), CPython и Lua используют открытую адресацию с линейным или смешанным пробированием.

4.3 Универсальное хеширование

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

В .NET хеш-коды для строк могут быть рандомизированы (опция DOTNET_SYSTEM_GLOBALIZATION_USE_RANDOMIZED_HASHING), что защищает от DoS-атак через хеш-коллизии.

4.4 Выбор хеш-функции

Хорошая хеш-функция должна быть:

• Быстрой (несколько тактов процессора);
• Равномерной (минимизация смещения и корреляции);
• Нечувствительной к малым изменениям входа (лавинный эффект).

Для целых чисел часто используется тождественное отображение или умножение на большую нечётную константу. Для строк — алгоритмы вроде FNV-1a, MurmurHash, CityHash или SipHash (последний — криптографически устойчивый, применяется в Python и Rust).

5. Бинарные кучи и приоритетные очереди

Приоритетная очередь — это абстрактный тип данных, в котором каждый элемент ассоциирован с приоритетом, и извлечение всегда происходит по элементу с наивысшим (в max-куче) или наинизшим (в min-куче) приоритетом. Наиболее распространённая и эффективная реализация приоритетной очереди — бинарная куча, представленная в виде почти полного двоичного дерева, хранящегося в массиве.

5.1 Структура бинарной кучи

Бинарная куча обладает двумя ключевыми свойствами:

1. Форма: дерево является почти полным — все уровни, кроме, возможно, последнего, полностью заполнены, а последний уровень заполнен слева направо.
2. Порядок: в max-куче значение любого узла не меньше значений его потомков; в min-куче — наоборот.

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

• Левый потомок: 2·i + 1
• Правый потомок: 2·i + 2
• Родитель: ⌊(i – 1)/2⌋

Это позволяет реализовать кучу с минимальными накладными расходами: один массив, O(1) дополнительной памяти, отличная кэш-локальность.

5.2 Основные операции

5.2.1 Вставка (insert)
Новый элемент добавляется в конец массива (сохраняя свойство формы), затем выполняется просеивание вверх (sift-up): элемент сравнивается с родителем и, если нарушено свойство порядка, меняется местами. Процесс продолжается до корня или до восстановления порядка.
Сложность: O(log n).

5.2.2 Извлечение максимума/минимума (extract)
Корневой элемент (экстремум) удаляется и возвращается. На его место перемещается последний элемент массива, после чего выполняется просеивание вниз (sift-down): узел сравнивается с потомками и меняется местами с наибольшим (в max-куче) или наименьшим (в min-куче) из них. Процесс продолжается до листа или до восстановления порядка.
Сложность: O(log n).

5.2.3 Построение кучи из массива (heapify)
Наивный подход — последовательная вставка всех элементов — даёт O(n log n). Однако существует линейный алгоритм: начиная с последнего внутреннего узла (индекс ⌊n/2⌋ – 1) и двигаясь к корню, выполняется sift-down.
Сложность: O(n). Это возможно благодаря тому, что большинство узлов находятся в нижних уровнях дерева, где высота мала.

5.3 Инженерные аспекты реализации

5.3.1 Выбор представления
Хотя теоретически куча может быть реализована и на связанных узлах, массивное представление доминирует в практике из-за:

• отсутствия аллокаций при каждой операции;
• предсказуемого поведения кэша (элементы дерева хранятся последовательно);
• простоты вычисления индексов.

5.3.2 Кэш-эффективные варианты: d-арные кучи
Вместо двух потомков у каждого узла допускается d потомков (обычно d = 4 или 8). Это уменьшает высоту дерева, сокращая число операций sift-down при извлечении. Однако увеличивается число сравнений на каждом уровне.
Компромисс выгоден в сценариях, где вставка происходит значительно реже извлечения, например, в алгоритме Дейкстры с плотным графом.
В стандартной библиотеке C++ (std::priority_queue) используется бинарная куча, но библиотеки вроде Intel TBB предлагают d-арные кучи для высоконагруженных систем.

5.3.3 Потокобезопасность
Обычная куча не является потокобезопасной. Для многопоточной среды применяются:

• внешняя синхронизация (блокировки);
• lock-free реализации на основе CAS-операций (редки из-за сложности);
• использование нескольких куч с последующим слиянием (подход в некоторых scheduler’ах ОС).

5.3.4 Применение в алгоритмах

• Сортировка кучей (Heapsort): построение кучи + n извлечений → O(n log n), in-place, нестабильная.
• Алгоритмы на графах: Дейкстра, Прим — требуют эффективного обновления приоритетов. Стандартная куча не поддерживает decrease-key напрямую; для этого используются бинарные кучи с обратными индексами или фибоначчиевы кучи (в теории).
• Планировщики задач: выполнение задач по приоритету (например, в ОС или message queues).

5.4 Ограничения и альтернативы

Стандартная бинарная куча не поддерживает:

• эффективный поиск произвольного элемента (O(n));
• изменение приоритета существующего элемента без внешнего индекса.

В случаях, где такие операции критичны (например, в интерактивных симуляторах), применяются:

• Индексированные кучи: хранят дополнительный массив, сопоставляющий элементы с их позициями в куче;
• Балансированные деревья поиска (например, TreeSet в Java): поддерживают все операции за O(log n), включая удаление по ключу и итерацию в порядке сортировки, но с худшей кэш-локальностью и большим оверхедом.

6. Деревья поиска

6.1 Двоичные деревья поиска (BST — Binary Search Tree)

Двоичное дерево поиска — это упорядоченное двоичное дерево, в котором для любого узла выполняется:

• все ключи в левом поддереве меньше ключа узла;
• все ключи в правом поддереве больше или равны (в зависимости от соглашения).

Это свойство позволяет выполнять поиск, вставку и удаление за время, пропорциональное высоте дерева: O(h).

Проблема несбалансированности

В худшем случае (при вставке отсортированной последовательности) дерево вырождается в связный список: h = n, и все операции становятся O(n). Это делает наивное BST непригодным для production-сценариев без дополнительных мер.

6.2 Самобалансирующиеся деревья

Чтобы гарантировать h = O(log n), применяются стратегии автоматического восстановления баланса после модификаций.

6.2.1 AVL-дерево
Самый ранний вариант сбалансированного дерева (1962). Инвариант: для любого узла разность высот левого и правого поддеревьев («баланс-фактор») не превышает 1 по модулю.

• Поддержание баланса достигается через вращения (левые, правые, комбинированные);
• После каждой вставки/удаления может потребоваться до O(log n) вращений;
• Высота дерева строго ограничена: h < 1.44·log₂(n + 2) – 0.328.

AVL-деревья оптимальны для читающих систем, где поиск значительно чаще модификаций, так как обеспечивают минимально возможную высоту.

6.2.2 Красно-чёрные деревья (Red-Black Tree)
Более «ленивый» подход к балансировке, используемый в std::map (C++), TreeMap (Java), ядре Linux (для планировщика).

Свойства:

1. Каждый узел либо красный, либо чёрный.
2. Корень — чёрный.
3. Все листья (NIL) — чёрные.
4. Красный узел не может иметь красного родителя.
5. Любой путь от узла до его листьев содержит одинаковое число чёрных узлов.

Из этого следует: высота h ≤ 2·log₂(n + 1).
Преимущества перед AVL:

• меньше вращений при вставке/удалении (в среднем O(1) против O(log n));
• лучше подходит для часто изменяемых структур.

Недостаток — дерево может быть на ~30% выше, чем AVL, что немного замедляет поиск.

6.3 Инженерные аспекты

• Узлы обычно содержат указатели на родителя, левого и правого потомков, а также служебные поля (цвет в RB-дереве).
• Для уменьшения фрагментации памяти в высоконагруженных системах применяется пул аллокаторов.
• В языках с GC (Java, C#) такие деревья безопасны, но создают давление на сборщик мусора при частых обновлениях.

---

7. B-деревья и их варианты

7.1 Мотивация: иерархия памяти

В то время как двоичные деревья оптимизированы под оперативную память, B-деревья разработаны для сред с высокой латентностью доступа, таких как диски (HDD/SSD) или сетевые хранилища. Основная идея: минимизировать количество обращений к медленному устройству, максимизируя полезную нагрузку в каждом блоке.

7.2 Структура B-дерева

B-дерево порядка m — это сбалансированное дерево, в котором:

• каждый узел содержит до m – 1 ключей и до m потомков;
• все листья находятся на одном уровне;
• внутренние узлы хранят ключи-разделители для навигации;
• листья содержат фактические данные (в классической версии) или указатели на них.

Пример (B-дерево порядка 4):

        [20|40]
       /   |    \
[5|10|15] [25|30|35] [45|50|55]

Каждый узел соответствует одному дисковому блоку (обычно 4 КБ). Чтение одного узла — одна I/O-операция.

7.3 B⁺-деревья

Наиболее распространённый вариант в СУБД (PostgreSQL, MySQL InnoDB, Oracle).

Отличия от классического B-дерева:

• Все данные хранятся только в листьях;
• Листья связаны в двусвязный список, что позволяет эффективно выполнять диапазонные запросы (range scans);
• Внутренние узлы содержат только ключи-разделители.

Это даёт два ключевых преимущества:

1. Повышенная плотность внутренних узлов → меньшая высота → меньше I/O;
2. Последовательное чтение листьев при диапазонных запросах — критично для аналитических нагрузок.

7.4 Реализация и оптимизации

• Размер узла обычно выравнивается по границе страницы ОС (4 КБ);
• При вставке, если узел переполнен, он расщепляется на два;
• При удалении, если узел становится менее чем наполовину заполнен, выполняется слияние или перераспределение с соседом;
• Для уменьшения блокировок в СУБД применяются ленивые (latch-free) алгоритмы, copy-on-write или версионирование (MVCC).

---

8. Суффиксные структуры: массивы и деревья

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

• биоинформатике (поиск паттернов в ДНК);
• полнотекстовом поиске;
• сжатии данных (алгоритмы вроде Burrows–Wheeler Transform);
• обнаружении плагиата.

8.1 Суффиксный массив (Suffix Array)

Суффиксный массив — это отсортированный массив индексов всех суффиксов строки.

Для строки S = "banana$" (с терминатором $):

• Суффиксы: "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$"
• Сортировка: "$", "a$", "ana$", "anana$", "banana$", "na$", "nana$"
• Суффиксный массив: [6, 5, 3, 1, 0, 4, 2]

Преимущества:

• Потребляет 4n–8n байт (в зависимости от типа индекса), что в 3–5 раз меньше, чем суффиксное дерево;
• Поддерживает быстрый поиск подстроки за O(m·log n) с помощью бинарного поиска по суффиксам;
• С дополнительными структурами (LCP-массивом) можно достичь O(m + log n).

Построение

Наивный метод — сортировка всех суффиксов — O(n² log n). Современные алгоритмы (SA-IS, DC3) строят массив за O(n) времени и O(n) памяти.

8.2 Суффиксное дерево (Suffix Tree)

Суффиксное дерево — это сжатое префиксное дерево (trie), содержащее все суффиксы строки как пути от корня к листьям.

Для той же строки "banana$" дерево будет содержать ветви для каждого уникального префикса суффиксов.

Свойства:

• Построение за O(n) (алгоритм Укконена);
• Поиск подстроки за O(m) — оптимально;
• Поддержка сложных запросов: самый длинный повторяющийся подстрок, наименьший общий предок (LCA) для LCP и др.

Недостатки:

• Высокое потребление памяти: до 20n–40n байт из-за указателей и метаданных;
• Сложность реализации.

Поэтому на практике суффиксные массивы почти всегда предпочтительнее, особенно в 64-битных системах, где указатели занимают 8 байт.

8.3 Современные гибриды

• FM-индекс (на основе BWT и суффиксного массива) — используется в bwa, bowtie для выравнивания геномов; поддерживает сжатое представление с возможностью поиска.
• Wavelet-деревья — позволяют не только искать, но и выполнять ранг/селект-запросы, что полезно в сжатых структурах данных.

9. Графовые структуры данных

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

9.1 Матрица смежности (Adjacency Matrix)

Матрица смежности — это двумерный массив A размером n × n, где A[i][j] = 1 (или вес ребра), если существует ребро из вершины i в j, и 0 (или ∞) в противном случае.

Свойства:

• Прямой доступ: проверка существования ребра — O(1);
• Простота реализации: особенно для плотных графов;
• Поддержка взвешенных и мультиграфов через значения ячеек.

Недостатки:

• Память: O(n²), что неприемлемо при больших n (например, для соцсети с 1 млрд пользователей — 10¹⁸ ячеек);
• Итерация по соседям: O(n), даже если степень вершины мала;
• Неэффективна для разреженных графов (где число рёбер m ≪ n²).

Применение:

• Алгоритмы, требующие частой проверки рёбер (например, Floyd–Warshall для всех пар кратчайших путей);
• Малые графы (до нескольких тысяч вершин);
• Теоретические задачи, где важна математическая интерпретация (спектральный анализ).

9.2 Список смежности (Adjacency List)

Список смежности — это массив (или хеш-таблица) из n элементов, где каждый элемент содержит список соседей данной вершины.

Реализации:

• vector<vector<int>> (C++);
• List<List<Node>> или Map<Node, List<Node>> (Java/C#);
• dict[int, list[int]] (Python).

Свойства:

• Память: O(n + m) — оптимально для разреженных графов;
• Итерация по соседям: O(deg(v)) — линейно от степени вершины;
• Добавление ребра: O(1) (в конец списка).

Недостатки:

• Проверка существования ребра: O(deg(v)) — нужно просканировать список;
• Удаление ребра: O(deg(v)) без двусвязного списка;
• Фрагментация памяти, если списки выделяются отдельно.

Применение:

• Большинство алгоритмов обхода: BFS, DFS, Dijkstra, Tarjan;
• Социальные графы, маршрутизация, семантические сети.

9.3 Compressed Sparse Row (CSR) — сжатое разреженное строковое представление

CSR — это компактное и кэш-эффективное представление разреженных графов, заимствованное из линейной алгебры. Используется в high-performance computing и графовых базах данных.

Структура:

Три массива:

1. values — список всех рёбер (или весов), упорядоченных по исходной вершине;
2. col_indices — для каждого элемента в values — индекс конечной вершины;
3. row_ptr — длина n + 1, где row_ptr[i] — позиция в values, с которой начинаются рёбра из вершины i.

Пример для графа:

0 → 1, 2  
1 → 2  
2 → 0

values      = [1, 2, 2, 0]
col_indices = [1, 2, 2, 0]
row_ptr     = [0, 2, 3, 4]

Преимущества:

• Непрерывное хранение данных → отличная кэш-локальность;
• Память: O(n + m), без указателей;
• Параллелизм: строки (исходные вершины) независимы — идеально для GPU и SIMD;
• Поддержка только чтения — оптимален для аналитических нагрузок.

Недостатки:

• Невозможно эффективно модифицировать — вставка ребра требует перестройки массивов;
• Сложность реализации.

Применение:

• Графовые процессоры (GraphBLAS, cuGraph);
• PageRank, связность, распространение влияния;
• Библиотеки вроде SciPy (scipy.sparse.csr_matrix).

9.4 Property Graphs — графы со свойствами

Property Graph — это модель данных, используемая в графовых базах данных (Neo4j, Amazon Neptune, JanusGraph). Отличается от математического графа тем, что:

• Вершины и рёбра могут иметь свойства в виде пар «ключ–значение»;
• Рёбра имеют тип (label): например, KNOWS, WORKS_AT;
• Рёбра всегда направленные, но могут быть запрошены как ненаправленные.

Пример:

(Алекс {age: 30}) -[KNOWS {since: 2020}]-> (Мария {age: 28})

Хранение в СУБД:

• Вершины и рёбра хранятся как отдельные записи;
• Индексы по:
  • ID вершин;
  • типу рёбер;
  • свойствам (для фильтрации);
• Для быстрого обхода используются adjacency lists на диске с кэшированием.

Neo4j, например, использует native graph storage: каждый узел содержит указатели на первое входящее и исходящее ребро, а рёбра образуют двусвязные списки по направлению. Это позволяет обходить соседей без полного сканирования.

Компромиссы:

• Гибкость модели vs. сложность оптимизации запросов;
• ACID-транзакции возможны, но дороже, чем в реляционных СУБД;
• Масштабирование — горизонтальное (шардинг по вершинам) остаётся сложной задачей из-за связности.

10. Вероятностные и потоковые структуры данных

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

10.1 Фильтр Блума (Bloom Filter)

Фильтр Блума — это компактная структура данных для проверки принадлежности элемента множеству с возможностью ложноположительных срабатываний, но без ложноотрицательных.

Принцип работы

• Инициализируется битовый массив длиной m, заполненный нулями.
• Используется k независимых хеш-функций h₁, ..., hₖ.
• При добавлении элемента x: устанавливаются биты h₁(x), ..., hₖ(x) в 1.
• При проверке: если все соответствующие биты равны 1 — элемент возможно в множестве; если хотя бы один бит 0 — элемент точно отсутствует.

Свойства

• Память: O(m), независимо от числа элементов.
• Операции: O(k) — константное время.
• Ложноположительная вероятность

Инженерные аспекты

• Невозможность удаления в классическом варианте (биты могут быть общими для разных элементов).
• Counting Bloom Filter: заменяет биты на счётчики (обычно 4 бита), что позволяет удалять элементы, но увеличивает память в 4–8 раз.
• Scalable Bloom Filters: динамически расширяются при превышении порога ошибки.
• Применение:
  • Проверка существования ключа в распределённой БД (Bigtable, Cassandra) — избегает дорогих дисковых I/O;
  • Спам-фильтрация (быстрая проверка на чёрный список);
  • Кэш-валидация (например, в CDN — есть ли ресурс в origin?).

Важно: Bloom Filter не хранит сами элементы и не поддерживает итерацию. Это оракул принадлежности, а не контейнер.

---

10.2 Count-Min Sketch

Count-Min Sketch (CMS) — структура для оценки частоты встречаемости элементов в потоке данных. Позволяет отвечать на запросы вида «сколько раз встречался ключ x?» с гарантированной верхней границей погрешности.

Принцип работы

• Матрица из d строк и w столбцов, все ячейки = 0.
• d независимых хеш-функций, каждая отображает ключ в [0, w).
• При обновлении счётчика для x: инкрементировать table[i][hᵢ(x)] для всех i.
• При запросе частоты: вернуть минимум по всем table[i][hᵢ(x)].

Почему минимум? Потому что коллизии только увеличивают значения (отсюда «min» даёт наименее завышенную оценку).

Свойства

• Память: O(ε⁻¹ log δ⁻¹)
• Операции: O(log δ⁻¹)
• Оценка завышена, но никогда не занижена.

Применение

• Обнаружение «тяжёлых» ключей (heavy hitters) — например, самых запрашиваемых URL;
• Анализ сетевого трафика (NetFlow, DDoS-детекция);
• Приближённые JOIN’ы в потоковых СУБД (Apache Flink, Kafka Streams);
• Системы рекомендаций (оценка популярности).

Варианты

• Conservative Update: уменьшает погрешность для редких элементов;
• Hierarchical CMS: для распределённых систем с агрегацией.

---

10.3 Другие вероятностные структуры

HyperLogLog

Оценивает количество уникальных элементов (кардинальность) с погрешностью ~1.5%, используя всего 1.5 КБ памяти независимо от объёма данных.

Применяется в Redis (PFADD, PFCOUNT), Google Analytics, рекламных системах.

Cuckoo Filter

Альтернатива Bloom Filter с поддержкой удаления и лучшей локальностью данных за счёт хранения «отпечатков» (fingerprints) в хеш-таблице с двумя возможными позициями.

Quotient Filter

Ещё одна замена Bloom Filter, поддерживающая слияние и удаление, с меньшим оверхедом памяти.

---

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

Структура	Тип ошибки	Память	Используется в
Bloom Filter	Ложноположительная	Очень низкая	Cassandra, Bitcoin (SPV), Squid
Count-Min Sketch	Завышенная оценка	Низкая	Akamai, Flink, мониторинг
HyperLogLog	Относительная погрешность	1–2 КБ	Redis, Druid, Google BigQuery
Cuckoo Filter	Ложноположительная	Ниже Bloom	Новые СУБД, secure routing

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

11. Реализация структур данных в системном ПО

11.1 Операционные системы

11.1.1 Планировщик задач (scheduler)

• Структура: красно-чёрное дерево (Linux, начиная с ядра 2.6.23, в Completely Fair Scheduler — CFS).
• Ключ: vruntime (виртуальное время исполнения процесса).
• Почему не куча? Планировщик должен:
  • быстро находить задачу с минимальным vruntime (как в куче),
  • но также поддерживать балансировку по группам (cgroups), удаление произвольных задач (при завершении), изменение приоритета.
• Итог: RB-дерево даёт O(log n) для всех операций с поддержкой итерации и модификации — куча этого не обеспечивает.

11.1.2 Управление виртуальной памятью

• Структура: radix-дерево (Linux) или сбалансированное B-дерево (Windows) для хранения VMA (Virtual Memory Areas).
• Задача: быстро находить регион памяти по адресу, объединять/разделять регионы при mmap/munmap.
• Radix-дерево эффективно для диапазонных запросов и обладает хорошей кэш-локальностью.

11.1.3 Кэши ядра (slab allocator)

• Структура: связные списки и битовые карты.
• Цель: выделение объектов фиксированного размера (например, task_struct) без фрагментации.
• Аналог в пользовательском пространстве — memory pool.

---

11.2 Системы управления базами данных (СУБД)

11.2.1 Индексы

• B⁺-деревья — стандарт де-факто для дисковых СУБД (PostgreSQL, MySQL InnoDB, Oracle, SQL Server).

  • Хранятся в страницах, выровненных по границе блока ОС (обычно 4–16 КБ).
  • Поддерживают многоверсионность (MVCC) через временные метки или undo-логи.
  • В InnoDB: листья B⁺-дерева содержат кластеризованные данные (clustered index), что ускоряет диапазонные запросы.

• LSM-деревья (Log-Structured Merge Trees) — в NoSQL и аналитических СУБД (Cassandra, RocksDB, ScyllaDB).

  • Данные сначала пишутся в memtable (skip-list или AVL-дерево в памяти),
  • При переполнении сбрасываются в неизменяемый SSTable на диск,
  • Фоновые процессы сливают SSTable’ы.
  • Преимущество: высокая write-throughput, особенно на SSD.
  • Недостаток: read amplification (нужно проверить несколько уровней).

11.2.2 Хэш-индексы

• Используются в in-memory СУБД (Redis, Memcached, VoltDB).
• Реализация: открытая адресация или цепочки.
• Ограничение: не поддерживают диапазонные запросы.

11.2.3 Векторные индексы (AI/ML)

• Современные СУБД (PostgreSQL + pgvector, Milvus, Pinecone) используют приближённые структуры:
  • HNSW (Hierarchical Navigable Small World) — граф, оптимизированный для поиска ближайших соседей в высоких размерностях;
  • IVF (Inverted File Index) — разбиение пространства на кластеры, поиск только в ближайших.
• Эти структуры — гибриды графов, хэшей и деревьев.

---

11.3 Runtime-окружения (CLR, JVM, V8)

11.3.1 Сборка мусора

• Remembered sets (в generational GC) — реализуются как битовые карты или хэш-таблицы для отслеживания ссылок из старого поколения в новое.
• Card tables — массив байтов, где каждый байт «покрывает» 512 байт кучи; модификация помечает «карту» как «грязную».

11.3.2 Коллекции

• .NET (List<T>, Dictionary<TKey, TValue>, SortedSet<T>):

  • List<T> — динамический массив;
  • Dictionary<,> — хэш-таблица с открытой адресацией и двойным хешированием;
  • SortedSet<T> — красно-чёрное дерево.

• Java (ArrayList, HashMap, TreeMap):

  • HashMap — массив + цепочки → дерево при длине > 8;
  • ConcurrentHashMap — сегментированная блокировка (раньше) или CAS + bins (с Java 8).

• V8 (JavaScript):

  • Массивы хранятся как fast elements (непрерывный массив) или dictionary mode (хэш-таблица) при разреженности;
  • Объекты — hidden classes + shape trees, что позволяет оптимизировать доступ к полям.

---