Qual è la differenza tra un hash e un dizionario?

Hash è una struttura di dati con un nome estremamente scadente in cui il programmatore ha confuso l'interfaccia con l'implementazione ( e era troppo pigro per scrivere il nome completo, ovvero HashTable invece di ricorrere a un'abbreviazione, Hash ).

Dictionary è il nome "corretto" dell'interfaccia (= il ADT ), ovvero un contenitore associativo che associa (in modo univoco) le chiavi (non necessariamente uniche) ) valori.

Una tabella hash è una possibile implementazione di un tale dizionario che fornisce caratteristiche di accesso piuttosto buone (in termini di runtime) ed è quindi spesso l'implementazione predefinita.

Tale implementazione ha due importanti proprietà:

1. le chiavi devono essere hashable e uguaglianza paragonabile .
2. le voci non appaiono in ordine particolare nel dizionario.

(Perché una chiave sia lavabile significa che possiamo calcolare un valore numerico da una chiave che viene successivamente utilizzata come indice in una matrice.)

Esistono implementazioni alternative della struttura dati del dizionario che impongono un ordinamento sui tasti - questo è spesso definito un dizionario ordinato (e viene solitamente implementato in termini di albero di ricerca, anche se esistono altre implementazioni efficienti.

Per riassumere: un dizionario è un ADT che associa le chiavi ai valori. Ci sono diverse possibili implementazioni di questo ADT, di cui la tabella hash è una. Hash è un termine improprio ma nel contesto è equivalente a un dizionario implementato in termini di tabella hash.

"Dizionario" è il nome del concetto. Una tabella hash è una possibile implementazione.

Un dizionario è il termine collettivo dato per qualsiasi implementazione della struttura dati utilizzata per ricerche / inserzioni veloci. Questo può essere raggiunto / implementato usando una varietà di strutture di dati come la tabella hash, skip list, albero rb ecc. Una tabella hash è una struttura dati specifica utile per molti scopi incluso l'implementazione di un dizionario.

Un dizionario utilizza una chiave per fare riferimento al valore direttamente all'interno di un array associativo .

i.e (KEY => VALUE)

Un hash è più spesso descritto come una tabella hash che utilizza una funzione hash per calcolare la posizione in memoria (o più facilmente array) dove sarà il valore. L'hash prenderà il KEY come input e darà un valore come output. Quindi collega quel valore alla memoria o all'indice dell'array.

i.e KEY => HASH FUNCTION => VALUE

Immagino che uno sia diretto mentre l'altro no. Anche le funzioni hash potrebbero non essere perfette e talvolta fornire un indice che faccia riferimento al valore sbagliato. Ma ciò può essere corretto.

Il posto migliore per cercare: Wikipedia ( array associativo e tabella hash )