Hva er forskjellen mellom en hash og en ordbok?

Hash er en ekstremt dårlig navngitt datastruktur der programmereren har forvekslet grensesnittet med implementering ( og var for lat til å skrive det fulle navnet, dvs. HashTable i stedet ty til en forkortelse, Hash).

Dictionary er “riktig” navn på grensesnittet (= ADT ), dvs. en assosiativ beholder som tilordner (vanligvis unike) nøkler til (ikke nødvendigvis unike) verdier.

En hash-tabell er en mulig implementering av en slik ordbok som gir ganske gode tilgangskarakteristikker (når det gjelder kjøretid) og derfor ofte er standardimplementeringen.

En slik implementering har to viktige egenskaper:

1. tastene må være ha shable og likeverdighet .
2. oppføringene vises i ingen bestemt rekkefølge i ordboken.

(For en nøkkel til være hashable betyr at vi kan beregne en numerisk verdi fra en nøkkel som deretter blir brukt som en indeks i en matrise.)

Det finnes alternative implementeringer av ordbokens datastruktur som pålegger en ordre på tastene – dette kalles ofte en sortert ordbok (og implementeres vanligvis i form av et søketre, selv om det finnes andre effektive implementeringer).

To oppsummer: en ordbok er en ADT som kartlegger nøkler til verdier. Det er flere mulige implementeringer av denne ADT, som hash-tabellen er en av. Hash er en feilnavn, men i sammenheng er det ekvivalent med en ordbok som er implementert i form av en hash-tabell.

Kommentarer

• For å gi et eksempel i C ++, kunne standardassosiative containermalene ikke ' ikke implementeres som hashes, selv om neste standard vil ha det som faktisk er hash-tabeller. De ' kalles unordered_map for å vise hva de gjør i stedet for hva de er.
• “rette” iht. hvilken autoritet? På noen språk, som Ruby og Perl, er det offisielle – les «riktig» – navnet på disse strukturene «hash».
• @nohat: Legg merke til at jeg bruker sitater. Videre har jeg forklart hvorfor navnet er dårlig valgt, ikke sant? Så hvis du trenger en autoritet, vil jeg si at det er av autoriteten til det teoretiske informatikkpolitiet.
• Interessant, i Ruby 1.9 er det faktisk umulig å implementere Hash klasse med hash-tabell, siden Ruby 1.9 Hash es bevarer innsettingsrekkefølgen mens en hash-tabell ikke gjør det. Så i Ruby 1.9 gjenspeiler ikke navnet Hash implementeringen lenger.
• @hippietrail Du tar feil – for det første er de objektive beskrivelsene. Tross alt kvalifiserer jeg hvorfor navngivningen er dårlig og en feilaktig navn (se nedenfor). «For lat» er kunstnerisk lisens fra min side, men poenget er fortsatt at grunnen til å forkorte navnet er iboende, dvs. det er ingen grunn til å bruke et kort navn her annet enn å forkorte navnet. Og du tar feil når det gjelder «ordbok»: det er ganske enkelt det offisielle navnet til datastrukturen. Definisjonen din av “ordbok” er feil i sammenheng med datavitenskap, og navnet foregår Python med flere tiår.