Отчёт по экспериментальному сравнению структур данных телефонного справочника
1. Условия эксперимента
Реализованы три структуры для хранения записей вида {name, phone}:

односвязный список (вставка в голову);

хеш-таблица с цепочками (размер таблицы ~ 2N, простое число, хеш-функция hash(name) % size);

двоичное дерево поиска без балансировки.

Измерялось время выполнения операций вставки N = 10 000 записей, поиска 110 имён (100 существующих + 10 несуществующих) и удаления 50 случайных записей.
Эксперименты проводились для двух вариантов порядка входных данных:

shuffled – случайный порядок имён;

sorted – имена, отсортированные по алфавиту.
Каждый замер повторялся 5 раз, результаты усреднены.

Полученные средние значения (фрагмент):

Структура	Режим	Вставка (сек)	Поиск (сек)	Удаление (сек)
LinkedList	shuffled	~0.003	~0.100	~0.056
LinkedList	sorted	~0.003	~0.063	~0.038
HashTable	shuffled	~0.008	~0.00006	~0.00004
HashTable	sorted	~0.006	~0.00008	~0.00003
BST	shuffled	~0.055	~0.0005	~0.00027
BST	sorted	~23.997	~0.212	~0.129
Точные числа см. в файле results.csv

2. Сравнительный анализ
2.1. Влияние порядка данных на BST: деградация до O(n)
На shuffled-данных дерево строится относительно сбалансированным, и операции выполняются в среднем за O(log N).
На sorted-данных каждая следующая вставка попадает строго в правого потомка, и дерево вырождается в линейный список. Глубина рекурсии достигает N = 10 000, что приводит к:

колоссальному росту времени вставки (с ~0.055 сек до ~24 сек);

значительному замедлению поиска и удаления (с ~0.0005 сек до ~0.21 сек и с ~0.00027 сек до ~0.13 сек соответственно).
Причина — рекурсивные функции вынуждены обходить все N узлов, превращая логарифмическую сложность в линейную. Практический вывод: использовать несбалансированное BST можно только при гарантированно случайном порядке поступающих ключей, иначе необходимы самобалансирующиеся варианты (AVL, красно-чёрное дерево).

2.2. Почему хеш-таблица почти не чувствительна к порядку
Хеш-функция равномерно распределяет ключи по корзинам независимо от порядка поступления. Операции вставки, поиска и удаления сводятся к вычислению хеша и проходу по очень короткой цепочке (в среднем O(1)). Время вставки в отсортированном наборе даже чуть меньше (0.006 сек против 0.008 сек), что объясняется меньшим количеством коллизий при последовательном поступлении близких имён (хотя разница несущественна). Поиск и удаление занимают доли миллисекунды и практически не зависят от размера набора в исследованном диапазоне. Хеш-таблица демонстрирует наилучшую устойчивость к любым шаблонам входных данных при условии хорошей хеш-функции и адекватного размера.

2.3. Почему связный список всегда медленен при поиске
В односвязном списке единственный способ найти элемент — линейный проход от головы к хвосту. Среднее время поиска — O(N), то есть пропорционально количеству записей. В эксперименте при 10 000 записей и поиске 110 имён время составило около 0.1 сек, что на три порядка хуже, чем у хеш-таблицы, и на два порядка хуже, чем у сбалансированного BST. Режим sorted/shuffled влияет слабо (для списка порядок вставки не меняет структуру). Медленный поиск — фундаментальное ограничение связного списка.

2.4. Удаление в каждой структуре
Связный список: удаление требует поиска элемента (O(N)) и изменения ссылки у предыдущего узла. Время удаления соизмеримо с поиском (0.038–0.056 сек).

Хеш-таблица: удаление выполняется за O(1) в среднем — вычисление индекса, поиск в цепочке (очень короткой) и изменение ссылок. Время минимально (~0.00004 сек).

BST: удаление узла с двумя потомками требует поиска минимального элемента в правом поддереве. На сбалансированных данных (shuffled) время ~0.00027 сек. На вырожденных (sorted) удаление замедляется до 0.13 сек из-за необходимости обходить длинные цепочки.

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

Если требуется хранить данные в отсортированном виде и нужны операции типа «найти следующий/предыдущий» – подходит BST, но обязательно самобалансирующееся (например, АВЛ или красно-чёрное дерево). Несбалансированное BST применимо только при случайном порядке вставки; иначе деградация до O(n) делает его бесполезным.

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

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