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

41

Qual é a diferença entre Hash e Dictionary ?

Vindo de um histórico de scripts, sinto que são semelhantes, mas queria descobrir as diferenças exatas. Pesquisando não me ajudou muito.

    
por Sairam 28.12.2010 / 08:33
fonte

4 respostas

87

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, ie HashTable em vez de recorrer a uma abreviação, Hash ).

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

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

Essa implementação tem duas propriedades importantes:

  1. as chaves devem ser hashable e igualdade comparável .
  2. as entradas aparecem em nenhuma ordem específica no dicionário.

(Para uma chave ser hashable significa que podemos calcular um valor numérico de uma chave que é usada subseqüentemente 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 - isto é frequentemente chamado de dicionário classificado (e é geralmente implementado em termos de um á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. Hash é um nome errado, mas no contexto é equivalente a um dicionário que é implementado em termos de uma tabela de hash.

    
por 28.12.2010 / 11:09
fonte
7

"Dicionário" é o nome do conceito. Uma hashtable é uma implementação possível.

    
por 28.12.2010 / 08:39
fonte
7

Um dicionário é o termo coletivo fornecido 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 pulos, árvore de rb, etc. Uma tabela de hash é uma estrutura de dados específica útil para muitas finalidades, incluindo a implementação de um dicionário.

    
por 28.12.2010 / 08:42
fonte
5

Um dicionário usa uma chave para fazer referência ao valor diretamente dentro de uma matriz associativa .

ou seja, (KEY => VALUE)

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

ou seja, KEY => HASH FUNCTION => VALUE

Eu acho que um é direto enquanto o outro não é. As funções hash também podem não ser perfeitas e podem, às vezes, fornecer um índice que faça referência ao valor incorreto. Mas isso pode ser corrigido.

Melhor lugar para procurar: Wikipedia ( matriz associativa e tabela hash )

    
por 28.12.2010 / 10:51
fonte