Структуры данных для подготовки к собеседованиям по алгоритмам

Александр Чепайкин

Senior Developer в крупном финтехе. С 2012 года в IT, участвовал в разработке мобильных приложений, игр и сложных распределенных систем. Несколько лет работал удаленно в крупных стартапах Кремниевой долины. Построил эффективное обучение, пройдя которое, все мои студенты получают работу в IT.

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

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

Рекомендую также прочитать мою статью про алгоритмы и оценку сложности. Эти две статьи помогут вам подготовиться к алгоритмическим собеседованиям.

Я не преследую цель дать всю исчерпывающую информацию в одной статье - это лишь перечисление самых часто используемых структур данных с поверхностным пояснением.

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

Если вы нанимаете, и готовы рассмотреть хорошего Junior+/Middle Python Backend, напишите мне в Telegram. Я учу людей программировать, а не просто проходить собеседования. Даже если прямо сейчас у вас нет вакансии, в будущем у вас появится потребность в хорошем Junior+, который готов к самостоятельной работе и может быстро расти до уровня Middle. Посмотрите как я обучаю, если у вас есть сомнения.

Используйте содержание и кнопку НАВЕРХ для удобства навигации по статье.

Содержание

1. Массивы

   1. Статический массив

   2. Динамический массив

   3. Двумерные массивы (матрицы)

2. Связные списки

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

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

   3. Циклические списки

3. Стек (Stack)

4. Очереди (Queues)

   1. FIFO (First In, First Out)

   2. LIFO (Last In, First Out)

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

   4. Очередь с приоритетом (Priority Queue)

5. Бинарная куча (Binary heap)

   1. Как работает бинарная куча (Binary heap)

   2. Минимальная куча (Min-Heap)

   3. Максимальная куча (Max-Heap)

6. Хеш-таблица (Hash table)

   1. Основные характеристики

   2. Как работает хеш-функция

   3. Что такое бакет (bucket)

   4. Как выбирается бакет

   5. Как работает resize в Хеш-таблице

   6. Худший случай в хеш-таблице

   7. Оптимизация работы Хеш-таблицы

7. Деревья (Trees)

   1. Бинарное дерево (Binary tree)

      1. Общие сведения

      2. Виды бинарных деревьев

      3. Бинарные деревья поиска (BST)

   2. AVL деревья

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

   4. Б-дерево (Btree)

   5. Б+-дерево (B+tree)

   6. Префиксные деревья (Tries)

8. Графы

   1. Деревья (Tree)

   2. Ориентированные графы (Direct Graph)

   3. Неориентированные графы (Undirected Graph)

   4. Взвешенные графы (Weighted Graph)

   5. Двудольные графы (Bipartite Graph)

   6. Сильно связные графы (Strongly Connected Graph)

   7. Графы с циклами (Cyclic Graph)

   8. Графы без циклов (Acyclic Graph)

9. Заключение

Массивы

Статический массив

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

В Python нет традиционных статических массивов (как в C или Java), но в Python есть массивы с фиксированным типом элементов это модуль array. Они работают более эффективно, чем списки, но поддерживают только один тип данных.

array.array в Python под капотом использует динамический массив.

Хотя он работает похоже на статический массив, он не является статическим, потому что:

1. Он может изменяться в размере с помощью .append(), .extend(), .pop(), и т. д.

2. При нехватке памяти он перевыделяется (realloc()) аналогично list.

3. Под капотом у array.array используется C-массив, но с динамическим управлением памятью.

Так же в python есть tuple, который похож на статический массив, но позволяет хранить элементы разного типа. Под капотом в CPython для его релизации используется статический массив, но хранит в себе не сами объекты, а ссылки на них.

Смотрите реализацию tuple в CPython тут и тут, чтобы лучше понять как он устроен. Обратите внимание на _PyTuple_Resize в некоторых ситуациях tuple все таки может изменяться, но это происхдит в особых случаях, и он на самом деле не изменяется, а пересоздается заново.

НАВЕРХ

Динамический массив

Динамическим называется массив, размер которого может изменяться во время выполнения програмы.

В python это любые последовательности кроме tuple, например list является динамическим массивом, потому что его размер можно изменить с помощью методов .append(), .extend(), .pop(), и т. д.

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

Давайте разберёмся на пальцах, как это работает под капотом большинства языков программирования (методы ниже из языка Си):

1. Выделем память с помощью calloc или malloc заданного размера

2. Добавляем в массив элементы

3. Когда выделенная память израсходована, вызывается метод realloc и выделяется дополнительная память, увеличив исходную в два(обычно) раза, чтобы массив вмещал не 4, а например 8 элементов.

4. Если realloc не может расширить непрерывный блок памяти, выделяется новый смежный участок увеличенного размера, и данные копируются туда.

5. Продолжаем добавлять элементы, если память снова закончилась повторяем шаг 3 и 4.

6. Когда массив нам больше не нужен, освобождаем память с помощью метода free

Выше всего лишь поверхотсное описание базового сценария добавления нового элемента в динамический массив.

НАВЕРХ

Двумерные массивы (матрицы)

Двумерный массив — это таблица данных, где:

• Строки идут горизонтально (слева направо).

• Столбцы идут вертикально (сверху вниз).

• Каждый элемент имеет два индекса: [номер строки][номер столбца].

Пример двумерного массива:

1  2  3
4  5  6
7  8  9

1 2 3 4 5 6 7 8 9 (не путайте с нумерацией строк 1, 2, 3 по вертикали)

1 — элемент с индексами [0][0]
5 — элемент с индексами [1][1]

Реализация двумерных массивов в Python

Python не имеет встроенного типа "двумерный массив", но можно создать его разными способами.

Двумерный массив с list (список списков)

matrix = [
    [1, 2, 3],  
    [4, 5, 6],  
    [7, 8, 9]
]

# Доступ к элементу (например, 5)
print(matrix[1][1])  # 5

Плюсы: Простая реализация
Минусы: Медленный доступ к элементам в больших массивах

Двумерный массив с numpy (быстрые вычисления)

import numpy as np

matrix = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])

# Доступ к элементу
print(matrix[1, 1])  # 5

Плюсы: Быстрее, чем list, удобные операции с числами
Минусы: Нужно устанавливать numpy

Двумерный массив с array.array (эффективно по памяти)

import array

matrix = [
    array.array('i', [1, 2, 3]),
    array.array('i', [4, 5, 6]),
    array.array('i', [7, 8, 9])
]

print(matrix[1][1])  # 5

Плюсы: Экономит память
Минусы: Только для чисел одного типа

Где используются двумерные массивы в реальных проектах?

Изображение — это двумерный массив пикселей. Например, чёрно-белая картинка — это матрица чисел (0 — чёрный, 255 — белый).

import cv2  # OpenCV

image = cv2.imread('image.jpg', cv2.IMREAD_GRAYSCALE)  # Загружаем картинку как 2D-массив
print(image.shape)  # (высота, ширина)

Матрицы используются в нейросетях, обработке текстов, анализе данных.

import numpy as np

weights = np.random.rand(3, 3)  # Матрица весов для нейросети
print(weights)

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

game_map = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]  # 0 — пустая клетка, 1 — стена

Когда мы загружаем таблицу из базы данных, она фактически является двумерным массивом.

import sqlite3

conn = sqlite3.connect('database.db')
cursor = conn.cursor()

cursor.execute("SELECT * FROM users")
data = cursor.fetchall()  # Получаем данные в виде списка кортежей (2D-матрица)

НАВЕРХ

Связные списки

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

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

Давайте рассмотрим пример на Python. Я использовал tuple, но можно использовать любую последовательность.

third = ('third', None)
second = ('second', third)
first = ('first', second)

В примере выше tuple содержит первым элементом значение, а вторым сслыку на объект, в котором хранится следующее значение. Последовательность заканчивается на third, так как второй элемент None и ни на что не ссылается.

НАВЕРХ

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

Двусвязный или двунаправленный список - это структура данных, состоящая из элементов, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на предыдущий и следующий элемент.

Давайте рассмотрим пример на Python.

third = (second, 'third', None)
second = (first, 'second', third)
first = (None, 'first', second)

В примере выше tuple содержит вторым элементом значение, а первым и третьим ссылки на предыдущий и следующий объект.

У first первый элемент None, потому что нет предыдущего объекта, а у third третий элемент None, потому что нет следующего объекта и на нем последовательность заканчивается.

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

Внешне deque выглядит как обычный двусвязный список и получение элемента по индексу происходит хотя и за линейное время O(n), но без полного прохода по всем элементам, потому что под капотом используются структура данных - связанный список блоков.

Как это реализованно:

[BLOCK_1] → [BLOCK_2] → [BLOCK_3] ...

• Каждый блок — это массив указателей (например, на 64 элемента).

• При переполнении создаётся новый блок, связанный с предыдущим.

• Внутри каждого блока элементы хранятся как кольцевой буфер (индексы left и right двигаются циклически).

• Когда один блок (64 элемента) заполняется, создаётся новый блок и связывается с предыдущим.

• Если один блок полностью пустеет, он может быть удалён.

• Доступ к элементу по индекс в deque не приводит к проходу по всем элементам, а идет по блокам, проверяя только вхождение индекса в блок (диапазон индексов в блоке например 64-127).

Допустим у нас deque с 256 элементами и блоками по 64 элемента:

Блок 0 → [0, 1, 2, ..., 63]   (индексы 0-63)
Блок 1 → [64, 65, ..., 127]   (индексы 64-127)
Блок 2 → [128, ..., 191]      (индексы 128-191)
Блок 3 → [192, ..., 255]      (индексы 192-255)

Чтобы найти deque[150]:

1. Проверяем Блок 0 (0-63) - не здесь.

2. Проверяем Блок 1 (64-127) - не здесь.

3. Проверяем Блок 2 (128-191) - индекс 150 внутри!

4. Берём deque[150] прямым доступом как в массиве за O(1). В итоге доступ по индексу O(k), но k - это число блоков, а не общее число элементов.

Не нужно проходить все 256 элементов!

НАВЕРХ

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

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

Обычный список:

A → B → C → D → None  (конец списка)

Циклический список:

A → B → C → D → A  (последний элемент ссылается на первый)

Такой список никогда не заканчивается, и если пройти по нему обычным способом, можно попасть в бесконечный цикл!

Давайте рассмотрим пример на Python.

third = ['third', None]
second = ['second', third]
first = ['first', second]

third[1] = first

В примере выше tuple содержит первым элементом значение, а вторым сслыку на объект, в котором хранится следующее значение. Цикл начинается на third, так как второй элемент ссылается на первый first.

Циклический список через collections.deque

Используется, если нужно легко делать "зацикленное" движение по списку.

from collections import deque

# Создаём двустороннюю очередь
cyclic_list = deque([1, 2, 3, 4])

# Циклический сдвиг (вращение)
cyclic_list.rotate(-1)  # Перемещает первый элемент в конец
print(cyclic_list)  # deque([2, 3, 4, 1])

cyclic_list.rotate(2)  # Сдвигаем два элемента назад
print(cyclic_list)  # deque([4, 1, 2, 3])

Где используется?

• В круговых очередях (например, обработка задач)

• В музыкальных плеерах (циклический плейлист)

• В игровых логиках (например, ходы по кругу)

Циклический список через itertools.cycle

Если нам нужно бесконечно проходить список по кругу:

import itertools

cyclic_list = [1, 2, 3, 4]

# Создаём бесконечный итератор
cycle_iter = itertools.cycle(cyclic_list)

for _ in range(10):  # Проходим 10 шагов (но можно бесконечно)
    print(next(cycle_iter), end=" ")  # 1 2 3 4 1 2 3 4 1 2

Где используется?

• В анимациях (повторяющиеся циклы кадров)

• В бесконечном переборе данных (например, изображения на веб-сайте)

• В ботах и автоматизации (например, перебор действий)

Реализация циклического связного списка вручную

Если нужен настоящий связанный список с циклом:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Следующий элемент

class CircularLinkedList:
    def __init__(self):
        self.head = None  # Голова списка

    def append(self, data):
        new_node = Node(data)
        if not self.head:  # Если список пуст
            self.head = new_node
            self.head.next = self.head  # Указываем на себя (создаём цикл)
        else:
            temp = self.head
            while temp.next != self.head:  # Находим последний элемент
                temp = temp.next
            temp.next = new_node  # Добавляем новый узел
            new_node.next = self.head  # Замыкаем в кольцо

    def display(self, steps=10):
        """Выводим список, но не бесконечно"""
        temp = self.head
        for _ in range(steps):
            print(temp.data, end=" → ")
            temp = temp.next
        print("... (цикл)")

# Используем
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.append(4)

cll.display()  # 1 → 2 → 3 → 4 → 1 → 2 → 3 → 4 → 1 → 2 → ... (цикл)

Где используется?

• В операционных системах (планировщики задач)

• В графах (если граф цикличен)

• В сетевых алгоритмах (маршрутизация пакетов)

НАВЕРХ

Стек (Stack)

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out), что означает: Последний добавленный элемент извлекается первым.

Пример на Python

stack = []  
stack.append(1)  # push(1)
stack.append(2)  # push(2)
stack.append(3)  # push(3)
print(stack)  # [1, 2, 3]

top = stack.pop()  # pop() -> 3
print(top)   # 3
print(stack)  # [1, 2]

Где используется стек?

• Обратный порядок выполнения (например, стек вызова функций в Python, JavaScript и т.д.).

• Алгоритмы обхода (DFS, обратная польская нотация).

• Отмена действий (Ctrl+Z).

• Парсинг выражений (проверка скобок, HTML).

НАВЕРХ

Очереди (Queues)

FIFO (First In, First Out)

FIFO (First In, First Out) — это очередь, где первый добавленный элемент извлекается первым.

Пример из жизни: Очередь в магазине

• Первый человек, который встал в очередь, обслуживается первым.

• Последний пришедший ждёт своей очереди.

Это и есть FIFO: первый зашёл — первый вышел.

Пример реализации в Python

from collections import deque

queue = deque()
queue.append(1)  # enqueue(1)
queue.append(2)  # enqueue(2)
queue.append(3)  # enqueue(3)

print(queue.popleft())  # dequeue() -> 1
print(queue)  # deque([2, 3])

Важно, что для реализации FIFO, хорошо подходит связанный список deque, потому что с ним мы можем брать первый элемент из очереди за константное время O(1) методом popleft. В случае с list эта операция займет O(n).

НАВЕРХ

LIFO (Last In, First Out)

LIFO (Last In, First Out) переводится как «последним пришёл – первым вышел».

Это принцип работы стека (stack), где последний добавленный элемент удаляется первым.
Представьте стопку тарелок:

• Если положить тарелку №1, затем №2, затем №3,

• То первыми достанем в обратном порядке: №3 → №2 → №1.

Графическое представление стека (LIFO):

Добавляем:  1 → 2 → 3  (3 сверху)
Извлекаем:  3 → 2 → 1  (3 первым выходит)

Реализация LIFO в Python

Используем list (встроенный стек)

stack = []  # Создаём пустой стек

stack.append("A")  # Добавляем "A"
stack.append("B")  # Добавляем "B"
stack.append("C")  # Добавляем "C"

print(stack)  # ['A', 'B', 'C']

# Удаляем (всегда с конца)
print(stack.pop())  # C
print(stack.pop())  # B
print(stack.pop())  # A

append() – добавляет в конец (верх стека)
pop() – удаляет последний добавленный элемент

Используем queue.LifoQueue (потокобезопасный стек)

from queue import LifoQueue

stack = LifoQueue()

stack.put("A")
stack.put("B")
stack.put("C")

print(stack.get())  # C
print(stack.get())  # B
print(stack.get())  # A

Подходит для многопоточных программ (безопасен в многозадачных системах).

НАВЕРХ

Двусторонняя очередь (Deque)

Дек — это двусторонняя очередь (так же называют deque, double-ended queue), которая поддерживает добавление и удаление элементов с обоих концов за O(1).

Пример из жизни: Очередь в метро

• Люди могут заходить спереди и сзади.

• Могут выходить как с начала, так и с конца.

Это и есть дек — гибкая очередь с доступом к обоим концам.

Пример на Python

from collections import deque

d = deque()  
d.append(1)       # [1]
d.append(2)       # [1, 2]
d.appendleft(0)   # [0, 1, 2]

print(d.pop())    # 2 (удаляем с конца)
print(d.popleft()) # 0 (удаляем с начала)
print(d)          # deque([1])

НАВЕРХ

Очередь с приоритетом (Priority Queue)

Очередь с приоритетом - это очередь, где элементы извлекаются не в порядке добавления (FIFO), а по приоритету.

Пример из жизни: Больница

• Пациенты поступают в разном порядке.

• Сначала обслуживаются те, у кого высокий приоритет (например, срочные случаи).

• Обычные пациенты ждут своей очереди.

Пример реализации с использованием queue.PriorityQueue (потокобезопасная реализация)

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((1, "Low priority"))
pq.put((3, "High priority"))
pq.put((2, "Medium priority"))

print(pq.get())  # (1, 'Low priority')
print(pq.get())  # (2, 'Medium priority')
print(pq.get())  # (3, 'High priority')

Так же можно использовать пакет heapq для реализации очереди с приоритетом.

НАВЕРХ

Бинарная куча (Binary heap)

Как работает бинарная куча (Binary heap)

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

Куча - это деревовидная структура данных, которая может быть минимальной или максимальной.

Основные операции (вставка, удаление) выполняются за O(log n). Куча автоматически перестраивается после вставки и удаления.

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

Представление кучи в виде дерева

        1
       / \
      2   3
     / \
    4   5

Свойство кучи:

• 1 (корень) < 2, 3

• 2 < 4, 5

• 3 не имеет потомков

Соответствующий массив (list)

heap = [1, 2, 3, 4, 5]

Элементы идут сверху вниз, слева направо.

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

• Родитель узла: parent(i) = (i - 1) // 2

• Левый потомок: left(i) = 2 * i + 1

• Правый потомок: right(i) = 2 * i + 2

Как изменяется куча при вставке и удалении?

Вставка нового элемента (например, 0)

До вставки:

        1
       / \
      2   3
     / \
    4   5

Массив: [1, 2, 3, 4, 5]

Добавляем 0 в конец массива:

        1
       / \
      2   3
     / \
    4   5
   /
  0

Массив: [1, 2, 3, 4, 5, 0]

Но 0 < 4, значит, поднимаем его вверх (просеивание вверх).

После перестановок:

        0
       / \
      1   3
     / \
    2   5
   /
  4

Массив: [0, 1, 3, 2, 5, 4]

Удаление минимального элемента (1)

До удаления:

        1
       / \
      2   3
     / \
    4   5

Массив: [1, 2, 3, 4, 5]

Удаляем 1, перемещаем последний элемент (5) в корень:

        5
       / \
      2   3
     / 
    4

Массив: [5, 2, 3, 4]

Так как 5 > 2, меняем местами 5 и 2:

        2
       / \
      5   3
     / 
    4

Массив: [2, 5, 3, 4]

Теперь 5 > 4, меняем местами 5 и 4:

        2
       / \
      4   3
     / 
    5

Массив: [2, 4, 3, 5]

Свойство минимальной кучи восстановлено!

НАВЕРХ

Минимальная куча (Min-Heap)

Минимальная куча (Min-Heap): Родительский элемент всегда меньше своих дочерних элементов. Таким образом, минимальный элемент всегда находится в корне дерева.

Пример минимальной кучи:

          1
         / \
        2   3
       / \
      4   5

1 - минимальный элемент, так как все элементы в дереве больше или равны ему.

Минимальная куча (Min-Heap) — извлекаются элементы с минимальным приоритетом.

• Используется в основном для реализации очереди с приоритетом, где меньшие числа имеют более высокий приоритет.

• Реализуется с помощью heapq (по умолчанию).

Пример реализации Min-Heap в Python:

import heapq

# Инициализация пустой очереди с приоритетом
pq = []

# Добавление элементов (приоритет, значение)
heapq.heappush(pq, (1, "Low priority"))
heapq.heappush(pq, (3, "High priority"))
heapq.heappush(pq, (2, "Medium priority"))

# Извлечение элемента с наивысшим приоритетом
print(heapq.heappop(pq))  # (1, 'Low priority')
print(heapq.heappop(pq))  # (2, 'Medium priority')
print(heapq.heappop(pq))  # (3, 'High priority')

В heapq приоритет задается первым значением в кортеже (кортеж вида (приоритет, значение)). Функция heappush добавляет элемент в кучу, а heappop извлекает элемент с минимальным приоритетом.

НАВЕРХ

Максимальная куча (Max-Heap)

Максимальная куча (Max-Heap): Родительский элемент всегда больше своих дочерних элементов. Максимальный элемент находится в корне дерева.

Пример максимальной кучи:

          5
         / \
        4   3
       / \
      2   1

5 — максимальный элемент, так как все элементы в дереве меньше или равны ему.

Максимальная куча (Max-Heap) - извлекаются элементы с максимальным приоритетом.

Пример реализации с помощью отрицания приоритетов в heapq:

import heapq

heap = []
heapq.heappush(heap, -3)  # Добавляем отрицательные числа
heapq.heappush(heap, -1)
heapq.heappush(heap, -5)

print(-heapq.heappop(heap))  # 5 (максимальный элемент)

НАВЕРХ

Хеш-таблица (Hash table)

Основные характеристики

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

Основные характеристики:

• Хеш-функция - применяется к ключу и возвращает целочисленное хеш-значение (обычно большое число).

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

  • Метод цепочек (Chaining) – каждый элемент массива хранит список (или другой контейнер) с элементами, имеющими одинаковый хеш.

  • Открытая адресация (Open Addressing) – при коллизии ищется следующая свободная ячейка (например, линейное пробирование).

Сложность операций

В Python хеш-таблицы реализованы в виде словарей (dict) и множеств (set).

Пример с dict:

# Создание хеш-таблицы (словаря)
hash_table = {
    "apple": 10,
    "banana": 20,
    "orange": 30
}

# Доступ к значению
print(hash_table["banana"])  # 20

# Добавление нового элемента
hash_table["grape"] = 40

# Удаление элемента
del hash_table["apple"]

# Проверка существования ключа
if "orange" in hash_table:
    print("Есть в таблице")

НАВЕРХ

Как работает хеш-функция

Когда мы добавляем ключ в словарь (dict), Python выполняет следующие шаги:

1. Вычисляет хеш-значение ключа с помощью встроенной функции hash().

2. Преобразует хеш в индекс бакета в хеш-таблице.

3. Если бакет занят (возникла коллизия), Python ищет другой бакет (используется открытая адресация).

Пример:

key = "hello"
hash_value = hash(key)  # Получаем хеш-значение
N = 8  # Размер хеш-таблицы (для простоты)
index = hash_value % N  # Вычисляем индекс бакета
print(f"Хеш: {hash_value}, Бакет: {index}")

НАВЕРХ

Что такое бакет (bucket)

• В Python хеш-таблица — это массив фиксированного размера, состоящий из бакетов.

• Бакет содержит ключ, значение и хеш ключа.

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

Размер массива всегда степень двойки (8, 16, 32, 64 и т.д.). Это ускоряет вычисление индекса с помощью & (N - 1), что быстрее, чем mod.

НАВЕРХ

Как выбирается бакет

Этап 1: Преобразование хеша в индекс

Python берет результат hash(key), а затем использует битовую операцию для вычисления индекса:

index = hash(key) & (N - 1)  # Быстрое вычисление индекса

Это эквивалентно hash(key) % N, но выполняется быстрее, так как N - степень двойки.

Этап 2: Проверка бакета

• Если бакет пуст, туда записывается (key, value, hash).

• Если бакет занят (коллизия). Python использует линейное пробирование и ищет следующую свободную ячейку.

Этап 3: Разрешение коллизий

Если два ключа попадают в один бакет (редкость, но возможно), Python:

1. Проверяет, совпадают ли ключи (не только хеши).

2. Если да — заменяет значение.

3. Если нет — использует линейное пробирование и проверяет следующий бакет.

НАВЕРХ

Как работает resize в Хеш-таблице

Когда происходит resize

Resize запускается, если используется более 2/3 бакетов.

• Начальный размер словаря = 8 бакетов

• При заполнении 6 бакетов (8 * 2/3 ≈ 5.3), словарь увеличивается до 16.

• При заполнении 10 бакетов (16 * 2/3 ≈ 10.6), увеличивается до 32.

• Этот процесс продолжается каждый раз при достижении 2/3 заполнения.

Как происходит resize

Когда Python увеличивает размер хеш-таблицы:

1. Создается новый массив в 2 раза больше старого.

2. Перехеширование всех элементов – каждый ключ получает новый индекс в новой таблице.

3. Запись элементов в новый массив по их новым индексам.

Почему нужно перехеширование (rehashing)

Когда увеличивается размер таблицы:

• Изменяется количество бакетов (N).

• Индекс каждого ключа вычисляется заново (hash(key) % new_size).

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

НАВЕРХ

Влияние resize и rehashing на производительность

resize – дорогая операция (O(n)). При увеличении размера все элементы копируются и перехешируются. Вставка в dict обычно O(1), но при resize становится O(n). Поэтому Python увеличивает размер в 2 раза, чтобы уменьшить частоту resize.

Худший случай в хеш-таблице

Python применяет открытую адресацию с линейным пробированием (linear probing). При коллизиях (hash(key1) % N == hash(key2) % N) новый ключ записывается в следующий свободный бакет.

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

Сравним скорость поиска в обычном словаре и словаре с плохими ключами:

import time

class BadHash:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 42  # Все объекты имеют одинаковый хеш

    def __eq__(self, other):
        return self.value == other.value  # Обычное сравнение

# Измеряем время для обычного словаря
start = time.time()
normal_dict = {i: f"Value {i}" for i in range(10000)}
print("Время создания обычного словаря:", time.time() - start)

# Измеряем время для словаря с плохими хешами
start = time.time()
bad_dict = {}
for i in range(10000):
    bad_dict[BadHash(i)] = f"Value {i}"
print("Время создания словаря с плохими хешами:", time.time() - start)

# Поиск элемента в словаре с обычными хешами
start = time.time()
for i in range(10000):
    _ = normal_dict[5000]  # Ожидаемая O(1)
print("Время поиска в словаре обычными хешами:", time.time() - start)

# Поиск элемента в словаре с плохими хешами
start = time.time()
for i in range(10000):
    _ = bad_dict[BadHash(5000)]  # Ожидаемая O(n)
print("Время поиска в словаре с плохими хешами:", time.time() - start)

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

Что происходит в этом примере?

• Мы создаем плохую хеш-функцию, которая всегда возвращает один и тот же хеш (42), что приводит к коллизиям для всех элементов.

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

• Так как мы используем линейное пробирование, при добавлении каждого нового элемента Python будет искать свободные ячейки по очереди, пока не найдет подходящую.

• В поиске Python будет использовать линейное пробирование для поиска нужной ячейки.

Результаты:

Время создания обычного словаря: 0.008013248443603516
Время создания словаря с плохими хешами: 4.327789306640625
Время поиска в словаре обычными хешами: 0.0017261505126953125
Время поиска в словаре с плохими хешами: 3.948306083679199

• В случае с плохим хешом, словарь будет работать неэффективно: при каждом поиске или вставке Python будет затрачивать больше времени на проверку ячеек.

• В худшем случае, если большая часть словаря занята, поиск и вставка могут быть выполнены за время O(n) вместо O(1).

НАВЕРХ

Оптимизация работы Хеш-таблицы

Способ 1: dict.fromkeys() (создает сразу N ключей)

Можно избежать resize задав нужный размер заранее, если это возможно.

d = dict.fromkeys(range(1000000), 0)  # Создаст сразу 1 млн ключей

Способ 2: defaultdict (лучше для больших словарей)

from collections import defaultdict
d = defaultdict(int)  # Значения по умолчанию будут 0
print(d[42])  # Вернет 0, даже если ключа 42 нет

defaultdict все равно использует те же правила resize, что и обычный dict, просто избегает лишних проверок наличия ключа, но количество элементов в нем растет так же, и еще он упрощает код, делая его более читаемым.

НАВЕРХ

Деревья (Trees)

Бинарное дерево (Binary tree)

Общие сведения

Бинарное дерево - это структура данных, где каждый узел (node) может иметь не более двух потомков (детей). Эти потомки называются левым и правым узлом.

Часто Binary tree путают с Btree, который используется в базах данных. Запомните, в базах данных используется Б+-деревья.

Основные термины:

• Корень (Root) — первый узел дерева. У него нет родителя.

• Лист (Leaf) — узел, у которого нет потомков.

• Родитель (Parent) — узел, имеющий потомков.

• Потомки (Children) — узлы, являющиеся дочерними по отношению к другому узлу.

• Глубина узла (Depth) — расстояние от корня до узла.

• Высота узла (Height) — расстояние от узла до самого дальнего листа.

• Поддерево (Subtree) — любое дерево, корнем которого является один из узлов исходного дерева.

• Размер дерева (Size) — общее количество узлов в дереве.

НАВЕРХ

Виды бинарных деревьев

• Полное (Full Binary Tree) — дерево, в котором у каждого узла либо два потомка, либо ни одного.

• Совершенное (Perfect Binary Tree) — бинарное дерево, у которого все внутренние узлы имеют ровно два потомка, а все листья находятся на одном уровне.

• Сбалансированное (Balanced Binary Tree) — бинарное дерево, в котором разница высот левого и правого поддерева любого узла не превышает 1.

• Двоичное или Бинарное дерево поиска (Binary Search Tree, BST) - рассмотрим подробно ниже.

НАВЕРХ

Бинарные деревья поиска (BST)

Бинарное дерево поиска (BST) — это бинарное дерево, в котором для каждого узла выполняется следующее свойство:

1. Все ключи в левом поддереве меньше, чем ключ текущего узла.

2. Все ключи в правом поддереве больше, чем ключ текущего узла.

3. Каждое поддерево также является бинарным деревом поиска.

Это свойство позволяет эффективно выполнять поиск, вставку и удаление элементов за O(log n) в среднем.

Структура BST

Допустим, у нас есть последовательность вставляемых элементов:
[10, 5, 15, 2, 7, 12, 20]

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

       10
      /  \
     5    15
    / \   /  \
   2   7 12  20

Код для построения этого дерева:

class Node:
    def __init__(self, value):
        self.value = value  # Значение узла
        self.left = None  # Ссылка на левое поддерево
        self.right = None  # Ссылка на правое поддерево


root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)

Проблемы BST

1. Несбалансированность

   • Если вставлять элементы в возрастающем порядке, дерево превращается в список (линейное дерево), и сложность поиска становится O(n).

   • Решение: самобалансирующиеся деревья

2. Дублирующиеся значения

   • Чаще всего BST не допускает дубликаты.

   • Можно разрешить их, например, используя счетчик частоты.

Поиск элемента в BST

Алгоритм:

1. Если дерево пустое, возвращаем None.

2. Если key == node.value, нашли элемент.

3. Если key < node.value, идем в левое поддерево.

4. Если key > node.value, идем в правое поддерево.

Пример поиска в BST. Код построения дерева описан выше.

def search(node, key):
    if not node or node.value == key:
        return node  # Найден или отсутствует в дереве
    if key < node.value:
        return search(node.left, key)
    return search(node.right, key)

found = search(root, 7)
print(found.value if found else "Не найдено")  # Вывод: 7

Сложность:

• В сбалансированном дереве: O(log n)

• В несбалансированном (спискообразном): O(n)

НАВЕРХ

AVL деревья

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

Основные свойства AVL дерева:

1. Бинарное дерево поиска (BST): Все элементы слева от узла меньше его значения, а все элементы справа — больше.

2. Балансировка: Для каждого узла разница в высоте между левым и правым поддеревом не может быть больше 1. Это называется фактором баланса.

3. Фактор баланса: Для каждого узла дерево должно быть сбалансировано:

   • Если разница высот поддеревьев для узла больше 1, выполняются повороты (правый или левый).

4. Повороты:

   • Левый поворот (если правое поддерево слишком высокое).

   • Правый поворот (если левое поддерево слишком высокое).

   • Иногда выполняются двойные повороты (сначала правый, потом левый, или наоборот).

Пример AVL дерева:

               [30]
             /    \
          [20]    [40]
         /   \    /    \
      [10]   [25] [35]  [50]
                      /
                    [32]

Объяснение структуры:

1. Корень дерева — 30.

2. В левом поддереве:

   • 20 — левая вершина с поддеревом 10 и 25.

3. В правом поддереве:

   • 40 — правая вершина с поддеревом 35 и 50.

   • 35 имеет левое поддерево 32.

Балансировка дерева:

• Узел 30: высота левого поддерева (20) = 2, высота правого поддерева (40) = 2 → фактор баланса = 0, всё сбалансировано.

• Узел 20: высота левого поддерева (10) = 1, высота правого поддерева (25) = 1 → фактор баланса = 0.

• Узел 40: высота левого поддерева (35) = 2, высота правого поддерева (50) = 1 → фактор баланса = 1.

• Узел 35: высота левого поддерева (32) = 1, правого поддерева нет → фактор баланса = 1.

Повороты в AVL деревьях:

• Если бы, например, добавление нового элемента привело бы к тому, что разница в высотах для узла 30 или 40 стала бы больше 1, то потребовались бы повороты для балансировки дерева.

Минусы AVL деревьев:

1. Сложность реализации:

   • Реализация AVL дерева требует дополнительного кода для поддержания балансировки (повороты и вычисление факторов баланса). Это делает такие деревья более сложными для реализации, чем обычные бинарные деревья поиска.

2. Более высокая стоимость вставки и удаления:

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

3. Дополнительные вычисления:

   • Для каждого узла нужно хранить дополнительную информацию — фактор баланса. Хотя это не является большим по объему, это увеличивает потребление памяти.

4. Частые повороты:

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

5. Меньшая эффективность при работе с большими объемами данных:

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

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

НАВЕРХ

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

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

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

Свойства красно-черного дерева:

1. Каждый узел окрашен либо в красный, либо в черный цвет.

2. Корень дерева всегда черный.

3. Каждый путь от корня до листа содержит одинаковое количество черных узлов.

4. У красного узла не может быть красного родителя (двойная краснота запрещена).

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

Если при добавлении или удалении узла нарушаются правила, выполняются повороты и перекрашивания, чтобы восстановить баланс.

Пример красно-черного дерева:

       [40B]
      /      \
   [20R]     [60B]
   /    \    /    \
[10B]  [30B] [50R] [70R]