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

46

Qual é a diferença entre Hashe Dictionary?

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

data-structures hashing dictionary difference hashtable Sairam
fonte

Respostas:

92

Hashé uma estrutura de dados extremamente mal nomeada em que o programador confundiu a interface com a implementação ( e ficou com preguiça de escrever o nome completo, ou seja, HashTablerecorrendo a uma abreviação Hash).

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

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, geralmente é a implementação padrão.

Essa implementação tem duas propriedades importantes:

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

(Para uma chave ser lavável, significa que podemos calcular um valor numérico a partir de uma chave que é subsequentemente usada como índice em uma matriz.)

Existem implementações alternativas da estrutura de dados do dicionário que impõem uma ordem às chaves - isso 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 de hash é uma. Hashé um nome impróprio, mas no contexto é equivalente a um dicionário implementado em termos de uma tabela de hash.

Konrad Rudolph
fonte
4
Para dar um exemplo em C ++, os modelos de contêiner associativo padrão não puderam ser implementados como hashes, embora o próximo padrão tenha o que são efetivamente tabelas de hash. Eles são chamados unordered_mappara mostrar o que fazem e não o que são.
David Thornley
6
"Correto" de acordo com que autoridade? Em alguns idiomas, como Ruby e Perl, o nome oficial - leia “correto” - para essas estruturas é “hash”.
nohat
11
@ nohat: Observe meu uso de aspas. Além disso, eu já explicou por que o nome é mal escolhido, não tenho eu? Então, se você precisar de uma autoridade, direi que é da autoridade da polícia teórica da ciência da computação.
Konrad Rudolph
9
Curiosamente, no Ruby 1.9, é realmente impossível implementar a Hashclasse com uma tabela de hash, pois o Ruby 1.9 Hashes preserva a ordem de inserção enquanto uma tabela de hash não. Portanto, no Ruby 1.9, o nome Hashnem reflete mais a implementação.
Jörg W Mittag
7
@hippietrail Você está errado - primeiro, essas são descrições objetivas. Afinal, qualifico por que a nomeação é ruim e um nome impróprio (veja abaixo). “Preguiçoso” é uma licença artística da minha parte, mas o argumento é que o motivo para encurtar o nome é intrínseco, ou seja, não há motivo para usar um nome abreviado aqui além de encurtar o nome. E você está errado sobre "dicionário": esse é 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 antecede o Python há décadas.
Konrad Rudolph
8

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

dan_waterworth
fonte
1
Hash também é um ADT. HashTable é uma implementação de um Hash
Sairam
3
Acho que é muito mais comum 'hash' significar uma função hash do que uma tabela hash.
jk.
@jk Na verdade, o "hash" é o resultado da aplicação de uma "função / algoritmo de hash" a alguma entrada. Um "tabela hash" ou "mapa de hash" refere omehoe e objeto Hashable para um objecto (objecto de uma forma genérica, não se limitando a OOP)
Johannes
Existem idiomas que usam 'Hash' para se referir a uma estrutura do tipo dicionário, e não apenas à operação da função hash. Ruby, por exemplo .
Sean Burton
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 muitos propósitos, incluindo a implementação de um dicionário.

aufather
fonte
Hash também é um ADT. Existe alguma diferença específica entre o Hash e o Dictionary ADT?
Sairam
2
@ Washam: Não, um hash é a saída de um certo tipo de algoritmo (função de hash).
5

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

ie (KEY => VALUE)

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

ie KEY => HASH FUNCTION => VALUE

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

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

Ross
fonte