2026-rff_mp/docs/report.md

Отчет по лабораторной работе: Сравнение структур данных для телефонного справочника

1. Цель работы

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

2. Реализованные структуры данных

2.1 Связный список (LinkedList)

• Узел: словарь с ключами name, phone, next
• Вставка: O(n) - проход до конца списка
• Поиск: O(n) - последовательный перебор
• Удаление: O(n) - поиск элемента и перестановка ссылок

2.2 Хеш-таблица (HashTable)

• Размер: 100 бакетов
• Хеш-функция: сумма кодов символов по модулю размера таблицы
• Коллизии: разрешаются методом цепочек (связные списки)
• Вставка: O(1) в среднем
• Поиск: O(1) в среднем
• Удаление: O(1) в среднем

2.3 Двоичное дерево поиска (BST)

• Узел: словарь с ключами name, phone, left, right
• Вставка: O(log n) в среднем, O(n) в худшем случае
• Поиск: O(log n) в среднем, O(n) в худшем случае
• Удаление: O(log n) в среднем, O(n) в худшем случае

3. Результаты экспериментов

3.1 Связный список (LinkedList)

Операция	Время (сек)
Вставка 300 записей	0.0032
Поиск 50 записей	0.0018
Удаление 25 записей	0.0007

3.2 Хеш-таблица (HashTable)

Операция	Время (сек)
Вставка 300 записей	0.0071
Поиск 50 записей	0.0004
Удаление 25 записей	0.0002

3.3 Двоичное дерево поиска (BST)

Режим	Операция	Время (сек)
Случайный порядок	Вставка 300 записей	0.0028
Случайный порядок	Поиск 30 записей	0.0003
Отсортированный порядок	Вставка 300 записей	0.0112

4. Сравнительный анализ

4.1 Сравнение времени вставки

• LinkedList: 0.0032 сек
• HashTable: 0.0071 сек
• BST (случайный): 0.0028 сек
• BST (отсортированный): 0.0112 сек

4.2 Сравнение времени поиска

• LinkedList: 0.0018 сек
• HashTable: 0.0004 сек
• BST: 0.0003 сек

5. Выводы

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

Плюсы:

• Простая реализация
• Не требует дополнительной памяти

Минусы:

• Медленный поиск
• Медленная вставка в конец

5.2 Хеш-таблица

Плюсы:

• Очень быстрый поиск
• Быстрая вставка и удаление
• Не зависит от порядка данных

Минусы:

• Требуется хорошая хеш-функция
• Дополнительная память для бакетов

5.3 Двоичное дерево поиска

Плюсы:

• Данные всегда в отсортированном виде
• Быстрый поиск на случайных данных

Минусы:

• Сильно замедляется на отсортированных данных
• Сложная реализация удаления

6. Влияние порядка входных данных

Эксперимент подтвердил теоретические оценки:

• BST: на отсортированных данных работает в 4 раза медленнее (0.0112 сек против 0.0028 сек)
• Хеш-таблица: практически не чувствительна к порядку данных
• Связный список: всегда O(n) независимо от порядка

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

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