Care este diferența dintre un hash și un dicționar?

Hash este o structură de date extrem de slab denumită, în care programatorul a confundat interfața cu implementarea ( și a fost prea leneș pentru a scrie numele complet, adică HashTable recurgând în schimb la o abreviere, Hash).

Dictionary este numele „corect” al interfeței (= ADT ), adică un container asociativ care mapează chei (de obicei unice) la valori (nu neapărat unice).

Un tabel hash este una posibilă implementare a unui astfel de dicționar care oferă caracteristici de acces destul de bune (în termeni de execuție) și, prin urmare, este adesea implementarea implicită.

O astfel de implementare are două proprietăți importante:

1. tastele trebuie să fie ha shable și egalitate comparabilă .
2. intrările nu apar în ordine specială în dicționar.

(Pentru o cheie pentru a fi hashable înseamnă că putem calcula o valoare numerică dintr-o cheie care este ulterior utilizată ca index într-o matrice.)

Există implementări alternative ale structurii de date din dicționar care impun o ordonare pe taste – acesta este adesea numit dicționar sortat (și este de obicei implementat în termenii unui arbore de căutare, deși există și alte implementări eficiente).

To rezumați: un dicționar este un ADT care mapează cheile la valori. Există mai multe implementări posibile ale acestui ADT, dintre care tabelul hash este unul. Hash este un nume greșit, dar în context este echivalent cu un dicționar care este implementat în termenii unui tabel hash.

Comentarii

• Pentru a da un exemplu în C ++, șabloanele de container asociative standard nu ar putea fi ' t implementate ca hash-uri, deși următorul standard va avea ceea ce sunt în mod efectiv tabele de hash. Ei ' au fost numiți unordered_map pentru a arăta mai degrabă ceea ce fac decât ceea ce sunt.
• „corect” conform ce autoritate? În unele limbi, cum ar fi Ruby și Perl, numele oficial – citește „corect” – numele pentru aceste structuri este „hash”.
• @nohat: observați că folosesc ghilimele. Mai mult, am explicat de ce numele este prost ales, nu-i așa? Deci, dacă aveți nevoie de o autoritate, atunci voi spune că este de către autoritatea poliției teoretice în informatică.
• Interesant, în Ruby 1.9, este de fapt imposibil să implementați Hash clasă cu un tabel hash, deoarece Ruby 1.9 Hash es păstrează ordinea de inserare în timp ce un tabel hash nu. Deci, în Ruby 1.9, numele Hash nu ' nu mai reflectă nici măcar implementarea.
• @hippietrail Te înșeli – mai întâi, acele sunt descrieri obiective. La urma urmei, mă calific de ce denumirea este slabă și nu este potrivită (vezi mai jos). „Prea leneș” este o licență artistică din partea mea, dar ideea rămâne că motivul pentru scurtarea numelui este intrinsec, adică nu există niciun motiv pentru a folosi un nume scurt aici, altul decât pentru a scurta numele. Și vă înșelați cu privire la „dicționar”: acesta este pur și simplu numele oficial al structurii de date. Definiția dvs. pentru „dicționar” este greșită în contextul informaticii, iar numele îl precedă pe Python cu decenii.

„Dicționar” este numele conceptului. Un hashtable este o posibilă implementare.

Comentarii

• Hash este, de asemenea, un ADT. HashTable este o implementare a unui Hash
• @Sairam cred că este mult mai comun pentru ' hash ' o funcție hash mai degrabă decât un tabel hash.
• @jk De fapt, " hash " este rezultatul aplicării o " funcție hash / algoritm " la o intrare. Un " tabel hash " sau " hartă hash " omehoe se referă și obiectul hashable la un obiect (obiect într-o formă generică, fără a se limita la OOP)
• Există limbi care folosesc ' Hash ' pentru a se referi la o structură de tip dicționar, mai degrabă decât la operația de funcție hash. Ruby, de exemplu .

Un dicționar este termenul colectiv dat pentru orice implementare a structurii de date folosită pentru căutări / inserții rapide. Acest lucru poate fi realizat / implementat folosind o varietate de structuri de date, cum ar fi tabelul hash, listele de salt, arborele rb etc. Un tabel hash este o structură specifică de date utilă pentru mai multe scopuri, inclusiv implementarea unui dicționar.

Comentarii

• Hash este, de asemenea, un ADT. Există vreo diferență specifică între Hash și Dictionary ADT?
• @Sairam: Nu, un hash este rezultatul unui anumit tip de algoritm (funcție hash).

Un dicționar folosește o cheie pentru faceți referire la valoarea direct în interiorul unei matrice asociativă .

ie (KEY => VALUE)

Un hash este mai des descris ca tabel hash care folosește o funcție hash hash poziția din memorie (sau mai ușor un tablou) unde va fi valoarea. Hash va lua cheia ca intrare și va da o valoare ca ieșire. Apoi conectați acea valoare la indexul de memorie sau matrice.

adică KEY => HASH FUNCTION => VALUE

Cred că una este directă în timp ce cealaltă Isn „t. Funcțiile Hash nu pot fi perfecte și pot furniza uneori un index care face referire la valoarea greșită. Dar acest lucru poate fi corectat.

Cel mai bun loc pentru a căuta: Wikipedia ( array asociativ și tabel hash )