Как выбрать между хеш-таблицей и сбалансированным деревом поиска?

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

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

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

Фундаментальные структуры данных

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

Найти тему в PaperMindСкороFind papers & topics

Tools & resources

Скачать слайды

Learn & explore

ВидеоСкоро

Definition

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

Scope

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

Sub-topics

Core questions

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

Key concepts

абстрактный тип данных
массивы и связные списки
стеки и очереди
хеш-таблицы
бинарные деревья поиска
сбалансированные деревья
кучи и очереди с приоритетом
амортизированный анализ
компромиссы между временем и пространством

Key theories

Абстрактные типы данных против реализаций: Абстрактный тип данных определяет операции и их семантику независимо от представления; несколько конкретных структур данных могут реализовывать один и тот же АТД с различными профилями производительности, что позволяет разработчикам рассуждать о корректности и стоимости отдельно.
Амортизированный анализ: Некоторые структуры (динамические массивы, Splay-деревья) имеют случайные дорогостоящие операции, но дешёвые операции в среднем по последовательности; амортизированный анализ (агрегатный, бухгалтерский, потенциальный методы) строго ограничивает эту среднюю стоимость.

Clinical relevance

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

History

Основополагающие структуры данных были каталогизированы в книге Кнута «Искусство программирования» начиная с 1968 года. Самобалансирующиеся деревья (AVL-деревья, 1962; красно-чёрные деревья и B-деревья в 1970-х) и продвинутые структуры, такие как Фибоначчиевы кучи и Splay-деревья (1980-е, в значительной степени благодаря Тарьяну и его сотрудникам), расширили эту область, в то время как амортизированный анализ дал строгое описание их производительности.

Key figures

Donald Knuth
Robert Sedgewick
Robert Tarjan
Rudolf Bayer

Seminal works

knuth1997vol1
cormen2009
sedgewick2011

Frequently asked questions

Как выбрать между хеш-таблицей и сбалансированным деревом поиска?: Хеш-таблицы обеспечивают ожидаемый поиск и вставку за O(1), но не поддерживают порядок, в то время как сбалансированные деревья поиска обеспечивают операции за O(log n) и сохраняют ключи отсортированными, поддерживая запросы диапазона и упорядоченный обход. Выбирайте хеширование для чистого поиска по ключу и дерево, когда важны порядок или операции с диапазонами.
Что означает амортизированная стоимость для структуры данных?: Амортизированная стоимость — это средняя стоимость одной операции в худшей последовательности операций. Динамический массив, например, иногда тратит O(n) на изменение размера, но в среднем O(1) на добавление, потому что изменения размера редки по сравнению с дешёвыми добавлениями.