Hvordan implementere en enkel hash-tabell i JavaScript

Hvor vakker er det {}?

Den lar deg lagre verdier etter nøkkel, og hente dem på en veldig kostnadseffektiv måte ( O(1), mer om dette senere).

I dette innlegget vil jeg implementere et veldig grunnleggende hashbord, og se på dets indre funksjoner for å forklare en av de mest geniale ideene innen informatikk.

Problemet

Tenk deg at du bygger et nytt programmeringsspråk: du begynner med å ha ganske enkle typer (strenger, heltall, flyter, ...) og fortsett med å implementere veldig grunnleggende datastrukturer. Først kommer du opp med matrisen ( []), deretter kommer hasjtabellen (ellers kjent som ordbok, assosiativ matrise, hashmap, kart og… listen fortsetter).

Har du noen gang lurt på hvordan de fungerer? Hvordan de er så jævla raske?

La oss si at JavaScript ikke hadde {}eller new Map(), og la oss implementere vårt helt eget DumbMap!

Et notat om kompleksitet

Før vi får ballen til å rulle, må vi forstå hvordan kompleksiteten til en funksjon fungerer: Wikipedia har en god oppdatering på beregningskompleksitet, men jeg vil legge til en kort forklaring på de late.

Kompleksitet måler hvor mange trinn som kreves av funksjonen vår - jo færre trinn, jo raskere utførelse (også kjent som "kjøretid").

La oss ta en titt på følgende tekstutdrag:

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

Beregningskompleksiteten (fra nå av bare "kompleksitet") av fner O(1), noe som betyr at den er konstant (du kan lese O(1)som " kostnaden er en "): Uansett hvilke argumenter du sender, må plattformen som kjører denne koden bare utføre en operasjon (multipliser ntil m). Igjen, siden det er en operasjon, blir kostnadene referert til som O(1).

Kompleksitet måles ved å anta at argumenter for funksjonen din kan ha veldig store verdier. La oss se på dette eksemplet:

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

Du vil tro at kompleksiteten er O(3), ikke sant?

Igjen, siden kompleksitet måles i sammenheng med veldig store argumenter, har vi en tendens til å "droppe" konstanter og vurdere O(3)det samme som O(1). Så, selv i dette tilfellet, vil vi si at kompleksiteten fner O(1). Uansett hva verdien av nog mer, ender du alltid med å utføre tre operasjoner - som igjen er en konstant kostnad (derfor O(1)).

Nå er dette eksemplet litt annerledes:

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

Som du ser, sløyfer vi så mange ganger som verdien av n, som kan være i millioner. I dette tilfellet definerer vi kompleksiteten til denne funksjonen som O(n), da du må utføre så mange operasjoner som verdien av et av argumentene dine.

Andre eksempler?

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

Disse eksemplene går 2 * nganger, noe som betyr at kompleksiteten bør være O(2n). Siden vi nevnte at konstanter “ignoreres” når vi beregner kompleksiteten til en funksjon, blir dette eksemplet også klassifisert 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øper vi over nog sløyfer igjen inne i hovedsløyfen, noe som betyr at kompleksiteten er "kvadrat" ( n * n): hvis ner 2, vil vi løpe s.push(m)4 ganger, hvis 3 vil vi kjøre den 9 ganger, og så videre.

I dette tilfellet blir kompleksets funksjon referert til som O(n²).

Et siste 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 tilfellet har vi ikke nestede sløyfer, men vi sløyfer to ganger over to forskjellige argumenter: kompleksiteten er definert som O(n+m). Krystallklart.

Nå som du nettopp har fått en kort introduksjon (eller oppdatering) om kompleksitet, er det veldig lett å forstå at en funksjon med kompleksitet O(1)kommer til å utføre mye bedre enn en med O(n).

Hash-bord har en O(1)kompleksitet: i lekmannsbetingelser er de superraske . La oss gå videre.

(Jeg ligger ganske på hasjbord som alltid har O(1)kompleksitet, men bare les videre;))

La oss bygge et (dumt) hasjbord

Hashtabellen vår har to enkle metoder - set(x, y)og get(x). La oss begynne å skrive litt kode:

Og la oss implementere en veldig enkel, ineffektiv måte å lagre disse nøkkelverdiparene og hente dem senere. Vi begynner først med å lagre dem i en intern matrise (husk, vi kan ikke bruke {}siden vi implementerer {}- mind blown!):

Så er det rett og slett et spørsmål om å hente riktig element fra listen:

Vårt fulle eksempel:

Vårt DumbMap er fantastisk! Det fungerer rett ut av esken, men hvordan vil det fungere når vi legger til en stor mengde nøkkelverdipar?

La oss prøve en enkel referanse. Vi vil først prøve å finne et ikke-eksisterende element i en hash-tabell med svært få elementer, og deretter prøve det samme i ett med en stor mengde elementer:

Resultatene? Ikke så oppmuntrende:

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

I implementeringen vår må vi gå gjennom alle elementene inni this.listfor å finne en med matchende nøkkel. Kostnaden er O(n), og det er ganske forferdelig.

Gjør det raskt (er)

Vi må finne en måte å unngå å løpe gjennom listen vår: tid til å sette hasj tilbake i hasjetabellen .

Har du noen gang lurt på hvorfor denne datastrukturen kalles hash- tabell? Det er fordi en hashing-funksjon brukes på tastene du setter og får. Vi vil bruke denne funksjonen til å gjøre nøkkelen vår til et heltall i, og lagre verdien vår i indeksen itil vår interne liste. Siden tilgang til et element, fra indeksen, fra en liste har en konstant kostnad ( O(1)), vil hash-tabellen også ha en kostnad på O(1).

La oss prøve dette:

Her bruker vi streng-hash-modulen, som bare konverterer en streng til en numerisk hash. Vi bruker den til å lagre og hente elementer i indeksen hash(key)på listen vår. Resultatene?

with lots of records in the map: 0.013ms

W - O - W. Dette er hva jeg snakker om!

Vi trenger ikke å gå gjennom alle elementene i listen, og å hente elementer fra DumbMaper super raskt!

La meg si dette så greit som mulig: hashing er det som gjør hasjbordene ekstremt effektive . Ingen magi. Ikke noe mer. Nada. Bare en enkel, smart, genial idé.

Kostnaden for å velge riktig hashing-funksjon

Å velge en hurtig hashing-funksjon er selvfølgelig veldig viktig. Hvis vi hash(key)kjører om noen få sekunder, vil funksjonen være ganske treg uavhengig av dens kompleksitet.

Samtidig er det veldig viktig å sørge for at hasjfunksjonen vår ikke gir mange kollisjoner , da de ville være skadelige for kompleksiteten til hasjbordet vårt.

Forvirret? La oss se nærmere på kollisjoner.

Kollisjoner

Du tenker kanskje “ Ah, en god hashing-funksjon genererer aldri kollisjoner! ”: Vel, kom tilbake til den virkelige verden og tenk igjen. Google var i stand til å produsere kollisjoner for SHA-1-hashingalgoritmen, og det er bare et spørsmål om tid, eller beregningskraft, før en hashing-funksjon sprekker og returnerer samme hash for 2 forskjellige innganger. Anta alltid at hashing-funksjonen din genererer kollisjoner, og implementer riktig forsvar mot slike tilfeller.

La oss prøve å bruke en hash()funksjon som genererer mange kollisjoner:

Denne funksjonen bruker en rekke med 10 elementer for å lagre verdier, noe som betyr at elementene sannsynligvis vil bli erstattet - en stygg feil i vår DumbMap:

For å løse problemet kan vi bare lagre flere nøkkelverdipar i samme indeks. Så la oss endre hasjbordet vårt:

Som du kanskje legger merke til, faller vi tilbake til vår opprinnelige implementering: lagre en liste over nøkkelverdipar og gå gjennom hver av dem. Dette kommer til å gå ganske sakte når det er mange kollisjoner for en bestemt indeks på listen.

La oss sammenligne dette med vår egen hash()funksjon som genererer indekser fra 1 til 10:

with lots of records in the map: 11.919ms

og ved å bruke hash-funksjonen fra string-hash, som genererer tilfeldige indekser:

with lots of records in the map: 0.014ms

Whoa! Det er kostnadene ved å velge riktig hashing-funksjon - raskt nok til at det ikke bremser utførelsen vår alene, og god nok til at den ikke produserer mange kollisjoner.

Vanligvis O (1)

Husker jeg ordene mine?

Hashtables har en O(1)kompleksitet

Vel, jeg løy: Kompleksiteten til et hashbord avhenger av hashing-funksjonen du velger. Jo flere kollisjoner du genererer, jo mer har kompleksiteten en tendens O(n).

En hashing-funksjon som:

function hash(key) { return 0}

vil bety at hasjbordet vårt har en kompleksitet på O(n).

Dette er grunnen til at beregningskompleksitet generelt har tre mål: beste, gjennomsnittlige og verste fall-scenarier. Hashtables har en O(1)kompleksitet i beste og gjennomsnittlige case-scenarier, men faller til O(n)i deres verste fall.

Husk: en god hashfunksjon er nøkkelen til et effektivt hashbord - ingenting mer, intet mindre.

Mer om kollisjoner ...

Teknikken vi brukte for å fikse DumbMapi tilfelle kollisjoner kalles separat kjetting: vi lagrer alle nøkkelparene som genererer kollisjoner i en liste og går gjennom dem.

En annen populær teknikk er åpen adressering:

  • ved hver indeks på listen vår lagrer vi ett og ett eneste nøkkelverdipar
  • når du prøver å lagre et par i indeksen x, hvis det allerede er et nøkkelverdipar, kan du prøve å lagre det nye paret påx + 1
  • hvis x + 1er tatt, prøv x + 2og så videre ...
  • når du henter et element, hash nøkkelen og se om elementet på den posisjonen ( x) samsvarer med nøkkelen vår
  • hvis ikke, prøv å få tilgang til elementet i posisjon x + 1
  • skyll og gjenta til du kommer til slutten av listen, eller når du finner en tom indeks - det betyr at elementet vårt ikke er i hash-tabellen

Smart, enkelt, elegant og vanligvis veldig effektivt!

Vanlige spørsmål (eller TL; DR)

Har en hash-tabell verdiene vi lagrer?

Nei, nøkler er hashert slik at de kan gjøres om til et heltall i, og både nøkler og verdier lagres på plassering ii en liste.

Genererer hashfunksjonene som brukes av hashtabeller kollisjoner?

Absolutt - så hash-tabeller er implementert med forsvarsstrategier for å unngå ekle feil.

Bruker hash-tabeller en liste eller en koblet liste internt?

Det avhenger, begge kan fungere. I eksemplene våre bruker vi JavaScript-arrayet ( []) som kan endres dynamisk:

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

Hvorfor valgte du JavaScript for eksemplene? JS arrays ER hash-tabeller!

For eksempel:

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

Jeg vet, jævla JavaScript.

JavaScript er “universelt” og sannsynligvis det enkleste språket å forstå når man ser på noen eksempler på kode. JS er kanskje ikke det beste språket, men jeg håper disse eksemplene er klare nok.

Er eksemplet ditt en veldig god implementering av et hash-bord? Er det virkelig så enkelt?

Nei ikke i det hele tatt.

Ta en titt på “implementering av en hash-tabell i JavaScript” av Matt Zeunert, da det vil gi deg litt mer sammenheng. Det er mye mer å lære, så jeg vil også foreslå at du sjekker ut:

  • Paul Kubes kurs på hasjbord
  • Implementering av vårt eget Hash-bord med separat lenking i Java
  • Algoritmer, 4. utgave - Hash-tabeller
  • Designe et raskt hasjbord

Til slutt…

Hash-tabeller er en veldig smart idé vi bruker regelmessig: uansett om du oppretter en ordbok i Python, en assosiativ matrise i PHP eller et Map i JavaScript. De deler alle de samme konseptene og jobber vakkert for å la oss lagre og hente element med en identifikator til en (mest sannsynlig) konstant pris.

Håper du likte denne artikkelen, og del gjerne tilbakemeldinger med meg.

En spesiell takk går til Joe som hjalp meg ved å lese gjennom denne artikkelen.

Adios!