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

Hash é uma estrutura de dados extremamente mal nomeada, onde o programador confundiu a interface com a implementação ( e estava com preguiça de escrever o nome completo, ou seja, HashTable em vez de recorrer a uma abreviatura, Hash).

Dictionary é o nome “correto” da interface (= o ADT ), ou seja, um contêiner associativo que mapeia chaves (geralmente exclusivas) para valores (não necessariamente exclusivos).

Uma tabela hash é uma implementação possível de tal dicionário que fornece características de acesso bastante boas (em termos de tempo de execução) e, portanto, é frequentemente a implementação padrão.

Tal implementação tem duas propriedades importantes:

1. as chaves devem ser ha shable e igualdade comparável .
2. as entradas não aparecem em nenhuma ordem específica no dicionário.

(Para uma chave para ser hashble significa que podemos calcular um valor numérico de uma chave que é subsequentemente usada como um índice em uma matriz.)

Existem implementações alternativas da estrutura de dados do dicionário que impõe uma ordenação nas chaves – geralmente é chamado de dicionário classificado (e geralmente é implementado em termos de uma árvore de pesquisa, embora existam outras implementações eficientes).

Para resumir: um dicionário é um ADT que mapeia chaves para valores. Existem várias implementações possíveis deste ADT, das quais a tabela hash é uma delas. Hash é um nome impróprio, mas no contexto é equivalente a um dicionário que é implementado em termos de uma tabela hash.

Comentários

• Para dar um exemplo em C ++, os modelos de contêiner associativo padrão não poderiam ' ser implementados como hashes, embora o próximo padrão tenha o que são efetivamente tabelas de hash. Eles ' são chamados de unordered_map para mostrar o que fazem e não o que são.
• “corretos” de acordo com que autoridade? Em algumas linguagens, como Ruby e Perl, o nome oficial – leia “correto” – para essas estruturas é “hash”.
• @nohat: Observe meu uso de aspas. Além disso, eu expliquei por que o nome foi mal escolhido, não foi? Portanto, se você precisar de uma autoridade, direi que é da autoridade da polícia teórica da ciência da computação.
• Curiosamente, em Ruby 1.9, é realmente impossível implementar o Hash classe com uma tabela hash, já que Ruby 1.9 Hash es preserva a ordem de inserção, enquanto uma tabela hash não. Portanto, em Ruby 1.9, o nome Hash não ' nem reflete mais a implementação.
• @hippietrail Você está errado – primeiro, essas são descrições objetivas. Afinal, qualifico por que a nomenclatura é inadequada e inadequada (veja abaixo). “Preguiçoso demais” é uma licença artística de minha parte, mas permanece o ponto de que a razão para encurtar o nome é intrínseca, ou seja, não há razão para usar um nome curto aqui, exceto para encurtar o nome. E você está errado quanto ao “dicionário”: isso é simplesmente o nome oficial da estrutura de dados. Sua definição de “dicionário” está errada no contexto da ciência da computação, e o nome é anterior a Python em décadas.

“Dicionário” é o nome do conceito. Uma tabela de hash é uma implementação possível.

Comentários

• Hash também é um ADT. HashTable é uma implementação de um Hash
• @Sairam, acho que é muito mais comum para ' hash ' significar uma função hash em vez de uma tabela hash.
• @jk Na verdade, o " hash " é o resultado da aplicação uma " função / algoritmo hash " para alguma entrada. Uma " tabela hash " ou " mapa hash " omehoe relaciona um objeto hashable a algum objeto (objeto em uma forma genérica, não limitado a OOP)
• Existem linguagens que usam ' Hash ' para se referir a uma estrutura do tipo dicionário em vez de apenas à operação da função hash. Ruby, por exemplo .

Um dicionário é o termo coletivo dado para qualquer implementação de estrutura de dados usada para pesquisas / inserções rápidas. Isso pode ser alcançado / implementado usando uma variedade de estruturas de dados como tabela de hash, listas de salto, árvore rb etc. Uma tabela de hash é uma estrutura de dados específica útil para muitos propósitos, incluindo a implementação de um dicionário.

Comentários

• Hash também é um ADT. Existe alguma diferença específica entre Hash e ADT de dicionário?
• @Sairam: Não, um hash é a saída de um certo tipo de algoritmo (função hash).

Um dicionário usa uma chave para referencie o valor diretamente dentro de uma matriz associativa .

ie (KEY => VALUE)

Um hash é mais frequentemente descrito como tabela hash que usa uma função hash para calcular a posição na memória (ou mais facilmente uma matriz) onde o valor estará. O hash pegará a CHAVE como entrada e dará um valor como saída. Em seguida, insira esse valor na memória ou no índice do array.

ie KEY => HASH FUNCTION => VALUE

Acho que um é direto, enquanto o outro isn “t. As funções de hash também podem não ser perfeitas e às vezes podem fornecer um índice referenciando o valor errado. Mas isso pode ser corrigido.

Melhor lugar para procurar: Wikipedia ( array associativo e tabela de hash )