Kako implementirati jednostavnu hash tablicu u JavaScript

Koliko je lijepo {}?

Omogućuje vam pohranjivanje vrijednosti po ključu i njihovo dohvaćanje na vrlo isplativ način ( O(1)o tome kasnije).

U ovom postu želim primijeniti vrlo osnovnu hash tablicu i pogledati njezin unutarnji rad kako bih objasnio jednu od najgenijalnijih ideja u računalnoj znanosti.

Problem

Zamislite da gradite novi programski jezik: započinjete s prilično jednostavnim tipovima (nizovi, cijeli brojevi, plutajući slojevi ...), a zatim nastavljate s implementacijom vrlo osnovnih struktura podataka. Prvo dođete do polja ( []), zatim dolazi hash tablica (inače poznata kao rječnik, asocijativni niz, hashmapa, karta i ... popis se nastavlja).

Jeste li se ikad zapitali kako rade? Kako su tako prokleto brzi?

Pa, recimo da JavaScript nije imao {}ili new Map(), i primijenimo svoj vlastiti DumbMap!

Napomena o složenosti

Prije nego što počnemo kotrljati loptu, moramo shvatiti kako složenost funkcije funkcionira: Wikipedia ima dobro osvježavanje računalne složenosti, ali za lijene ću dodati kratko objašnjenje.

Složenost mjeri koliko koraka zahtijeva naša funkcija - što je manje koraka, brže je izvršenje (poznato i kao "vrijeme izvođenja").

Pogledajmo sljedeći isječak:

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

Kompjutacijska složenost (od sada jednostavno "složenost") fnje O(1), što znači da je konstantna (možete čitati O(1)kao " trošak je jedan "): bez obzira na argumente koje prenesete, platforma koja pokreće ovaj kôd mora izvršiti samo jednu operaciju (pomnožiti nu m). Opet, budući da je riječ o jednoj operaciji, trošak se naziva O(1).

Složenost se mjeri pretpostavljajući da bi argumenti vaše funkcije mogli imati vrlo velike vrijednosti. Pogledajmo ovaj primjer:

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

Pomislili biste da je njegova složenost O(3), zar ne?

Opet, budući da se složenost mjeri u kontekstu vrlo velikih argumenata, skloni smo "ispuštati" konstante i razmatrati O(3)iste kao O(1). Dakle, čak i u ovom slučaju, rekli bismo da je složenost fnis O(1). Bez obzira na vrijednost ni mvrijednost, na kraju uvijek napravite tri operacije - što je opet stalni trošak (dakle O(1)).

Sad je ovaj primjer malo drugačiji:

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

Kao što vidite, petljamo onoliko puta koliko je vrijednost n, koja bi mogla biti u milijunima. U ovom slučaju, mi definiramo složenost ove funkcije kao O(n), jer ćete morati izvršiti onoliko operacija koliko je vrijednost jednog od vaših argumenata.

Ostali primjeri?

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

Ovaj primjer petlja 2 * nputa, što znači da bi složenost trebala biti O(2n). Budući da smo spomenuli da se konstante "zanemaruju" pri izračunavanju složenosti funkcije, ovaj je primjer također klasificiran kao O(n).

Još jedan?

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

Ovdje se petljamo ni ponovno petljamo unutar glavne petlje, što znači da je složenost "na kvadrat" ( n * n): ako nje 2, trčat ćemo s.push(m)4 puta, ako ćemo 3 trčati 9 puta, i tako dalje.

U ovom se slučaju složenost funkcije naziva O(n²).

Posljednji primjer?

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}

U ovom slučaju nemamo ugniježđene petlje, ali dvaput petljujemo preko dva različita argumenta: složenost se definira kao O(n+m). Kristalno čisto.

Sad kad ste upravo dobili kratki uvod (ili osvježavanje) o složenosti, vrlo je lako shvatiti da će složena funkcija O(1)raditi puno bolje od one sa O(n).

Hash tablice imaju O(1)složenost: laički rečeno, superbrze su . Idemo dalje.

(Nekako ležim na hash tablicama i uvijek imam O(1)složenost, ali samo nastavim;))

Izgradimo (nijemu) hash tablicu

Naša hash tablica ima 2 jednostavne metode - set(x, y)i get(x). Počnimo pisati neki kod:

A implementirajmo vrlo jednostavan, neučinkovit način za pohranu tih parova ključ / vrijednost i njihovo kasnije preuzimanje. Prvo započinjemo s pohranjivanjem u unutarnji niz (sjetite se, ne možemo koristiti {}jer provodimo {}- mind flow!):

Tada je jednostavno stvar dobiti pravi element s popisa:

Naš puni primjer:

Naš DumbMap je nevjerojatan! Djeluje odmah, ali kako će se izvesti kada dodamo veliku količinu parova ključ / vrijednost?

Pokušajmo s jednostavnom referentnom vrijednošću. Prvo ćemo pokušati pronaći nepostojeći element u hash tablici s vrlo malo elemenata, a zatim isto u jednom s velikom količinom elemenata:

Rezultati? Ne baš ohrabrujuće:

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

U našoj provedbi trebamo provući sve elemente iznutra this.listkako bismo pronašli jedan s odgovarajućim ključem. Trošak je O(n), i to poprilično strašan.

Neka bude brzo (er)

Moramo pronaći način da izbjegnemo petljanje po našem popisu: vrijeme je da vratimo hash natrag u hash tablicu .

Jeste li se ikad zapitali zašto se ta struktura podataka naziva hash tablicom? To je zato što se na tipkama koje postavite i dobijete koristi funkcija raspršivanja. Pomoću ove funkcije pretvorit ćemo svoj ključ u cijeli broj ii pohraniti svoju vrijednost u indeks inašeg unutarnjeg popisa. Budući da pristup elementu, putem njegovog indeksa, s popisa, ima konstantnu cijenu ( O(1)), tada će i hash tablica imati cijenu od O(1).

Isprobajmo ovo:

Ovdje koristimo niz-hash modul, koji jednostavno pretvara niz u numeričko hash. Koristimo ga za spremanje i dohvaćanje elemenata u indeksu hash(key)našeg popisa. Rezultati?

with lots of records in the map: 0.013ms

W - O - W. O tome govorim!

Ne moramo petljati kroz sve elemente na popisu, a dohvaćanje elemenata iz njih DumbMapje super brzo!

Dopustite mi da to kažem što je moguće izravnije: raspršivanje je ono što hash tablice čini izuzetno učinkovitima . Magija nikakva. Ništa više. Nada. Samo jednostavna, pametna, genijalna ideja.

Trošak odabira prave funkcije raspršivanja

Naravno, odabir funkcije brzog raspršivanja vrlo je važan. Ako hash(key)trčimo za nekoliko sekundi, naša će funkcija biti prilično spora, bez obzira na njezinu složenost.

Istodobno, vrlo je važno osigurati da naša funkcija raspršivanja ne proizvodi puno sudara , jer bi oni bili štetni za složenost naše tablice raspršivanja.

Zbunjen? Pogledajmo pobliže sudare.

Sudari

Mogli biste pomisliti „ Ah, dobra funkcija raspršivanja nikad ne stvara sudar! ”: Dobro, vratite se u stvarni svijet i razmislite ponovno. Google je uspio stvoriti sudare za algoritam raspršivanja SHA-1, a samo je pitanje vremena ili računske snage, prije nego što funkcija raspršivanja pukne i vrati isto raspršivanje za 2 različita ulaza. Uvijek pretpostavite da vaša funkcija raspršivanja generira sudare i primijenite ispravnu obranu od takvih slučajeva.

U konkretnom slučaju, pokušajmo koristiti hash()funkciju koja generira puno sudara:

Ova funkcija koristi niz od 10 elemenata za pohranu vrijednosti, što znači da će elementi vjerojatno biti zamijenjeni - gadna greška u našem DumbMap:

Da bismo riješili problem, možemo jednostavno pohraniti više parova ključ / vrijednost u isti indeks. Pa izmijenimo našu hash tablicu:

Kao što ste mogli primijetiti, ovdje se vraćamo na našu izvornu implementaciju: spremite popis parova ključ / vrijednost i prođite kroz svaki od njih. To će biti prilično sporo kad se za određeni indeks popisa dogodi puno sudara.

Uporedimo to pomoću vlastite hash()funkcije koja generira indekse od 1 do 10:

with lots of records in the map: 11.919ms

i pomoću hash funkcije from string-hash, koja generira slučajne indekse:

with lots of records in the map: 0.014ms

Joj! Tu je trošak odabira prave funkcije raspršivanja - dovoljno brzo da samostalno ne usporava naše izvršavanje i dovoljno dobro da ne izaziva puno sudara.

Općenito O (1)

Sjećate se mojih riječi?

Hashtables imaju O(1)složenost

Pa, lagao sam: složenost hash tablice ovisi o odabranoj funkciji raspršivanja. Što više sudara generirate, to je složenija težnja O(n).

Funkcija raspršivanja poput:

function hash(key) { return 0}

značilo bi da naša hash tablica ima složenost O(n).

Zbog toga, općenito, računska složenost ima tri mjere: najbolji, prosječni i najgori scenarij. Hashtables imaju O(1)složenost u najboljem i prosječnom scenariju, ali spadaju O(n)u njihov najgori scenarij.

Zapamtite: dobra funkcija raspršivanja ključ je učinkovite tablice raspršivanja - ništa više, ništa manje.

Više o sudarima ...

Tehnika koju smo koristili za popravljanje DumbMapu slučaju sudara naziva se odvojenim ulančavanjem: sve parove ključeva koji generiraju sudare pohranjujemo na popis i provlačimo se kroz njih.

Još jedna popularna tehnika je otvoreno adresiranje:

  • u svaki indeks našeg popisa pohranjujemo jedan i jedan jedini par ključ / vrijednost
  • kada pokušavate pohraniti par u indeks x, ako već postoji par ključ / vrijednost, pokušajte pohraniti naš novi par nax + 1
  • ako x + 1se uzme, pokušajte x + 2i tako dalje ...
  • kada dohvaćate element, hashirajte ključ i pogledajte odgovara li element na toj poziciji ( x) našem ključu
  • ako ne, pokušajte pristupiti elementu na položaju x + 1
  • isperite i ponavljajte dok ne dođete do kraja popisa ili kada pronađete prazan indeks - to znači da naš element nije u hash tablici

Pametno, jednostavno, elegantno i obično vrlo učinkovito!

Česta pitanja (ili TL; DR)

Hash tablica hashira li vrijednosti koje pohranjujemo?

Ne, ključevi su raspršeni kako bi se mogli pretvoriti u cijeli broj i, a i ključevi i vrijednosti pohranjeni su na mjestu ina popisu.

Generiraju li funkcije raspršivanja koje koriste hash tablice kolizije?

Apsolutno - tako se hash tablice provode sa obrambenim strategijama kako bi se izbjegle gadne bugove.

Koriste li hash tablice interno popis ili povezani popis?

Ovisi, oboje mogu raditi. U našim primjerima koristimo JavaScript niz ( []) koji se može dinamički mijenjati:

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

Zašto ste za primjere odabrali JavaScript? JS nizovi SU heš tablice!

Na primjer:

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

Znam, prokleti JavaScript.

JavaScript je "univerzalan" i vjerojatno je najlakši jezik za razumijevanje kada se gleda neki uzorak koda. JS možda nije najbolji jezik, ali nadam se da su ovi primjeri dovoljno jasni.

Je li vaš primjer stvarno dobra primjena hash tablice? Je li stvarno TAKO jednostavno?

Ne, uopće.

Pogledajte "implementaciju hash tablice u JavaScript" Matta Zeunerta, jer će vam dati malo više konteksta. Postoji još mnogo toga za naučiti, pa bih vam predložio i da provjerite:

  • Tečaj Paula Kubea o hash tablicama
  • Implementacija vlastite tablice raspršivanja s odvojenim ulančavanjem u Javi
  • Algoritmi, 4. izdanje - Hash tablice
  • Dizajniranje brze tablice raspršivanja

Na kraju…

Hash tablice vrlo su pametna ideja koju redovito koristimo: bez obzira stvarate li rječnik u Pythonu, asocijativni niz u PHP-u ili Mapu u JavaScript-u. Svi dijele iste koncepte i lijepo rade na tome da nam omoguće pohranu i dohvaćanje elementa pomoću identifikatora, uz (najvjerojatnije) konstantnu cijenu.

Nadam se da vam se svidio ovaj članak i slobodno podijelite svoje povratne informacije sa mnom.

Posebna zahvala ide Joeu koji mi je pomogao pregledavajući ovaj članak.

Adios!