Qual é a diferença entre um mapa e um dicionário?

Eu sei que um mapa é uma estrutura de dados que mapeia chaves para valores. Um dicionário não é o mesmo? Qual é a diferença entre um mapa e um dicionário ¹ ?

_{1. Não estou perguntando como eles são definidos na linguagem X ou Y (que parece ser o que geralmente as pessoas estão perguntando aqui no SO), quero saber qual é a diferença deles na teoria.}

Dois termos para a mesma coisa:

• "Mapa" é usado por Java, C ++
• "Dictionary" é usado por .Net, Python
• "Matriz associativa" é usada pelo PHP

"Mapa" é o termo matemático correto, mas é evitado porque tem um significado separado na programação funcional .

Algumas linguagens ainda usam outros termos ("Objeto" em Javascript, "Hash" em Ruby, "Tabela" em Lua) , mas todos eles têm significados separados na programação também, então eu os evitaria.

Veja aqui para mais informações.

Um é um termo antigo para o outro. Normalmente, o termo "dicionário" foi usado antes que o termo matemático "mapa" se estabelecesse. Além disso, os dicionários tendem a ter um tipo de string chave, mas isso não é 100% verdadeiro em todos os lugares.

Meus 2 centavos.

Dictionary é uma classe abstrata em Java, enquanto Map é uma interface. Como o Java não suporta várias heranças, se uma classe estender o Dictionary, não poderá estender nenhuma outra classe.

Portanto, a interface do mapa foi introduzida.

A classe Dictionary é obsoleta e o uso do Map é preferido.

Responder a essa pergunta é complicado porque os programadores viram os termos com significados mais específicos em idiomas ou sistemas específicos que eles usaram, mas a pergunta pede uma comparação independente da linguagem "na teoria", o que eu entendo nos termos da Ciência da Computação .

A terminologia explicada

O Dicionário de Ciência da Computação da Universidade de Oxford lista:

dicionário qualquer estrutura de dados que represente um conjunto de elementos que possam suportar a inserção e exclusão de elementos, além de testar a associação

• Por exemplo, temos um conjunto de elementos {A, B, C, D ...} que conseguimos inserir e poderíamos excluir, e podemos consultar "C está presente?" .

A noção de mapa da Computing Science é baseada no mapeamento matemático de termos linguísticos , que o Dicionário Oxford define como:

mapeamento Uma operação que associa cada elemento de um determinado conjunto (o domínio) a um ou mais elementos de um segundo conjunto (o intervalo).

• Como tal, uma estrutura de dados do mapa fornece uma maneira de passar de elementos de um determinado conjunto - conhecidos como " chaves " no mapa, para um ou mais elementos no segundo conjunto - conhecidos como " valor (es) associado ".
• O aspecto "... ou mais elementos no segundo conjunto" pode ser suportado por uma implementação de duas maneiras distintas:
  • Muitas implementações de mapas reforçam a exclusividade das chaves e apenas permitem que cada chave seja associada a um valor, mas esse valor pode ser uma estrutura de dados que contém muitos valores de um tipo de dados mais simples, por exemplo, {{1, {"one" , "ichi"}, {2, {"two", "ni"}}} ilustra valores que consistem em pares de cadeias.
  • Outras implementações de mapas permitem chaves duplicadas, cada mapeamento para valores iguais ou diferentes - o que satisfaz funcionalmente os "associados ... cada elemento [chave] ... com ... mais [um] elemento [valor] elementos" ". Por exemplo, {{1, "one"}, {1, "ichi"}, {2, "two"}, {2, "ni"}}.

Dicionário e mapa contrastados

Portanto, usando a terminologia estrita do Comp Sci acima, um dicionário é apenas um mapa se a interface oferecer suporte a operações adicionais não necessárias em todos os dicionários:

• a capacidade de armazenar elementos com componentes distintos de chave e valor

• a capacidade de recuperar o (s) valor (es) fornecido (s) apenas a chave

Uma torção trivial:

• uma interface de mapa pode não suportar diretamente um teste para verificar se um par {key, value} está no contêiner, o que é pedanticamente um requisito de um dicionário no qual os elementos sejam pares {key, value}; um mapa pode nem ter uma função para testar uma chave, mas, na pior das hipóteses, você pode ver se uma tentativa de recuperação de valor por chave é bem-sucedida ou falha, e se você se importa, pode verificar se a chave recuperou um valor esperado.

Comunique-se de maneira inequívoca com seu público

⚠ Apesar de tudo o que foi exposto acima, se você usar o dicionário no estrito significado da Ciência da Computação explicado acima, não espere que o seu público o siga inicialmente ou fique impressionado ao compartilhar e defender a terminologia. As outras respostas a esta pergunta (e seus upvotes) mostram como é provável que "dicionário" seja sinônimo de "mapa" na experiência da maioria dos programadores. Tente escolher uma terminologia que seja compreendida de maneira mais ampla e inequívoca: por exemplo

• contêiner associativo : qualquer contêiner que armazena pares de chave / valor com recuperação de valor e apagamento por chave
• mapa de hash : uma implementação de tabela de hash de um contêiner associado
• conjunto de hash que impõe chaves exclusivas : uma implementação de tabela de hash de um dicionário que armazena elemento / valores sem tratá-los como contendo componentes distintos de chave / valor, em que duplicatas dos elementos não podem ser inseridas
• equilibrar o mapa de árvore binária que suporta chave duplicada : ...

Terminologia de referência cruzada Comp Sci com implementações específicas

Biblioteca Padrão C ++

• Mapas: map, multimap, unordered_map,unordered_multimap
• outros dicionários: set, multiset, unordered_set,unordered_multiset
• NOTA: Com iterators ou std::findvocê pode apagar um elemento e teste de adesão em array, vector, list, dequeetc, mas as interfaces de recipiente não suportam diretamente que porque encontrar um elemento é espetacularmente ineficiente em O (N), em alguns casos, inserir / apagar estiver ineficiente e o suporte a essas operações prejudicam a API deliberadamente limitada que o contêiner implica - por exemplo, deques devem suportar apenas apagar / pop na frente e atrás e não em termos de alguma chave. Ter que trabalhar mais em código para orquestrar a pesquisa encoraja gentilmente o programador a mudar para uma estrutura de dados de contêiner com uma pesquisa mais eficiente.

... pode adicionar outros idiomas mais tarde / pode editar em ...

Normalmente, assumo que um mapa é apoiado por uma tabela de hash; conota uma loja não ordenada. Os dicionários conectam uma loja solicitada.

Há um dicionário baseado em árvore chamado Trie .

No Lisp, pode ser assim:

(a (n (d t)) n d )

O que encapsula as palavras:

• uma
• e
• formiga
• a
• de Anúncios

A travessia do topo para a folha produz uma palavra.

Não é realmente a mesma coisa. Mapas são um subconjunto de dicionário. Dicionário é definido aqui como tendo as funções de inserção, exclusão e localização. O mapa usado pelo Java (de acordo com isso ) é um dicionário com o requisito de que o mapeamento de chaves para valores seja mapeado estritamente como uma função individual. Um dicionário pode ter mais de um mapa de chave para um valor ou um mapa de chave para vários valores (como encadeamento em uma tabela de hash), por exemplo, pesquisas de hashtag no Twitter.

Como um exemplo mais "mundo real", procurar uma palavra em um dicionário pode nos dar várias definições para a mesma palavra e, quando encontramos uma entrada que nos aponta para outra entrada (veja outra palavra), várias palavras para a mesma lista de definições. No mundo real, os mapas são muito mais amplos, permitindo que tenhamos locais para nomes ou nomes para coordenadas, mas também podemos encontrar um vizinho mais próximo ou outros atributos (populações, etc.), então IMHO poderia haver argumentos para uma maior expansão de o tipo de mapa pode ter implementações baseadas em gráfico, mas seria melhor sempre assumir apenas o par de valores-chave, especialmente porque o vizinho mais próximo e outros atributos do valor poderiam ser apenas membros de dados do valor.

Os mapas java, apesar do requisito individual, podem implementar algo mais como um dicionário generalizado se o valor for generalizado como uma coleção em si, ou se os valores forem meramente referências a coleções armazenadas em outro local.

Lembre-se de que os mantenedores de Java não são os mantenedores das definições de ADT e que as decisões de Java são especificamente para Java.

Outros termos desse conceito bastante comuns: array associativo e hash.

Sim, eles são iguais, você pode adicionar "Matriz associativa" à mistura.

usando Hashtable ou Hashofter refere-se à implementação.

assim, em um nível puramente teórico.

Um dicionário é um valor que pode ser usado para localizar um valor vinculado. Um mapa é um valor que fornece instruções sobre como localizar outros valores

todas as coleções que permitem acesso não linear (ou seja, apenas obtêm o primeiro ou o último) são um mapa, pois mesmo uma matriz simples possui um índice que mapeia o valor correto. Assim, enquanto um dicionário é um tipo de mapa, os mapas são uma gama muito mais ampla de funções possíveis.

Na prática, geralmente é a função de mapeamento que define o nome; portanto, um HashMap é uma estrutura de dados mapeada que usa um algoritmo de hash para vincular a chave ao valor, enquanto um dicionário não especifica como as chaves são vinculadas a um valor. portanto, pode ser armazenado através de uma lista vinculada, árvore ou qualquer outro algoritmo. do ponto de uso, geralmente você não se importa com o algoritmo que eles funcionam, então você usa um dicionário genérico e só muda para uma das outras estruturas apenas quando precisar do tipo de algoritmo

Estes são dois termos diferentes para o mesmo conceito.
Hashtablee HashMaptambém se referem ao mesmo conceito.

A principal diferença é que um mapa exige que todas as entradas (valor e par de chaves) tenham uma chave única. Se ocorrerem colisões, ou seja, quando uma nova entrada tiver a mesma chave que uma entrada já existente na coleção, será necessário o tratamento de colisões.

Normalmente, lidamos com colisões usando um encadeamento separado . Ou sondagem linear .

Um dicionário permite que várias entradas sejam vinculadas à mesma chave.

Quando um mapa implementa o encadeamento separado, ele tende a se parecer com um dicionário.