Sådan implementeres en simpel hash-tabel i JavaScript

Hvor smuk er det {}?

Det giver dig mulighed for at gemme værdier efter nøgle og hente dem på en meget omkostningseffektiv måde ( O(1)mere om dette senere).

I dette indlæg vil jeg implementere en meget grundlæggende hash-tabel og se på dens indre funktion for at forklare en af ​​de mest geniale ideer inden for datalogi.

Problemet

Forestil dig, at du bygger et nyt programmeringssprog: du starter med at have ret enkle typer (strenge, heltal, flyder, ...) og derefter fortsætte med at implementere meget grundlæggende datastrukturer. Først kommer du op med arrayet ( []), så kommer hash-tabellen (ellers kendt som ordbog, associativt array, hashmap, kort og ... listen fortsætter).

Har du nogensinde spekuleret på, hvordan de fungerer? Hvordan er de så forbandede hurtige?

Lad os sige, at JavaScript ikke havde {}eller new Map(), og lad os implementere vores helt egne DumbMap!

En note om kompleksitet

Før vi får bolden til at køre, er vi nødt til at forstå, hvordan kompleksiteten af ​​en funktion fungerer: Wikipedia har en god opdatering af beregningskompleksitet, men jeg vil tilføje en kort forklaring på de dovne.

Kompleksitet måler, hvor mange trin der kræves af vores funktion - jo færre trin, jo hurtigere udførelse (også kendt som "driftstid").

Lad os se på følgende uddrag:

function fn(n, m) { return n * m}

Den beregningsmæssige kompleksitet (fra nu af simpelthen "kompleksitet") af fner O(1), hvilket betyder, at den er konstant (du kan læse O(1)som " prisen er en "): uanset hvilke argumenter du sender, den platform, der kører denne kode, skal kun udføre en operation (formere sig ntil m). Igen, da det er en operation, betegnes omkostningerne som O(1).

Kompleksitet måles ved at antage, at argumenter for din funktion kan have meget store værdier. Lad os se på dette eksempel:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Du ville tro, at dens kompleksitet er O(3), ikke?

Igen, da kompleksitet måles i sammenhæng med meget store argumenter, har vi tendens til at "droppe" konstanter og betragter O(3)det samme som O(1). Så selv i dette tilfælde vil vi sige, at kompleksiteten fner O(1). Uanset hvad værdien af nog mer, ender du altid med at udføre tre operationer - hvilket igen er en konstant pris (derfor O(1)).

Nu er dette eksempel lidt anderledes:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Som du ser, løber vi lige så mange gange som værdien af n, hvilket kunne være i millioner. I dette tilfælde definerer vi kompleksiteten af ​​denne funktion som O(n), da du bliver nødt til at udføre så mange operationer som værdien af ​​et af dine argumenter.

Andre eksempler?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Disse eksempler sløjfer 2 * ngange, hvilket betyder, at kompleksiteten skal være O(2n). Da vi nævnte, at konstanter "ignoreres" ved beregning af en funktions kompleksitet, klassificeres dette eksempel også som O(n).

En til?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Her løber vi rundt nog løber igen inde i hovedsløjfen, hvilket betyder, at kompleksiteten er "kvadratisk" ( n * n): hvis ner 2, løber vi s.push(m)4 gange, hvis 3 kører vi den 9 gange osv.

I dette tilfælde betegnes funktionens kompleksitet som O(n²).

Et sidste eksempel?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

I dette tilfælde har vi ikke indlejrede sløjfer, men vi sløjfer to gange over to forskellige argumenter: kompleksiteten er defineret som O(n+m). Krystalklar.

Nu hvor du lige har fået en kort introduktion (eller opdatering) om kompleksitet, er det meget let at forstå, at en funktion med kompleksitet O(1)vil fungere meget bedre end en med O(n).

Hash-tabeller har en O(1)kompleksitet: i lægmandssprog er de superhurtige . Lad os gå videre.

(Jeg ligger lidt på hashborde, der altid har O(1)kompleksitet, men læs bare videre;))

Lad os bygge et (dumt) hashbord

Vores hash-tabel har 2 enkle metoder - set(x, y)og get(x). Lad os begynde at skrive en kode:

Og lad os implementere en meget enkel, ineffektiv måde at gemme disse nøgleværdipar på og hente dem senere. Vi starter først med at gemme dem i et internt array (husk, vi kan ikke bruge, {}da vi implementerer {}- mind blown!):

Så er det simpelthen et spørgsmål om at få det rigtige element fra listen:

Vores fulde eksempel:

Vores DumbMap er fantastisk! Det fungerer lige ud af kassen, men hvordan fungerer det, når vi tilføjer en stor mængde nøgleværdipar?

Lad os prøve et simpelt benchmark. Vi vil først forsøge at finde et ikke-eksisterende element i en hash-tabel med meget få elementer, og derefter prøve det samme i et med en stor mængde elementer:

Resultaterne? Ikke så opmuntrende:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

I vores implementering er vi nødt til at løbe gennem alle elementerne indeni this.listfor at finde en med den matchende nøgle. Omkostningerne er O(n), og det er ret forfærdeligt.

Gør det hurtigt (er)

Vi er nødt til at finde en måde at undgå at løbe gennem vores liste: tid til at sætte hash tilbage i hash-tabellen .

Har du nogensinde spekuleret på, hvorfor denne datastruktur kaldes en hash- tabel? Det er fordi en hashing-funktion bruges på de taster, du indstiller og får. Vi bruger denne funktion til at gøre vores nøgle til et heltal iog gemme vores værdi i indekset ipå vores interne liste. Da adgang til et element ved et indeks fra en liste har en konstant pris ( O(1)), vil hash-tabellen også have en pris på O(1).

Lad os prøve dette:

Her bruger vi streng-hash-modulet, som simpelthen konverterer en streng til en numerisk hash. Vi bruger den til at gemme og hente elementer på indekset hash(key)på vores liste. Resultaterne?

with lots of records in the map: 0.013ms

W - O - W. Dette er hvad jeg taler om!

Vi behøver ikke at løbe gennem alle elementer på listen, og det DumbMaper super hurtigt at hente elementer fra !

Lad mig sætte det så ligetil som muligt: hashing er det, der gør hash-tabeller ekstremt effektive . Ingen magi. Intet mere. Nada. Bare en simpel, smart, genial idé.

Omkostningerne ved at vælge den rigtige hashing-funktion

Det er selvfølgelig meget vigtigt at vælge en hurtig hashing-funktion. Hvis vores hash(key)løber om et par sekunder, vil vores funktion være ret langsom uanset dens kompleksitet.

Samtidig er det meget vigtigt at sikre, at vores hashing-funktion ikke producerer mange kollisioner , da de ville være skadelige for kompleksiteten af ​​vores hash-bord.

Forvirret? Lad os se nærmere på kollisioner.

Kollisioner

Du tænker måske ” Ah, en god hashing-funktion genererer aldrig kollisioner! ”: Nå, kom tilbage til den virkelige verden og tænk igen. Google var i stand til at producere kollisioner til SHA-1-hashing-algoritmen, og det er bare et spørgsmål om tid eller beregningskraft, før en hashing-funktion knækker og returnerer den samme hash til 2 forskellige input. Antag altid, at din hashing-funktion genererer kollisioner, og implementer det rigtige forsvar mod sådanne tilfælde.

Lad os prøve at bruge en hash()funktion, der genererer mange kollisioner:

Denne funktion bruger en matrix på 10 elementer til at gemme værdier, hvilket betyder at elementer sandsynligvis vil blive erstattet - en grim fejl i vores DumbMap:

For at løse problemet kan vi simpelthen gemme flere nøgleværdipar i det samme indeks. Så lad os ændre vores hash-tabel:

Som du måske bemærker, falder vi her tilbage til vores oprindelige implementering: Gem en liste over nøgleværdipar og løb gennem hver af dem. Dette vil være ret langsomt, når der er mange kollisioner for et bestemt indeks på listen.

Lad os benchmark dette ved hjælp af vores egen hash()funktion, der genererer indekser fra 1 til 10:

with lots of records in the map: 11.919ms

og ved hjælp af hash-funktionen fra string-hash, der genererer tilfældige indekser:

with lots of records in the map: 0.014ms

Whoa! Der er omkostningerne ved at vælge den rigtige hashing-funktion - hurtigt nok til, at det ikke bremser vores udførelse alene, og godt nok til, at det ikke producerer mange kollisioner.

Generelt O (1)

Kan du huske mine ord?

Hashtables har en O(1)kompleksitet

Jeg løj: Kompleksiteten af ​​et hashbord afhænger af den hashing-funktion, du vælger. Jo flere kollisioner du genererer, jo mere har kompleksiteten tendens til O(n).

En hashing-funktion som:

function hash(key) { return 0}

ville betyde, at vores hash-tabel har en kompleksitet på O(n).

Dette er grunden til, at beregningskompleksitet generelt har tre mål: bedste, gennemsnitlige og værst tænkelige scenarier. Hashtables har en O(1)kompleksitet i bedste og gennemsnitlige scenarier, men falder til O(n)i deres værste tilfælde.

Husk: en god hashing-funktion er nøglen til en effektiv hash-tabel - ikke mere, intet mindre.

Mere om kollisioner ...

Den teknik, vi brugte til at rette DumbMapi tilfælde af kollisioner, kaldes separat kædning: vi gemmer alle nøglepar, der genererer kollisioner, på en liste og går igennem dem.

En anden populær teknik er åben adressering:

  • ved hvert indeks på vores liste gemmer vi et og kun nøgleværdipar
  • når du prøver at gemme et par ved indeks x, hvis der allerede er et nøgleværdipar, så prøv at gemme vores nye par påx + 1
  • hvis x + 1er taget, prøv x + 2og så videre ...
  • når du henter et element, skal du hash nøglen og se om elementet i den position ( x) matcher vores nøgle
  • hvis ikke, prøv at få adgang til elementet i position x + 1
  • skyl og gentag, indtil du kommer til slutningen af ​​listen, eller når du finder et tomt indeks - det betyder, at vores element ikke er i hash-tabellen

Smart, enkel, elegant og normalt meget effektiv!

Ofte stillede spørgsmål (eller TL; DR)

Har en hash-tabel hash de værdier, vi gemmer?

Nej, nøgler er hashede, så de kan omdannes til et heltal i, og både nøgler og værdier gemmes på position ii en liste.

Genererer hashfunktionerne, der bruges af hashtabeller, kollisioner?

Absolut - så hash-tabeller er implementeret med forsvarsstrategier for at undgå grimme fejl.

Bruger hash-tabeller en liste eller en sammenkædet liste internt?

Det afhænger af, begge kan fungere. I vores eksempler bruger vi JavaScript-arrayet ( []), der kan ændres dynamisk:

> a = []
> a[3] = 1
> a[ , 1 ]

Hvorfor valgte du JavaScript til eksemplerne? JS-arrays ER hash-tabeller!

For eksempel:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Jeg ved, forbandet JavaScript.

JavaScript er ”universelt” og sandsynligvis det nemmeste sprog at forstå, når man ser på en prøvekode. JS er måske ikke det bedste sprog, men jeg håber, at disse eksempler er klare nok.

Er dit eksempel en rigtig god implementering af en hash-tabel? Er det virkelig så simpelt?

Nej slet ikke.

Se på "implementering af en hash-tabel i JavaScript" af Matt Zeunert, da det giver dig lidt mere sammenhæng. Der er meget mere at lære, så jeg vil også foreslå, at du tjekker:

  • Paul Kubes kursus om hashborde
  • Implementering af vores egen Hash-tabel med separat lænkning i Java
  • Algoritmer, 4. udgave - Hash-tabeller
  • Design af et hurtigt hashbord

Til sidst…

Hash-tabeller er en meget smart idé, vi bruger regelmæssigt: uanset om du opretter en ordbog i Python, et associerende array i PHP eller et Map i JavaScript. De deler alle de samme koncepter og arbejder smukt for at lade os gemme og hente element ved hjælp af en identifikator til en (sandsynligvis) konstant pris.

Håber du nød denne artikel, og du er velkommen til at dele din feedback med mig.

En særlig tak går til Joe, som hjalp mig ved at gennemgå denne artikel.

Adios!