Vad är skillnaden mellan en hash och en ordbok?

Hash är en extremt dåligt namngiven datastruktur där programmeraren har förväxlat gränssnittet med implementering ( och var för lat för att skriva hela namnet, dvs. HashTable istället tillgripa en förkortning, Hash).

Dictionary är “rätt” namn för gränssnittet (= ADT ), dvs. en associerande behållare som mappar (vanligtvis unika) nycklar till (inte nödvändigtvis unika) värden.

En hashtabell är en möjlig implementering av en sådan ordbok som ger ganska bra åtkomstegenskaper (när det gäller körtid) och därför ofta är standardimplementeringen.

En sådan implementering har två viktiga egenskaper:

1. tangenterna måste vara ha shable och jämlikhet jämförbar .
2. posterna visas i ingen särskild ordning i ordboken.

(För en nyckel till vara hashbar betyder att vi kan beräkna ett numeriskt värde från en nyckel som därefter används som ett index i en matris.)

Det finns alternativa implementeringar av ordboksdatastrukturen som inför en ordning på tangenterna – detta kallas ofta en sorterad ordbok (och implementeras vanligtvis i termer av ett sökträd, även om det finns andra effektiva implementeringar).

To sammanfatta: en ordlista är en ADT som mappar nycklar till värden. Det finns flera möjliga implementeringar av denna ADT, varav hash-tabellen är en. Hash är felaktigt men i sitt sammanhang motsvarar det en ordlista som implementeras i termer av en hash-tabell.

Kommentarer

• För att ge ett exempel i C ++ kunde standardassociativa behållarmallar inte ' inte implementeras som hash, även om nästa standard kommer att ha vad som är effektiva hashtabeller. De ' kallas unordered_map för att visa vad de gör snarare än vad de är.
• “rätta” enligt vilken myndighet? På vissa språk, som Ruby och Perl, är det officiella – läs ”rätt” – namnet på dessa strukturer ”hash”.
• @nohat: Lägg märke till att jag använder citat. Dessutom har jag förklarat varför namnet är dåligt valt, eller hur? Så om du behöver en auktoritet så ska jag säga att det är av den teoretiska datavetenskapspolisen.
• Intressant är det i Ruby 1.9 faktiskt omöjligt att implementera Hash klass med en hash-tabell, eftersom Ruby 1.9 Hash es bevarar införingsordningen medan en hash-tabell inte gör det. Så i Ruby 1.9 speglar namnet Hash inte ens ' t ens implementeringen längre.
• @hippietrail Du har fel – först är de objektiva beskrivningar. När allt kommer omkring kvalificerar jag mig för varför namngivningen är dålig och felaktig (se nedan). ”För lat” är konstnärlig licens från min sida men poängen kvarstår att anledningen till att förkorta namnet är inneboende, det vill säga det finns ingen anledning att använda ett kort namn här annat än att förkorta namnet. Och du har fel när det gäller ”ordlista”: det är helt enkelt officiellt namn för datastrukturen. Din definition av ”ordbok” är fel i datavetenskapens sammanhang, och namnet föregår Python med årtionden.

”Ordbok” är konceptets namn. En hashtable är en möjlig implementering.

Kommentarer

• Hash är också en ADT. HashTable är en implementering av en Hash
• @Sairam Jag tror att den är mycket vanligare för ' hash ' en hash-funktion snarare än en hash-tabell.
• @jk Egentligen är " hash " resultatet av tillämpningen en " hash-funktion / algoritm " till någon ingång. En " hash-tabell " eller " hashkarta " omehoe relaterar till och hashable-objekt till något objekt (objekt i generisk form, inte begränsat till OOP)
• Det finns språk som använder ' Hash ' för att hänvisa till en ordbokstypstruktur snarare än bara till hashfunktionen. Ruby, till exempel .

En ordbok är den samlade termen som ges för alla datastrukturimplementeringar som används för snabba sökningar / insättningar. Detta kan uppnås / implementeras med en mängd olika datastrukturer som hashtabell, hopplistor, rb-träd etc. En hashtabell är en specifik datastruktur som är användbar för många ändamål, inklusive implementering av en ordlista.

Kommentarer

• Hash är också en ADT. Finns det någon specifik skillnad mellan Hash och Dictionary ADT?
• @Sairam: Nej, en hash är utdata från en viss typ av algoritm (hash-funktion).

A ordbok använder en nyckel för att referera värdet direkt inuti en associerande matris .

dvs. (KEY => VALUE)

En hash beskrivs oftare som en hashtabell som använder en hashfunktion för att beräkna positionen i minnet (eller lättare en matris) där värdet kommer att vara. Hashet tar KEY som input och ger ett värde som output. Anslut sedan det värdet till minnet eller array-indexet.

dvs KEY => HASH FUNCTION => VALUE

Jag antar att den ena är direkt medan den andra är inte. Hash-funktioner kanske inte är perfekta heller och kan ibland ge ett index som refererar till fel värde. Men det kan korrigeras.

Bästa stället att leta efter: Wikipedia ( associerande array och hash-tabell )