Hvad er forskellen mellem Hash og Dictionary?

Jeg kommer fra en scriptingbaggrund og føler, at de ligner hinanden, men jeg ønskede at finde ud af de nøjagtige forskelle. Googling hjalp mig ikke meget.

Svar

Hash er en ekstremt dårligt navngivet datastruktur, hvor programmøren har forvekslet grænsefladen med implementering ( og var for doven til at skrive det fulde navn, dvs. HashTable i stedet for at bruge en forkortelse, Hash).

Dictionary er “korrekt” navn på grænsefladen (= ADT ), dvs. en associerende beholder, der kortlægger (normalt unikke) nøgler til (ikke nødvendigvis entydige) værdier.

En hash-tabel er en mulig implementering af en sådan ordbog, der giver ganske gode adgangskarakteristika (med hensyn til runtime) og derfor ofte er standardimplementeringen.

En sådan implementering har to vigtige egenskaber:

  1. tasterne skal være ha shable og ligestilling sammenlignelig .
  2. posterne vises i ingen særlig rækkefølge i ordbogen.

(For en nøgle til være hashable betyder, at vi kan beregne en numerisk værdi ud fra en nøgle, som efterfølgende bruges som et indeks i en matrix.)

Der findes alternative implementeringer af ordbogsdatastrukturen, der pålægger en ordre på tasterne – dette kaldes ofte en sorteret ordbog (og implementeres normalt i form af et søgetræ, selvom der findes andre effektive implementeringer).

Til opsummer: en ordbog er en ADT, der kortlægger nøgler til værdier. Der er flere mulige implementeringer af denne ADT, hvoraf hash-tabellen er en. Hash er en misvisende betegnelse, men i kontekst svarer det til en ordbog, der er implementeret i form af en hash-tabel.

Kommentarer

  • For at give et eksempel i C ++ kunne standardassociative container-skabeloner ikke ' ikke implementeres som hashes, selvom den næste standard vil have, hvad der faktisk er hash-tabeller. De ' kaldes unordered_map for at vise hvad de gør i stedet for hvad de er.
  • “korrekt” i henhold til hvilken autoritet? På nogle sprog, såsom Ruby og Perl, er det officielle – læs “korrekt” – navnet på disse strukturer “hash”.
  • @nohat: Bemærk min brug af citater. Desuden har jeg forklaret, hvorfor navnet er dårligt valgt, har jeg ikke? Så hvis du har brug for en autoritet, så vil jeg sige, at det er under myndighed fra det teoretiske datalogipoliti.
  • Interessant nok er det i Ruby 1.9 faktisk umuligt at implementere Hash klasse med en hash-tabel, da Ruby 1.9 Hash es bevarer indsættelsesrækkefølgen, mens en hash-tabel ikke gør det. Så i Ruby 1.9 afspejler navnet Hash ikke engang ' implementeringen mere.
  • @hippietrail Du tager fejl – for det første er disse objektive beskrivelser. Når alt kommer til alt kvalificerer jeg mig til, hvorfor navngivningen er dårlig og en misvisende betegnelse (se nedenfor). “For doven” er kunstnerisk licens fra min side, men pointen er, at grunden til at forkorte navnet er iboende, dvs. der er ingen grund til at bruge et kort navn her andet end at forkorte navnet. Og du tager fejl med “ordbog”: det er simpelthen officielt navn af datastrukturen. Din definition af “ordbog” er forkert i forbindelse med datalogi, og navnet forud for Python med årtier.

Svar

“Ordbog” er konceptets navn. En hashtable er en mulig implementering.

Kommentarer

  • Hash er også en ADT. HashTable er en implementering af en Hash
  • @Sairam Jeg tror det er langt mere almindeligt for ' hash ' en hash-funktion snarere end en hash-tabel.
  • @jk Faktisk er " hash " resultatet af anvendelse en " hash-funktion / algoritme " til noget input. En " hash-tabel " eller " hash-kort " omehoe relaterer til og hashable objekt til et objekt (objekt i generisk form, ikke begrænset til OOP)
  • Der er sprog, der bruger ' Hash ' for at henvise til en ordbogstypestruktur snarere end blot til hash-funktion. Ruby, for eksempel .

Svar

En ordbog er den samlede betegnelse for enhver datastrukturimplementering, der bruges til hurtige opslag / indsættelser. Dette kan opnås / implementeres ved hjælp af en række datastrukturer som hash-tabel, springlister, rb-træ osv. En hash-tabel er en specifik datastruktur, der er nyttig til mange formål, herunder implementering af en ordbog.

Kommentarer

  • Hash er også en ADT. Er der nogen specifik forskel mellem Hash og ordbog ADT?
  • @Sairam: Nej, en hash er output fra en bestemt type algoritme (hash-funktion).

Svar

A ordbog bruger en nøgle til henvise til værdien direkte inde i et associativt array .

dvs. (KEY => VALUE)

En hash beskrives oftere som en hash-tabel som bruger en hash-funktion til at beregne positionen i hukommelsen (eller lettere en matrix), hvor værdien vil være. Hashet tager KEY som input og giver en værdi som output. Sæt derefter denne værdi i hukommelsen eller arrayindekset.

dvs. KEY => HASH FUNCTION => VALUE

Jeg antager, at den ene er direkte, mens den anden isn “t. Hash-funktioner er muligvis heller ikke perfekte og kan undertiden give et indeks, der henviser til den forkerte værdi. Men det kan rettes.

Bedste sted at kigge på: Wikipedia ( associativ matrix og hash-tabel )

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *