Qual è la differenza tra un hash e un dizionario?

Hash èuna struttura dati con un nome estremamente scadente in cui il programmatore ha confuso linterfaccia con limplementazione ( e era troppo pigro per scrivere il nome completo, cioè HashTable ricorrendo invece a unabbreviazione, Hash).

Dictionary è il “nome corretto” dellinterfaccia (= ADT ), ovvero un contenitore associativo che mappa chiavi (solitamente univoche) a valori (non necessariamente univoci).

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

Tale implementazione ha due proprietà importanti:

1. le chiavi devono essere ha shable e uguaglianza confrontabile .
2. le voci non appaiono in un ordine particolare nel dizionario.

(Per una chiave per essere hashable significa che possiamo calcolare un valore numerico da una chiave che viene successivamente utilizzata come indice in un array.)

Esistono implementazioni alternative della struttura dati del dizionario che impongono un ordinamento sulle chiavi – questo è spesso chiamato dizionario ordinato (e di solito è implementato in termini di albero di ricerca, sebbene esistano altre implementazioni efficienti).

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

Commenti

• Per dare un esempio in C ++, i modelli di contenitore associativo standard non possono ' essere implementati come hash, sebbene lo standard successivo avrà quelle che sono effettivamente tabelle hash. ' ha chiamato unordered_map per mostrare quello che fanno invece di quello che sono.
• “corretto” secondo quale autorità? In alcune lingue, come Ruby e Perl, il nome ufficiale – leggi “corretto” – per queste strutture è “hash”.
• @nohat: nota il mio uso delle virgolette. Inoltre, ho spiegato perché il nome è stato scelto male, no? Quindi, se hai bisogno di unautorità, dirò che è dallautorità della polizia informatica teorica.
• È interessante notare che in Ruby 1.9 è effettivamente impossibile implementare il Hash classe con una tabella hash, poiché Ruby 1.9 Hash es conserva lordine di inserzione mentre una tabella hash no. Quindi, in Ruby 1.9, il nome Hash ' non riflette nemmeno più limplementazione.
• @hippietrail Ti sbagli: in primo luogo, quelle sono descrizioni oggettive. Dopo tutto, qualifico il motivo per cui la denominazione è scarsa e un termine improprio (vedi sotto). “Troppo pigro” è licenza artistica da parte mia, ma resta il punto che il motivo per abbreviare il nome è intrinseco, cioè non cè motivo di usare un nome breve qui se non per abbreviare il nome. E ti sbagli su “dizionario”: questo è semplicemente il nome ufficiale della struttura dei dati. La tua definizione di “dizionario” è sbagliata nel contesto dellinformatica e il nome precede Python di decenni.

“Dictionary” è il nome del concetto. Una tabella hash è una possibile implementazione.

Commenti

• Anche lhash è un ADT. HashTable è unimplementazione di un hash
• @Sairam Penso che sia molto più comune che ' hash ' significhi una funzione hash invece che una tabella hash.
• @jk In realtà " hash " è il risultato dellapplicazione una " funzione / algoritmo hash " per qualche input. Una " tabella hash " o " mappa hash " omehoe mette in relazione un oggetto hashable con qualche oggetto (oggetto in una forma generica, non limitato a OOP)
• Ci sono linguaggi che usano ' Hash ' per fare riferimento a una struttura di tipo dizionario piuttosto che solo alloperazione della funzione hash. Ruby, ad esempio .

Un dizionario è il termine collettivo dato per qualsiasi implementazione della struttura dati usata per ricerche / inserimenti veloci. Ciò può essere ottenuto / implementato utilizzando una varietà di strutture dati come tabelle hash, elenchi da saltare, albero rb ecc. Una tabella hash è una struttura dati specifica utile per molti scopi, inclusa limplementazione di un dizionario.

Commenti

• Hash è anche un ADT. Cè qualche differenza specifica tra Hash e Dictionary ADT?
• @Sairam: No, un hash è loutput di un certo tipo di algoritmo (funzione hash).

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

ie (KEY => VALUE)

Un hash è più spesso descritto come tabella hash che utilizza una funzione hash per calcolare la posizione in memoria (o più facilmente un array) in cui sarà il valore. Lhash prenderà la CHIAVE come input e darà un valore come output. Quindi inserisci quel valore nella memoria o nellindice dellarray.

ie KEY => HASH FUNCTION => VALUE

Immagino che uno sia diretto mentre laltro non è “t. Anche le funzioni hash potrebbero non essere perfette e talvolta fornire un indice che fa riferimento al valore sbagliato. Ma questo può essere corretto.

Posto migliore dove cercare: Wikipedia ( array associativo e tabella hash )