В чем разница между абстрактными и конкретными структурами данных?

Я думал, что ассоциативный массив (т. Е. Карта или словарь) и таблица хеширования были одним и тем же понятием, пока я не увидел в Википедии, что

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

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

Словари также могут храниться в двоичных деревьях поиска или в структурах данных, специализированных для определенного типа ключей, таких как радикальные деревья, попытки, массивы Джуди или деревья Ван-Эмде-Боаса. ...

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

Мои вопросы будут

• В чем разница и связь между абстрактными структурами данных и конкретными структурами данных?

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

• Есть ли список того, какие конкретные структуры данных могут быть использованы для реализации каких абстрактных структур данных? Было бы неплохо иметь один.

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

Слишком много ADT и соответствующих конкретных структур, чтобы перечислить их в одном ответе, но вот несколько примеров:

• Find(x)$x$$x$Insert(x)Delete(x)

• Findsuccessor(x)$S$$x$$t \in S$$s < t$

• Приоритет очереди является ГТ , которая требует insertи delete-minоперации (а иногда и другие операции , а также, например, find-min increase-keyили delete-key). Структуры данных, которые реализуют приоритетную очередь ADT, включают в себя:

  1. несортированный связанный список, который имеет быстрый, insertно медленный delete-min.

  2. отсортированный связанный список, который имеет быстрый, delete-minно медленныйinsert

  3. insertdelete-min$sort(n)$

  4. двоичная куча , которая имеет логарифмическую insertи delete-min, и линейную инициализацию времени.

  5. Есть и другие варианты реализации кучи .

• stabbing(x)$x$

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

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