19

Estes termos remetem à estruturas que possuem características muito semelhantes, se não iguais. Muitas vezes parecem ser usados intercambiavelmente. Isto seria só nomenclatura diferente dependendo da tecnologia ou tem uma diferença real entre map (em geral unordered, faz diferença?), dictionary, associative array e hash table?

Um pode ser especialização ou implementação do outro? Quais?

Se eles, ou alguns deles, são iguais e só o nome mudam, sabe se existe alguma razão para ter essa fragmentação de nomenclatura? É possível explicar os nomes serem diferentes?

A Wikipedia parecer indicar que é a mesma coisa (quase todos), mas não sei se não foi um artigo mal escrito, por isso só copiar o que tem lá não terá muito valor. Mas fundamentar com fontes diferentes, mesmo demonstrando incoerência no uso é bem útil e cria conhecimento.

Ver:

3
  • 6
    Só responda se entender bem a diferença, uma resposta que "acha" que é, não é boa. Se não surgir nada bom eu responderei depois.
    – Maniero
    Commented 8/01/2020 às 15:33
  • 4
    A nomenclatura "array associativo" foi usada para acessar variáveis em "posições" não numéricas. Por exemplo, em Bash, ${var[1]} acessa a posição 1 da variável var, enquanto ${var[pos]} acessa a posição pos da variável var; e isso é chamado de "array associativo". Por curiosidade, existe um hardware com memória associativa, em que a memória não é acessada por um "endereço numérico", mas por um índice que reflete o conteúdo desejado. Commented 9/01/2020 às 12:35
  • 4
    Engraçado que o tipo "hash" do Harbour {"nome"=>"Alceu", "idade"=>32} é o array associativo. Eu preferiria que tivessem chamado de array associativo mesmo... se bem que por ser XBase provavelmente preferiram escolher um nome para o tipo com "inicial desocupada" para não confundir com outros tipos
    – Largato
    Commented 9/01/2020 às 18:12

3 Respostas 3

11

Como a pergunta é , vamos focar primeiro em definições que... não dependem de uma linguagem específica, e depois partimos para as especificidades de algumas linguagens que forem pertinentes à discussão.


Definições (independente da linguagem)

Dicionário x Map

Das fontes que consultei, apenas uma dá uma definição que vai na contra-mão do "resto do mundo". É uma diferença sutil, mas acho que vale mencionar.

O "do contra"

Segundo o Dictionary of Computer Science da Universidade de Oxford 1, o termo "dicionário" é definido como:

Any data structure representing a set of elements that can support the insertion and deletion of elements as well as a test for membership.

Obs: a versão online só tem esta frase. Para ter a definição completa, só adquirindo a versão paga (ps: eu não adquiri).

Ou seja, segundo esta definição, um dicionário é um conjunto de elementos no qual você pode adicionar e remover elementos, além de verificar se um elemento está contido nele. Importante notar que não são mencionados chaves e valores, tão comumente associados aos termos da pergunta.

Nesta resposta do SOen também é dada a definição de mapping (que não aparece na versão online do Dicionário de Oxford então acredito que o autor da resposta deva ter o livro):

mapping An operation that associates each element of a given set (the domain) with one or more elements of a second set (the range).

Vale notar que o termo é mapping (a operação de mapear um elemento de um determinado conjunto para um ou mais elementos de outro conjunto). Já o map seria uma estrutura que usa esta operação para manter os pares chave-valor(es). Lembrando que as implementações podem ou não exigir que chaves sejam únicas (porém, as definições parecem deixar isso em aberto).

A mesma resposta já citada defende - com base nas definições da Oxford - esta distinção entre os termos, e afirma que um dicionário só é um map se ele suportar as seguintes operações (que não seriam obrigatórias para todo dicionário):

  • guardar elementos com valores distintos de chave/valor
  • consultar e apagar valores, usando-se apenas a chave

Portanto, segundo a definição da Oxford, dicionário seria uma estrutura mais genérica, que permite adicionar e remover elementos, além de verificar se determinado elemento pertence à estrutura, mas sem necessariamente ter pares de chave-valor.

Já um map seria uma estrutura que mapeia um conjunto de chaves para seus respectivos valores, além de permitir as mesmas operações do dicionário (adicionar, remover, consultar), porém usando-se a chave para tal. Seria, portanto, um caso especial de dicionário.

Porém, a própria resposta já citada reconhece que esta distinção não é o "entendimento comum", já que a maioria parece acreditar que dicionário e map são sinônimos, e portanto, os termos seriam intercambiáveis (inclusive, outras respostas à mesma pergunta seguem esta linha).


O "senso comum"

Também consultei o Dictionary of Algorithms and Data Structures do NIST 2 (citado nesta resposta) e ali o termo "dicionário" é definido como:

An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete.

Importante notar que é dito que "dicionário" é um ADT (Abstract Data Type), ou seja, ele só diz o que a estrutura faz (guarda valores que são acessados por suas respectivas chaves, além de poder adicionar, remover e procurar valores), mas não como isso é feito (não dá nenhum detalhe sobre a implementação). E ao contrário da definição de Oxford, ele diz que um dicionário associa (ou mapeia) chaves com seus respectivos valores. Portanto, não há a separação entre dictionary e map, tanto que a definição de map do NIST é:

map: see dictionary

Consultando outros materiais (1, 2, 3, 4, entre muitos outros similares), a impressão que tenho é que a grande maioria parece discordar de Oxford e define que o dicionário obrigatoriamente faz o mapeamento chave-valor, e que os valores sempre são adicionados, atualizados, removidos e buscados a partir da chave.

Muitas fontes ainda adicionam o fato de que a ordem das chaves não é garantida (neste caso seria um dictionary/map unordered) - ou seja, se você iterar pelas chaves, elas podem vir em qualquer ordem, que varia conforme a implementação. Porém, em muitas definições também há a separação dos dicionários em ordenados e não-ordenados, indicando se as chaves devem ou não ser mantidas em determinada ordem, o que também depende da implementação: pode ser a ordem em que foram inseridas (insertion order), ordem alfabética ou qualquer outro critério (neste caso seria sorted - "classificado" em vez de "ordenado"), etc. Em caso de ter alguma ordem ou classificação definida, ele é chamado de ordered/sorted dictionary/map (alguns não fazem a distinção entre ordered e sorted e acabam escolhendo apenas um dos termos).

Enfim, a ideia de que dicionário e map são a mesma coisa está tão difundida que parece ser o "senso comum". Com base nas fontes já citadas (e várias outras que não citei por serem redundantes), me parece que ambos se referem a uma estrutura de dados abstrata (ADT, só diz o que faz, mas não impõe detalhes de implementação), que mapeia chaves a seus valores, e possui operações para adicionar, atualizar, remover e buscar elementos (ou verificar se um elemento existe), usando-se as chaves para tal.


Há ainda outro termo: o livro Algorithms, de Sedgewick e Wayne, descreve o termo Symbol Table (Tabela de Símbolos), que pela definição, é basicamente "o mesmo" que dicionário/map:

The primary purpose of a symbol table is to associate a value with a key. The client can insert key–value pairs into the symbol table with the expectation of later being able to search for the value associated with a given key.

Ou seja, além de ter o mapemaneto chave-valor, o livro também menciona as operações básicas (adicionar, remover, buscar/verificar se existe), além de descrever várias opções que podem ser escolhidas pelas implementações, como o tipo das chaves, se permite chaves duplicadas, valores nulos, se as chaves estão em determinada ordem (Ordered symbol tables, que permitiriam operações adicionais, como obter o valor da maior ou menor chave, ou de chaves que estão em determinado intervalo), etc.

Por fim, outras fontes também mencionam os termos "tabela", ou "associative container" como sinônimos (embora "tabela" dê a impressão de que está expondo um detalhe de implementação, conforme o próximo item).


Tabela Hash

Uma tabela hash é uma forma de implementar um dicionário. O NIST, por exemplo, define hash table assim:

A dictionary in which keys are mapped to array positions by hash functions.

Ou seja, é uma das implementações possíveis de um dicionário (já que também pode ser feito com árvores, por exemplo). Neste caso, ele usa uma tabela hash, que por sua vez usa uma função de hash (que calcula um valor a partir da chave, sendo que esse valor é chamado de hash, veja aqui para mais detalhes).

Claro que a implementação também pode variar, já que há muitas formas de se criar uma função de hash, de tratar colisões, etc.


Array associativo

No artigo da Wikipedia, os termos "dictionary", "map" e "associative container" redirecionam para "Associative array", o que dá a impressão de que este seria o termo "correto" e que os outros seriam sinônimos.

Porém, já houve discussão sobre o nome do artigo, sugerindo mudá-lo para Map ou Dictionary, argumentando que são termos mais usados que "array associativo" (que por sua vez, seria o "menos popular", pois "só PHP usa" reclamem com quem iniciou a discussão, não comigo). Mas pelo jeito não foi pra frente, já que o nome do artigo continua sendo "Associative array".

No fim das contas, seria o mesmo que dicionário/map, apenas mais um termo para se referir à mesma coisa. Porém, pode-se argumentar que "array" na verdade está expondo um detalhe de implementação, e que portanto não seria um ADT, ou que ter "array" no nome é confuso, já que se trata de outra estrutura de dados completamente diferente (esse foi um dos argumentos para defender a mudança no nome do artigo, aliás).

O NIST define "associative array" desta forma:

A collection of items that are randomly accessible by a key, often a string.

O que me parece similar a um dicionário, embora só haja uma menção explícita à operação de consulta. Mas acredito que as outras estejam implícitas, afinal, se não desse nem para adicionar, seria uma estrutura de utilidade bem limitada.

Fora a Wikipedia, a única fonte que encontrei que menciona este termo (como conceito abstrato e independente de linguagem) é o já citado livro Algorithms, ao falar sobre o caso específico em que uma tabela de símbolos não permite chaves duplicadas:

Duplicate keys. Only one value is associated with each key (no duplicate keys in a table). When a client puts a key-value pair into a table already containing that key (and an associated value), the new value replaces the old one. These conventions define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.

Ou seja, mesmo que o termo seja mencionado, ele refere-se a um tipo específico de dicionário (e ainda me passa uma impressão de que há vazamento de abstração, ao citar explicitamente uma tabela e sua correlação com o array).

Portanto, não fico seguro em afirmar que, conceitualmente falando, "array associativo" é um termo equivalente a "dicionário" ou "map" (exceto se determinada implementação garantir que é, para o seu contexto específico).


Dado tudo que foi dito acima, me parece que o "senso comum" é de que os conceitos de dicionário e map são aceitos como sinônimos (ADT, mapeia chave-valor, operações básicas), enquanto array associativo é um pouco mais debatível. No fundo, depende de para quem você pergunta, mas os links estão aí e cada um que tire suas próprias conclusões.

Já o termo "tabela hash" refere-se à implementação.


Implementações

Não vou colocar todas as linguagens, apenas citarei alguns casos que achei pertinentes. Se quiser um comparativo mais completo, tem aqui.

De forma geral, vejo que cada linguagem dá o nome que quer, e nem sempre corresponde às definições acima. E como as próprias definições dos conceitos também divergem em certos pontos, me parece - infelizmente - natural que as implementações também o façam.

Lembrando que tudo que é dito abaixo sobre as linguagens referem-se à implementação atual (exceto quando versões anteriores forem mencionadas), consultadas na data desta resposta. Pois como são detalhes de implementação, podem perfeitamente mudar - muitas vezes sem aviso - em versões futuras.


Java

Em Java existe a classe abstrata Dictionary (obsoleta) e uma subclasse Hashtable, o que mostra que pelo menos conceitualmente houve uma preocupação com a nomenclatura (já que um dicionário é um ADT e uma das formas de implementar é com tabelas hash).

Porém, a recomendação é que qualquer implementação atual use a interface Map e suas várias implementações. A mais comum (pelo menos é a que vejo sendo usada com mais frequência) é o HashMap, que segundo a documentação (e como o próprio nome diz) é implementando com uma tabela hash e não garante a ordem das chaves. Mas também há implementações que garantem a ordem, como TreeMap (que é implementado com uma árvore rubro-negra e usa a ordem natural das chaves, mas você também pode customizar a ordenação usando um Comparator) ou LinkedHashMap, que mantém as chaves na ordem em que foram inseridas (usando uma tabela hash para o dicionário e uma lista duplamente ligada para manter a ordem das chaves).

Ou seja, Java optou pelo termo Map (<speculation>talvez porque Dictionary já havia sido usado, e depois que esta classe ficou obsoleta, acabaram tendo que usar outro termo</speculation>), cuja implementação está de acordo com as definições vistas acima. Claro que há alguns detalhes específicos (algumas classes permitem chaves e/ou valores nulos, outras não, etc), mas de forma geral, me parece não desviar das definições.


Python

Em Python existe o dicionário (dict), que me parece estar de acordo com as definições acima (possui as operações para adicionar/remover/atualizar/procurar chaves, que são mapeadas para os respectivos valores).

Um detalhe é que a partir do Python 3.7 é garantido que as chaves estarão na ordem em que foram inseridas (obs: no CPython 3.6 isso era um detalhe de implementação, mas a partir do Python 3.7 isso é garantido - e aprovado pelo próprio BDFL - para todas as implementações da linguagem - ver mais aqui).

Vale lembrar que também existe o OrderedDict, que além de manter as chaves em ordem de inserção, possui outras funcionalidades, como a opção de mover uma chave para o final, além de levar em conta a ordem nas comparações:

d1 = { 'a': 1, 'b': 2 }
d2 = { 'b': 2, 'a': 1 }
# chaves em ordem diferente
print(d1.keys()) # dict_keys(['a', 'b'])
print(d2.keys()) # dict_keys(['b', 'a'])
# apesar disso, os dicionários são iguais
print(d1 == d2) # True

# com OrderedDict, é diferente
from collections import OrderedDict
d1 = OrderedDict({ 'a': 1, 'b': 2 })
d2 = OrderedDict({ 'b': 2, 'a': 1 })
print(d1.keys()) # odict_keys(['a', 'b'])
print(d2.keys()) # odict_keys(['b', 'a'])
# chaves não estão na mesma ordem, dicionários não são iguais
print(d1 == d2) # False

Internamente, um dict é implementado com uma tabela hash.


C#

Em C# temos a classe Dictionary, que representa uma coleção de chaves e valores, não garante a ordem das chaves e é implementado com uma tabela hash. Existe também o SortedDictionary, que ordena as chaves e é implementado com uma árvore binária.


JavaScript

Historicamente, objetos têm sido usados como dicionários/maps, já que eles possuem as funcionalidades necessárias: posso adicionar, apagar e obter valores a partir de uma chave, além de testar a existência da mesma. Ex:

const obj = { 'a': 1, 'b': 2 };
// atualiza a chave e obtém o valor
obj.a = 3;
console.log(obj.a); // 3
// se a chave existe, apaga
if ('b' in obj) delete obj['b'];
console.log(obj); // { a: 3 }

Vale lembrar que o uso de objetos como dicionários tem alguns poréns: o protótipo do objeto pode ter propriedades (ou seja, "chaves") que podem conflitar com aquelas definidas no próprio objeto:

Object.prototype.c = 3;
const obj = { 'a': 1, 'b': 2 };
// verifica se a chave "C" está no objeto
console.log('c' in obj); // true (pois a propriedade "c" está no prototype)

Neste caso, a solução para evitar este problema seria usar um Map, que é um objeto específico para guardar pares de chave-valor, além de ter todas as operações de um dicionário e manter as chaves na ordem de inserção (o Map não existia nas versões iniciais da linguagem, o que pode explicar a preferência por usar objetos como dicionários, muito comum até hoje). Veja a diferença:

Object.prototype.c = 3;
const obj = new Map([ ['a', 1], ['b', 2] ]);
// verifica se a chave "C" está no objeto
console.log(obj.has('c')); // false (não é afetada pelo prototype)

// se usar o operador "in", ele ainda olha no prototype
// por isso, para ver se a chave existe no Map, o recomendado é usar has()
console.log('c' in obj); // true

Há outras diferenças entre um Map e um objeto "comum", veja aqui para mais detalhes. Mas de forma geral, o Map me parece mais adequado, pois a impressão que tenho é que foi feito especialmente para ser uma implementação de um dicionário.

Ver também:


PHP

Em PHP existe o array, que na verdade é uma estrutura "faz-tudo". Segundo a documentação (com ênfase minha):

An array in PHP is actually an ordered map. A map is a type that associates values to keys. This type is optimized for several different uses; it can be treated as an array, list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, and probably more

Ou seja, no fundo o array é um dicionário/map, mas que pode ser tratado como o array "clássico" de outras linguagens (estrutura sequencial com índices numéricos), tendo os índices numéricos agindo como chaves. Interessante que o trecho acima trata a tabela hash (uma implementação de map) e o dicionário como dois itens distintos.

Vale lembrar também que a documentação menciona que "PHP arrays can contain int and string keys at the same time as PHP does not distinguish between indexed and associative arrays". Repare no uso do termo "associative array". De fato, conforme argumentado na discussão da Wikipedia - e pelo menos nas linguagens que conheço melhor - PHP parece ser uma das poucas linguagens que usam este termo oficialmente, para se referir a uma estrutura que implementa o conceito do ADT dicionário/map.

Em JavaScript, por exemplo, encontramos o termo "associative array" na documentação da MDN ("If you want to use an ordered associative array in a cross-browser environment, use a Map object"), mas a especificação da linguagem não contém nenhuma menção ao termo. Outras linguagens parecem preferir dicionário ou map, mas como já disse, não conheço todas, então (sempre) tem uma chance de eu estar enviesado/errado.

Ver também:


Ruby/Perl

Em Ruby existe a classe Hash, que mapeia pares de chave-valor e possui as operações já mencionadas (adicionar, remover, etc). Em Perl, a estrutura que possui essas características também se chama Hash), embora haja menção a "associative array" na documentação.

Enfim, este exemplo foi só para registrar mais um dos muitos nomes usados para se referir à implementação de um dicionário.


Conclusão

Os termos "dicionário", "map" e "array associativo" podem ou não ser intercambiáveis, dependendo do contexto. Em alguns círculos/comunidades, uns podem ser mais aceitos que outros, e os nomes escolhidos pela linguagem podem ter forte influência nisso.

A definição mais, digamos, acadêmica considera que dicionário e map referem-se ao ADT (podendo ser idênticos, ou um ser uma variação do outro), enquanto "array associativo" parece ser mais restrito e controverso. Características como a ordem/classificação ou a unicididade das chaves podem ou não ser consideradas "obrigatórias". Quanto à implementação, cada linguagem dá o nome que bem entender (algumas são mais "fiéis" às definições, outras nem tanto).

Já a tabela hash eu não diria que é intercambiável, por se tratar de um detalhe específico de implementação.

Enfim, o que fica é a dica de ler a documentação de cada linguagem para saber o que de fato é cada estrutura, já que somente pelos nomes não dá para ter 100% de certeza sobre o que eles são. Eu não sei os motivos de cada uma ter optado por determinado nome, e nem quero especular, só posso lamentar por ser tão bagunçado. Isso mostra que de fato é complicado dar nomes para as coisas.


1 - neste caso, é tanto um dicionário no sentido não-computacional (um livro que contém a definição de vários termos), como no sentido computacional (mapeia cada termo - que seriam as chaves - para sua respectiva definição - que seriam os valores) :-)
2 - idem 1 (mas em vez de livro, é um site)

4
  • 2
    Uma das coisas que eu acho, já que não tem consenso absoluto, é que o dicionário tem chave única (dict<word, definitons>) e o mapa não necessariamente (map<word, definiton>, note a sutileza), embora possa ter. A tabela e o array são mesmo detalhes de implementação, sendo o array associativo um nome errado de chamar a tabela hash (PHP sendo PHP e outros indo na onda). Boas linguagens escolhem se querem um ADT ou um detalhe exposto, só para confirmar sua resposta, que acho que passa ser uma das melhores fontes sobre o assunto na internet, ainda que não encerre o assunto.
    – Maniero
    Commented 29/06/2021 às 17:23
  • Eu acho que algumas definições "formais" citadas são muito sem vergonhas, parece não ser bem pensadas, mas é o que tem, a pesquisa aqui foi boa.
    – Maniero
    Commented 29/06/2021 às 17:27
  • 1
    Eu gostaria que fosse: hashtable => unordered (unique); associative array => ordered (non unique); dictionary => sorted (unique, mas deveria ter um outro nome para a estrutura classificada com duplicidade de chaves); map => implementação e garantias não definidas, só tem chave e valor, e manipulação das entradas como requisitos, e pode ter mais e uma entrada. O mapa eu fico mais em dúvida, quem sabe ele deveria ser o multi sorted e não ter um mais abstrato. Faz sentido?
    – Maniero
    Commented 29/06/2021 às 18:12
  • 1
    @Maniero Num mundo ideal teríamos estruturas com nomes bem definidos e que não variam conforme a linguagem/tecnologia. Poderia ser sua ideia, assim como qualquer outra variação, desde que fosse consenso geral, e não a bagunça que é atualmente. Mas como a chance de alguém arrumar isso e conseguir um consenso comum a todos é bem pequena, só nos resta aceitar que cada linguagem vai usar os termos que bem entender, e a gente que se vire :-/
    – hkotsubo
    Commented 30/06/2021 às 0:41
11
+50

Array associativo (Javascript, PHP), dicionário (Python) e Map (Java, C++) são a mesma coisa.

Também são chamados de "hash", mas isso é uma metonímia, a função de hash é o coração de uma implementação eficiente de array associativo. Mas pode-se implementar array associativa de outros jeitos.

Em Java, Map é a interface de array associativo. HashMap é uma implementação de Map que usa hash, EnumMap é uma impl. que usa um vetor (array sequencial), LinkedHashMap permite o acesso das chaves na ordem em que foram inseridas, e TreeMap permite o acesso das chaves em ordem alfabética/numérica (implementação é baseada em árvore, não em hash).

1
-4

Um mapa, um dicionário, um array associativo e uma tabela hash são estruturas de dados que permitem associar valores a chaves para realizar operações de busca, inserção e remoção eficientes. Embora esses conceitos tenham semelhanças, existem diferenças sutis entre eles.

Mesmo assim os termos mapa, dicionário, array associativo e tabela hash são frequentemente usados de forma intercambiável, dependendo da linguagem de programação ou contexto. No entanto, eles se referem a estruturas de dados que têm em comum a capacidade de associar chaves a valores, com diferentes implementações e nuances específicas em cada caso. A escolha da estrutura a ser usada depende das necessidades específicas de um projeto e das características da linguagem de programação em questão.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .