Основные структуры данных и их реализация

Play ITЗагрузка интерактивного демо…

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

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

Основные структуры данных и их реализация

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

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

Сначала пробежимся по всем:

Массивы — сплошной блок памяти, очень быстрый доступ по номеру ячейки, но вставка/удаление в середину — всё сдвигать.
Списки — цепочка элементов, где каждый знает следующего; быстрое добавление/удаление, но поиск — полный перебор.
Стек и очередь — это просто правила поведения (LIFO и FIFO), ими делают на массивах или списках.
Хеш-таблица — как картотека — хеш-функция превращает ключ в номер ящичка, почти мгновенный доступ, но при коллизиях (два ключа в один ящик) нужны запасные варианты.
Бинарная куча — дерево, где родитель всегда старше детей (записано компактно в массив), используется для очередей с приоритетом.
Деревья поиска — упорядоченные структуры, где слева меньшие, справа большие; двоичные деревяшки вырождаются в список, поэтому используют самобалансирующиеся (AVL, красно-чёрные) для гарантированного O(log n).
B-деревья — толстые, широкие, оптимизированы под диски и базы данных (один узел = один диск-блок).
Суффиксные массивы — все окончания строки отсортировали, чтобы быстро искать подстроки; экономят память по сравнению с суффиксными деревьями.
Графы хранят либо матрицей (все-со-всеми, O(n²) памяти), либо списками соседей (экономично, когда рёбер мало).
Вероятностные и компактные структуры (Bloom Filter, HyperLogLog, Cuckoo Filter, MinHash, Skip List, Count-Min Sketch) — отвечают на типовые вопросы о множествах и потоках без хранения всех элементов; часть допускает контролируемую погрешность ради памяти и скорости.

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

Рабочий принцип выбора

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

Как читать эту главу

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

Разделы 1–4 (массивы, списки, стек/очередь, хеш) — база на каждый день; 5–9 — деревья, графы и специализированные структуры; 10–11 — вероятностные структуры и связь с ОС/СУБД.

Алгоритмический справочник (псевдокод)

Ниже — как работают операции, без привязки к синтаксису. В Java это list.get(i), в Python lst[i], в Go s[i] — смысл один.

Play ITЗагрузка интерактивного демо…

Массив и динамический массив

АЛГОРИТМ Получить(массив, индекс)
  адрес := база + индекс * размер_элемента
  вернуть прочитать(адрес)          // O(1)
КОНЕЦ

АЛГОРИТМ ДобавитьВКонец(динамический_массив, значение)
  если размер = ёмкость то
    ёмкость := ёмкость * 2
    новый_буфер := выделить(ёмкость)
    скопировать(старый_буфер → новый_буфер)
  конец
  буфер[размер] := значение
  размер := размер + 1             // амортизированно O(1)
КОНЕЦ

АЛГОРИТМ ВставитьВСередину(массив, индекс, значение)
  для i от размер-1 до индекс шаг -1
    массив[i+1] := массив[i]       // сдвиг вправо — O(n)
  конец
  массив[индекс] := значение
  размер := размер + 1
КОНЕЦ

Связный список

УЗЕЛ
  поле значение
  поле следующий
КОНЕЦ

АЛГОРИТМ НайтиПоИндексу(голова, индекс)
  текущий := голова
  для i от 0 до индекс-1
    текущий := текущий.следующий     // O(n)
  конец
  вернуть текущий
КОНЕЦ

АЛГОРИТМ ВставитьПосле(узел, новое_значение)
  новый := новый УЗЕЛ(новое_значение)
  новый.следующий := узел.следующий
  узел.следующий := новый            // O(1), если узел уже найден
КОНЕЦ

Стек (LIFO) и очередь (FIFO)

АЛГОРИТМ Стек_Положить(стек, x)
  стек.добавить_на_вершину(x)        // O(1) на массиве или списке
КОНЕЦ

АЛГОРИТМ Стек_Снять(стек)
  если стек.пусто то ошибка "переполнение"
  вернуть стек.удалить_с_вершины()
КОНЕЦ

АЛГОРИТМ Очередь_ВКонец(очередь, x)
  очередь.хвост := x                   // на списке: хвост.next := x
КОНЕЦ

АЛГОРИТМ Очередь_СНачала(очередь)
  x := очередь.голова
  очередь.голова := очередь.голова.следующий
  вернуть x                          // O(1) на списке или кольцевом буфере
КОНЕЦ

Кольцевой буфер (очередь на массиве):

АЛГОРИТМ Кольцо_ВКонец(буфер, голова, хвост, x)
  буфер[хвост] := x
  хвост := (хвост + 1) mod ёмкость    // без сдвига всего массива
КОНЕЦ

Хеш-таблица (словарь)

АЛГОРИТМ Словарь_Записать(таблица, ключ, значение)
  idx := хеш(ключ) mod таблица.ёмкость
  если метод = "цепочки" то
    добавить_пару_в_список(таблица.корзины[idx], ключ, значение)
  иначе
    пока таблица.ячейки[idx] занята и ключ ≠ занятый_ключ
      idx := (idx + 1) mod таблица.ёмкость   // линейное пробирование
    конец
    таблица.ячейки[idx] := (ключ, значение)
  конец
КОНЕЦ

АЛГОРИТМ Словарь_Прочитать(таблица, ключ)
  idx := хеш(ключ) mod таблица.ёмкость
  найти пару (ключ, значение) в корзине idx
  если не найдено то ошибка "нет ключа"
  вернуть значение                    // в среднем O(1)
КОНЕЦ

АТД	Главные операции	Массив	Связный список	Хеш
Список по индексу	get/set	O(1) get	O(n) get	—
Вставка в середину	insert	O(n)	O(1)*	—
Стек	push/pop	O(1)*	O(1)	—
Очередь	enqueue/dequeue	O(1)* кольцо	O(1)	—
Словарь	get/put по ключу	—	O(n)	O(1) среднее

* при известном индексе/узле или амортизации на динамическом массиве.

Теория O(·)

Смысл обозначений, порядок классов от O(1) до O(n!) и примеры на алгоритмах — в Нотация Большое O.

Таблица операций ниже в коде на Python — Lab / Big-O — шпаргалка.

1. Массивы

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

Буквально:

массив = [элемент1, элемент2, элемент3]

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

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

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

То же на псевдокоде — см. Получить выше.

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

JavaScript:

// Фиксированная длина: new Array(n) или TypedArray
const colors = new Array(3);
colors[0] = "red";
colors[1] = "green";
colors[2] = "blue";
// Обычный литерал ["red", "green", "blue"] в JS может расти — это уже динамический массив

Python:

# list в Python динамический; для плотного фиксированного блока — array.array
from array import array
numbers = array("i", [1, 2, 3, 4, 5])  # "i" — signed int

C#:

// Статический массив в C# с фиксированным размером
int[] values = new int[10];
values[0] = 1;
values[1] = 2;

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

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

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

Python:

# Добавление элементов происходит автоматически
list_data = []
list_data.append(10)
list_data.append(20)
list_data.append(30)
print(list_data)  # [10, 20, 30]

Java:

// ArrayList в Java — динамическая структура
ArrayList<Integer> dynamicList = new ArrayList<>();
dynamicList.add(5);
dynamicList.add(15);
dynamicList.add(25);
System.out.println(dynamicList);  // [5, 15, 25]

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

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

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

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

Python:

# Хранение только ненулевых значений
sparse_array = {
    0: 10,
    100: 50,
    1000: 200
}
# Остальные элементы считаются нулями

C#:

// Dictionary как реализация разрежённого массива
Dictionary<int, int> sparseData = new Dictionary<int, int>();
sparseData.Add(0, 10);
sparseData.Add(100, 50);
sparseData.Add(1000, 200);

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

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

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

Python:

# Массив массивов разной длины
jagged = [
    [1, 2],
    [3, 4, 5],
    [6, 7, 8, 9]
]

C#:

// Целочисленный зигзагообразный массив
int[][] zigzagArray = new int[3][];
zigzagArray[0] = new int[] { 1, 2 };
zigzagArray[1] = new int[] { 3, 4, 5 };
zigzagArray[2] = new int[] { 6, 7, 8, 9 };

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

2. Списки

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

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

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

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

Python:

# Узлы связаны друг с другом через указатель next
node1 = {"value": 10, "next": None}
node2 = {"value": 20, "next": None}
node3 = {"value": 30, "next": None}

node1["next"] = node2
node2["next"] = node3

C#:

// Класс узла односвязного списка
class Node {
    public int Value;
    public Node Next;
    
    public Node(int val) {
        Value = val;
        Next = null;
    }
}

// Создание списка: 1 -> 2 -> 3
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);

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

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

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

Python:

# Два указателя — prev и next
node1 = {"value": 10, "prev": None, "next": None}
node2 = {"value": 20, "prev": None, "next": None}
node3 = {"value": 30, "prev": None, "next": None}

node1["next"] = node2
node2["prev"] = node1
node2["next"] = node3
node3["prev"] = node2

C++:

// Структура узла двусвязного списка на C++
struct DoublyNode {
    int value;
    DoublyNode* prev;
    DoublyNode* next;
};

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

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

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

Python:

# Последний элемент указывает на первый
head = {"value": 10, "next": None}
node2 = {"value": 20, "next": None}
node3 = {"value": 30, "next": None}

head["next"] = node2
node2["next"] = node3
node3["next"] = head  # Цикл замыкается

C#:

// Циклический список
CircularNode first = new CircularNode(10);
CircularNode second = new CircularNode(20);
CircularNode third = new CircularNode(30);

first.Next = second;
second.Next = third;
third.Next = first;  // Замыкание цикла

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

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

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

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

стек.положить(30)
стек.положить(20)
стек.положить(10)
x := стек.снять()    // x = 10 — последним вошёл, первым вышел

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

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

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

Python:

# Последовательность операций со стеком
stack = []
stack.append(10)   # push
stack.append(20)   # push
stack.append(30)   # push
last = stack.pop() # LIFO — последний элемент извлекается первым
print(last)  # 30

Java:

// Стек в Java
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.pop();  // Извлекает 3

Реализация на динамическом массиве.

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

Реализация на односвязном списке.

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

Инженерные соображения.

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

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

очередь.в_конец("A")
очередь.в_конец("B")
очередь.в_конец("C")
первый := очередь.с_начала()   // "A" — кто раньше встал, того раньше обслужили

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

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

Python:

# Предпочтительно — deque — O(1) с обоих концов
from collections import deque
queue = deque()
queue.append(1)   # enqueue в хвост
queue.append(2)
queue.append(3)
first = queue.popleft()  # dequeue из головы
print(first)  # 1

# queue.pop(0) у list — O(n) — только для учебных мини-примеров

Java:

// Очередь в Java
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
String first = queue.poll();  // Извлекает A

Реализация на связном списке.

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

Реализация на массиве: кольцевой буфер (circular buffer).

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

tail = (tail + 1) % capacity;

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

Динамические очереди на основе двух стеков.

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

3.3. Дек (двусторонняя очередь)

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

Python:

# Использование с обеих сторон
from collections import deque
dq = deque()
dq.append(1)      # справа
dq.appendleft(0)  # слева
rightEnd = dq.pop()       # извлекает 1
leftEnd = dq.popleft()    # извлекает 0

Java:

// Deque в Java
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(10);
Integer left = deque.removeFirst();
Integer right = deque.removeLast();

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

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

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

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

index = h(key) mod capacity
bucket[index] → список пар (key, value)

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

4.2.1 Цепочки (chaining)

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

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

Недостатки:

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

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

Python (упрощённая идея цепочек — массив бакетов, в каждом список пар):

SIZE = 8
buckets = [[] for _ in range(SIZE)]

def h(key: str) -> int:
    return hash(key) % SIZE

def put(key, value):
    idx = h(key)
    for i, (k, _) in enumerate(buckets[idx]):
        if k == key:
            buckets[idx][i] = (key, value)
            return
    buckets[idx].append((key, value))

put("port", 80)
put("sport", 443)  # возможна коллизия с "port" — обе пары в одном бакете

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 используют открытую адресацию с линейным или смешанным пробированием.

Python (линейное пробирование — упрощённо):

size = 10
table = [None] * size  # (key, value) или None

def probe_insert(key, value):
    i = hash(key) % size
    for _ in range(size):
        if table[i] is None or table[i][0] == key:
            table[i] = (key, value)
            return
        i = (i + 1) % size
    raise OverflowError("таблица заполнена")

probe_insert("key1", "value1")
probe_insert("key2", "value2")

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Python:

# heapify создаёт минимальную кучу

import heapq

heap = [5, 2, 8, 1, 9]
heapq.heapify(heap)
minValue = heapq.heappop(heap)  # извлекает 1

Java:

// PriorityQueue — реализация бинарной кучи
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
minHeap.add(8);
Integer smallest = minHeap.poll();  // Извлекает 2

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).

Python:

# Структура узла дерева
class TreeNode:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)

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

В худшем случае (при вставке отсортированной последовательности) дерево вырождается в связный список: 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 (для планировщика).

Свойства:

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

Из этого следует: высота 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-дереве ключи и указатели на строки (или сами поля записи) могут лежать и во внутренних узлах, и в листьях — поиск иногда завершается на внутреннем уровне, без спуска к листу.

В дисковых СУБД для индексов таблиц чаще применяют B⁺-дерево (§7.3): данные только в листьях, листья связаны списком для диапазонов. Сравнение пяти типовых структур индексов (B-tree, B⁺, хеш, bitmap, инвертированный) — в основах БД.

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

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

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

Python:

# Упрощённое представление узлов B-дерева
btree_node_1 = {"keys": [20, 40], "children": [node_a, node_b, node_c]}
node_a = {"keys": [5, 10, 15]}
node_b = {"keys": [25, 30, 35]}
node_c = {"keys": [45, 50, 55]}

C#:

// Структура узла B-дерева
class BTreeNode {
    public int[] Keys;
    public BTreeNode[] Children;
    public int Degree;
    public bool IsLeaf;
}

7.3 B⁺-деревья

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

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

Все значения ключей и ссылки на строки хранятся только в листьях;
Листья связаны в двусвязный список — после нахождения начала диапазона движок идёт по горизонтальным указателям без подъёма к корню (BETWEEN, ORDER BY по индексу);
Внутренние узлы содержат только ключи-разделители (навигация).

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

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

Схема "корень → внутренние узлы с границами → листья со значениями и связью лист↔лист" — в пяти основных структурах индексов.

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]

Python:

# Суффиксы строки banana$
string_with_terminator = "banana$"
suffixes = [
    "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$"
]
suffixes.sort()
print(suffixes)  # ['$', 'a$', 'ana$', 'anana$', 'banana$', 'na$', 'nana$']

# Индексы отсортированных суффиксов
suffix_array = [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$" дерево будет содержать ветви для каждого уникального префикса суффиксов.

Python:

# Дерево представляется словарём
suffix_tree = {
    'root': {
        '$': {'leaf': '$'},
        'a': {
            'n': {
                'a': {'leaf': 'ana'}
            }
        },
        'n': {
            'a': {
                'n': {'leaf': 'nana'}
            }
        }
    }
}

Свойства

Построение за 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 (или ∞) в противном случае.

Python:

# Матрица 4x4 для графа
adjacency_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]
# adj_matrix[i][j] = 1 означает наличие ребра между вершинами i и j

C#:

// Целочисленная матрица смежности
int[,] matrix = new int[4, 4];
matrix[0, 1] = 1;
matrix[0, 3] = 1;
matrix[1, 0] = 1;
matrix[1, 2] = 1;

Свойства

Прямой доступ: проверка существования ребра — 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).

Python:

# Каждая вершина содержит список соседей
adjacency_list = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

Java:

// Map с набором вершин
Map<Integer, Set<Integer>> graph = new HashMap<>();
graph.put(0, Set.of(1, 3));
graph.put(1, Set.of(0, 2));

Свойства

Память: 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 и графовых базах данных.

Python:

# Граф — 0→1, 0→2, 1→2, 2→0 (веса = 1, опущены)
col_indices = [1, 2, 2, 0]   # конечная вершина каждого ребра
row_ptr = [0, 2, 3, 4]       # начало списка рёбер для вершины i

# Вершина 0 — col_indices[row_ptr[0]:row_ptr[1]] → [1, 2]
# Вершина 1 — col_indices[row_ptr[1]:row_ptr[2]] → [2]
# Вершина 2 — col_indices[row_ptr[2]:row_ptr[3]] → [0]

Структура

Три массива (для невзвешенного графа достаточно двух):

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

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

→ 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. Вероятностные и потоковые структуры данных

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

Напоминалка — шесть структур для Big Data и highload

Структура	Типичный вопрос	Память / идея
Bloom Filter	Встречался ли элемент раньше?	Битовый массив + несколько хешей; "нет" — точно, "да" — возможно
HyperLogLog	Сколько уникальных значений?	Регистры по "длине хвоста" хеша; ~1–2 КБ на миллионы уникальных
Cuckoo Filter	Элемент в множестве? Нужно удаление?	Отпечатки в двух корзинах; как Bloom, но с `delete`
MinHash	Насколько похожи два множества?	Короткая "подпись" множества; оценка Jaccard без полного пересечения
Skip List	Быстрый поиск/вставка в упорядоченном списке?	Несколько уровней "экспресс-рельс"; в среднем O(log n)
Count-Min Sketch	Какова частота ключа в потоке?	Несколько строк счётчиков + min по хешам; оценка не занижается

Подробнее по каждой — ниже. Прикладной контекст масштаба — в Big Data и потоковой аналитике; в Redis — модули Redis Stack, ZSET и skip list.

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

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

Python (идея: k хеш-функций, все k бита должны быть 1):

bit_array = [0] * 16

def h(s, seed):
    return (hash(s) ^ seed) % len(bit_array)

def add(item):
    for seed in (0, 1, 2):
        bit_array[h(item, seed)] = 1

def maybe_contains(item):
    return all(bit_array[h(item, seed)] for seed in (0, 1, 2))

add("example")
print(maybe_contains("example"))   # True (если не было ложного срабатывания)
print(maybe_contains("unknown"))  # может быть True ложно, False — только если точно нет

C#:

// Фильтр Блума на C#
BitArray bloomFilter = new BitArray(1000);
foreach (var key in keys) {
    int index = GetHash(key) % 1000;
    bloomFilter.Set(index, true);
}

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

Инициализируется битовый массив длиной 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?).

10.2 Count-Min Sketch

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

Python:

# Таблица счётов для оценки частоты
width = 100
depth = 4
table = [[0] * width for _ in range(depth)]

def count_item(item):
    counts = [table[d][hash(item) % width] for d in range(depth)]
    return min(counts)  # Возвращает минимальное значение среди всех строк

Java:

// Count-Min Sketch в Java
int[][] cmSketch = new int[5][256];
for (int d = 0; d < 5; d++) {
    cmSketch[d][hash(key) % 256]++;
}

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

Матрица из 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–2%, удерживая объём памяти фиксированным (типично около 12 КБ на структуру в Redis, в учебных оценках часто указывают ~1.5 КБ на "базовый" вариант) — независимо от того, сколько миллиардов значений прошло через поток.

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

Python (упрощённая иллюстрация регистров):

# m регистров: в каждый пишем max(длина ведущих нулей в хеше элемента)
registers = [0, 0, 0, 0, 1, 0, 2, 0, 1, 0]

# Оценка кардинальности — функция от registers (формула HyperLogLog++)
estimated_unique = estimate_hyperloglog(registers)

Когда выбирать: уникальные посетители, уникальные user_id в логе, cardinality в аналитике — когда точный COUNT(DISTINCT) по всему кластеру слишком дорог. Слияние: несколько HLL на разных узлах объединяют (PFMERGE в Redis) без повторного чтения сырых событий.

Применяется в Redis (PFADD, PFCOUNT, PFMERGE), Druid, Google BigQuery (приближённые агрегаты), рекламных и продуктовых метриках.

Cuckoo Filter

Альтернатива Bloom Filter с поддержкой удаления и лучшей локальностью данных за счёт хранения коротких отпечатков (fingerprints) в таблице с двумя возможными корзинами на элемент. Если обе корзины заняты, один отпечаток "вытесняют" (cuckoo hashing) в другую позицию — отсюда название.

Python:

# Таблица с двумя возможными позициями для каждого элемента
bucket_size = 4
cuckoo_table = [
    [None] * bucket_size for _ in range(size)
]

def add_item(item, fingerprint):
    pos1 = hash(item) % size
    pos2 = (hash(item) + hash(fingerprint)) % size
    
    if can_insert(pos1, fingerprint):
        insert_at(pos1, fingerprint)
    elif can_insert(pos2, fingerprint):
        insert_at(pos2, fingerprint)
    else:
        kick_and_redistribute(pos1, fingerprint)

Quotient Filter

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

10.4 MinHash (оценка похожести множеств)

MinHash сжимает большое множество (или бинарную матрицу "элемент × множество") в короткий вектор подписи из k целых чисел. Похожие множества с высокой вероятностью получают похожие подписи.

Идея: для каждой хеш-функции hᵢ сохраняют минимум hᵢ(x) по всем элементам x множества. Для двух множеств A и B доля совпадающих позиций в подписи — несмещённая оценка коэффициента Жаккара |A∩B|/|A∪B|.

Типичный сценарий — дедупликация почти одинаковых документов, поиск похожих пользователей по множеству тегов/покупок, LSH (Locality-Sensitive Hashing) для приближённого поиска соседей в больших коллекциях. В связке с потоковой аналитикой MinHash помогает сравнивать снимки аудиторий без полного join по факту.

Аспект	Деталь
Память	O(k) на множество при фиксированном `k` (часто 128–256)
Точность	Чем больше `k`, тем устойчивее оценка Jaccard
Ограничение	Оценка похожести, не точное пересечение; для малых множеств нужна осторожность

10.5 Skip List (пропускающий список)

Skip list — упорядоченная структура из нескольких уровней связных списков. Нижний уровень (h=0) содержит все ключи в порядке сортировки; на каждом следующем уровне остаётся подмножество "экспресс-узлов", через которые поиск перепрыгивает большие отрезки. Высота узла задаётся случайно (обычно геометрическое распределение), что даёт в среднем O(log n) на поиск, вставку и удаление.

h=2:  HEAD ------------------------> 8 -> NULL
h=1:  HEAD --------> 5 ------------> 8 -> NULL
h=0:  HEAD -> 2 -> 5 -> 8 -> NULL

Зачем в инженерии: проще сбалансированного дерева при конкурентном доступе (ConcurrentSkipListMap в Java), хорошо ложится на memtable в LSM-СУБД (RocksDB, LevelDB) и на sorted set в Redis (skiplist + хеш для O(1) по элементу — см. упорядоченные множества (ZSET)). Это точная структура (без ложных срабатываний), но её часто ставят рядом с вероятностными в той же главе, потому что решает ту же задачу "быстро по упорядоченным данным под нагрузкой".

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

Структура	Тип ошибки / ответ	Память	Используется в
Bloom Filter	Ложноположительная	Очень низкая	Cassandra, HBase, CDN, Squid
Count-Min Sketch	Завышенная оценка	Низкая	Akamai, Flink, Kafka Streams, мониторинг
HyperLogLog	~1–2% по кардинальности	Фиксированная	Redis, Druid, BigQuery approx.
Cuckoo Filter	Ложноположительная	Ниже Bloom	RedisBloom, маршрутизация, фильтры
MinHash	Оценка Jaccard	O(k) на set	LSH, дедуп, рекомендации, Spark MLlib
Skip List	Точный порядок	O(n)	Redis ZSET, RocksDB memtable, Java CHM

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

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 Системы управления базами данных (СУБД)

Пять классических индексных структур (B-tree, B⁺, хеш, bitmap, инвертированный) с примерами запросов — в основах БД. Расширенная восьмёрка (skip list, LSM, SSTable и др.) — в таблице "Как СУБД выполняет запрос". Ниже — реализация с акцентом на код и сложность.

Структура	Среда	Задача	Раздел / ссылка
Skip list	RAM	Упорядоченные ключи в памяти	§10.5
Хеш-индекс	RAM	Точный ключ за O(1)	§11.2.2
Битовый индекс	Диск / OLAP	Низкая кардинальность, AND/OR фильтров	§11.2.8
SSTable	Диск	Неизменяемый отсортированный сегмент	§11.2.3
LSM-дерево	RAM + диск	Высокая скорость записи	§11.2.4
B⁺-дерево	Диск	Индекс таблицы, диапазоны	§7
Инвертированный индекс	Поисковый индекс	Термин → документы	§11.2.5
Суффиксное дерево / массив	Строка / индекс	Подстроки, префиксы	§8
R-дерево	Пространство	Объекты в области, kNN	Геометрические структуры

11.2.1 B⁺-деревья (дисковые СУБД)

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

Подробнее о мотивации, B- и B⁺-вариантах — в §7.

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

Используются в in-memory СУБД (Redis, Memcached, VoltDB).
Реализация: ключ → hash(key) % N → корзина (bucket) в массиве; в корзине — указатель на строку или цепочка коллизий.
Доступ: в среднем O(1) при точном совпадении ключа (WHERE id = 123).
Ограничение: диапазоны (BETWEEN), сортировка по ключу и префиксный поиск без отдельной структуры.

Теория хеш-таблиц — в §4 этой статьи; цепочка "ключ → хеш → корзина → строка" — в пяти структурах индексов; применение в реляционных СУБД — хешированные индексы.

11.2.3 SSTable

SSTable (Sorted String Table) — неизменяемый файл на диске: пары ключ–значение отсортированы по ключу, в конце файла лежит индекс блоков (ключ → смещение и длина в "blob"-части). Поиск ключа — бинарный поиск по индексу, затем чтение одного блока данных.

Запись в уже существующий SSTable не выполняется; обновления и удаления накапливаются как новые версии ключей в более свежих файлах.
Отдельно SSTable почти не используют — он входит в LSM-стек уровней (Level 0, Level 1, …).
Слияние (merge) нескольких SSTable при compaction убирает устаревшие версии и tombstone’ы.

См. также глоссарий — SSTable и NoSQL — memtable / SSTable.

11.2.4 LSM-дерево

LSM (Log-Structured Merge-tree) — схема хранения "сначала быстро в RAM, потом упорядоченно на диск":

Записи попадают в WAL (журнал durability) и в memtable — упорядоченная структура в RAM (часто skip list или сбалансированное дерево).
При переполнении memtable сбрасывается (flush) в новый SSTable на диск.
Фоновая compaction сливает SSTable’ы на разных уровнях, сжимая дубликаты ключей.

Плюс	Минус
Высокая пропускная способность записи (последовательная запись на диск)	Read amplification — чтение может проверить memtable и несколько уровней SSTable
Хорошо ложится на SSD и распределённые узлы (Cassandra, RocksDB)	Пики нагрузки при compaction

Примеры — Cassandra, RocksDB, LevelDB, ScyllaDB. Обзор в экосистеме — Основы NoSQL.

11.2.5 Инвертированный индекс

Прямой индекс (forward): документ → {термины}. Инвертированный: термин → {документы} (и часто позиции в тексте). Запрос "найти все тексты со словом database" читает posting list для database; несколько слов — пересечение или объединение списков.

Строится при индексации (токенизация, стемминг, стоп-слова).
Используется в поисковых движках (Lucene, Elasticsearch) и в полнотекстовых расширениях СУБД.
Дополняет B⁺-дерево по первичному ключу: реляционная таблица отвечает на WHERE id = …, инвертированный индекс — на WHERE text @@ '…'.

Связь с алгоритмами поиска — инвертированные индексы; обзор для БД — пять структур.

11.2.8 Битовые индексы

Для столбца с малым числом значений (статус, пол, флаг) на каждое значение домена строят битовую карту по строкам таблицы: 1 — значение в строке есть, 0 — нет. Фильтры по нескольким таким столбцам сводятся к побитовым AND / OR / NOT.

Типичная среда — OLAP, витрины, редкие обновления индексируемых атрибутов.
В OLTP с частыми UPDATE пересчёт карт дорог; чаще достаточно B⁺-индекса.
В PostgreSQL оптимизатор может собрать Bitmap Index Scan из нескольких B-tree; в Oracle — отдельный Bitmap Index на столбце.

Подробнее — битовые индексы в основах БД.

11.2.6 Пространственные индексы (R-дерево)

Для координат, полигонов и многомерных атрибутов применяют R-деревья и родственные структуры: узлы дерева — ограничивающие прямоугольники (или гиперпрямоугольники), внутри которых лежат объекты. Запрос "все точки в этом bbox" или "ближайший сосед" обходят только пересекающиеся ветви.

Подробно — в Геометрических структурах данных (PostGIS, ГИС, kNN).

11.2.7 Векторные индексы (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, что позволяет оптимизировать доступ к полям.

Частые ошибки при выборе структуры данных

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

Мини-чеклист перед реализацией

Какие операции самые частые — get, put, range, delete, iterate.
Какой целевой объём данных и как он растёт.
Где хранение — RAM, диск, распределённый кластер.
Нужна ли потокобезопасность и какая модель конкуренции.
Есть ли требования к порядку, сортировке и диапазонам.
Допустимы ли аппроксимации и вероятностные ошибки.

Основные структуры данных и их реализация​

Алгоритмический справочник (псевдокод)​

Массив и динамический массив​

Связный список​

Стек (LIFO) и очередь (FIFO)​

Хеш-таблица (словарь)​

1. Массивы​

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

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

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

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

2. Списки​

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

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

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

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

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

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

3.3. Дек (двусторонняя очередь)​

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

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

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

4.2.1 Цепочки (chaining)​

4.2.2 Открытая адресация (open addressing)​

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

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

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

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

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

5.2.1 Вставка (insert)​

5.2.2 Извлечение максимума/минимума (extract)​

5.2.3 Построение кучи из массива (heapify)​

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

5.3.1 Выбор представления​

5.3.2 Кэш-эффективные варианты — d-арные кучи​

5.3.3 Потокобезопасность​

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

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

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

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

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

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

6.2.1 AVL-дерево​

6.2.2 Красно-чёрные деревья (Red-Black Tree)​

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

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

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

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

7.3 B⁺-деревья​

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

8. Суффиксные структуры​

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

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

Построение​

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

Свойства​

Недостатки​

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

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

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

Свойства​

Недостатки​

Применение​

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

Свойства​

Недостатки​

Применение​

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

Структура​

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

Недостатки​

Применение​

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

Пример​

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

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

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

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

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

Свойства​

Основные структуры данных и их реализация

Алгоритмический справочник (псевдокод)

Массив и динамический массив

Связный список

Стек (LIFO) и очередь (FIFO)

Хеш-таблица (словарь)

1. Массивы

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

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

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

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

2. Списки

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

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

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

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

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

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

3.3. Дек (двусторонняя очередь)

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

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

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

4.2.1 Цепочки (chaining)

4.2.2 Открытая адресация (open addressing)

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

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

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

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

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

5.2.1 Вставка (`insert`)

5.2.2 Извлечение максимума/минимума (`extract`)

5.2.3 Построение кучи из массива (`heapify`)

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

5.3.1 Выбор представления

5.3.2 Кэш-эффективные варианты — d-арные кучи

5.3.3 Потокобезопасность

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

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

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

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

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

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

6.2.1 AVL-дерево

6.2.2 Красно-чёрные деревья (Red-Black Tree)

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

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

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

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

7.3 B⁺-деревья

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

8. Суффиксные структуры

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

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

Построение

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

Свойства

Недостатки

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

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

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

Свойства

Недостатки

Применение

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

Свойства

Недостатки

Применение

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

Структура

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

Недостатки

Применение

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

Пример

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

Компромиссы

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

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

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

Свойства