Qual é a diferença entre estruturas de dados abstratas e concretas?

Eu pensei que matriz associativa (ou seja, mapa ou dicionário) e tabela de hash eram o mesmo conceito, até que vi na Wikipedia que

Para dicionários com um número muito pequeno de ligações, pode fazer sentido implementar o dicionário usando uma lista de associações, uma lista vinculada de ligações. ...

A implementação de propósito geral usada com mais freqüência de uma matriz associativa é com uma tabela de hash: uma matriz de ligações, juntamente com uma função de hash que mapeia cada chave possível em um índice de matriz. ...

Os dicionários também podem ser armazenados em árvores de pesquisa binária ou em estruturas de dados especializadas em um tipo específico de chave, como árvores de raiz, tentativas, matrizes de Judy ou árvores de van Emde Boas. ...

Então, acho que meu problema reside no fato de não saber que a matriz associativa (ou seja, mapa ou dicionário) é um tipo de dados abstrato e a tabela de hash é uma estrutura de dados concreta, e diferentes estruturas de dados concretas podem ser usadas para implementar o método mesmo tipo de dado abstrato.

Minhas perguntas seriam

• Qual é a diferença e a relação entre estruturas de dados abstratas e estruturas de dados concretas?

• Quais exemplos são para cada um deles (estruturas de dados abstratas e concretas)? Quanto mais melhor.

• Existe uma lista de quais estruturas de dados concretas podem ser usadas para implementar quais estruturas de dados abstratas? Seria bom ter um.

O tipo de dados abstratos (ADT) é essencialmente uma API e uma estrutura de dados concreta fornece uma implementação dessa API. Para um determinado ADT, geralmente existem várias opções diferentes de estruturas de dados concretas que suportam as operações de consulta e atualização descritas pelo ADT. Toda estrutura de dados concreta para um determinado ADT deve suportar todas as operações descritas pelo ADT (possivelmente com alguma probabilidade de sucesso no caso de estruturas aleatórias), mas cada estrutura concreta pode oferecer garantias diferentes dos tempos de execução de cada operação. A escolha de qual estrutura de dados concreta a ser implementada para um determinado ADT geralmente depende das prioridades de eficiência de cada operação (incluindo a inicialização da estrutura) e da complexidade de implementar e manter os vários tipos de dados.

Existem muitas ADT e estruturas concretas correspondentes a serem listadas em uma única resposta, mas aqui estão alguns exemplos:

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

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

• A prioridade da fila é um ADT que exige inserte delete-minoperações (e às vezes outras operações, bem como, tais como find-min increase-keyou delete-key). As estruturas de dados que implementam a fila de prioridade ADT incluem:

  1. uma lista vinculada não classificada, que é rápida, insertmas lenta delete-min.

  2. uma lista vinculada classificada, que é rápida, delete-minmas lentainsert

  3. insertdelete-min$sort(n)$

  4. uma pilha binária que possui inicialização logarítmica inserte de delete-mintempo linear.

  5. Há também outras variantes de implementações de heap .

• stabbing(x)$x$

O tipo de dado abstrato descreve quais operações estão disponíveis e quais leis elas obedecem. Por exemplo, um dicionário permite que você armazene um valor em uma determinada chave e recupere um valor para uma chave, e promete que, se você primeiro armazenar um valor e depois recuperá-lo com a mesma chave, receberá o valor armazenado. Uma pilha possui operações push e pop.

O tipo de dados concreto diz como essas operações são realmente implementadas.