Kuinka yksinkertainen hash-taulukko otetaan käyttöön JavaScriptissä

Kuinka kaunis on {}?

Sen avulla voit tallentaa arvot avaimen mukaan ja noutaa ne erittäin kustannustehokkaalla tavalla ( O(1)lisätietoja tästä myöhemmin).

Tässä viestissä haluan toteuttaa hyvin yksinkertaisen hash-taulukon ja tarkastella sen sisäistä toimintaa selittääkseen tietotekniikan nerokkaimpia ideoita.

Ongelma

Kuvittele, että rakennat uutta ohjelmointikieliä: aloitat hankkimalla melko yksinkertaisia ​​tyyppejä (merkkijonoja, kokonaislukuja, kelluvia jne.) Ja jatkat sitten hyvin perustietorakenteiden toteuttamista. Ensin []keksit taulukon ( ), sitten tulee hash-taulukko (joka tunnetaan myös nimellä sanakirja, assosiatiivinen taulukko, hashmap, kartta ja ... luettelo jatkuu).

Oletko koskaan miettinyt, miten ne toimivat? Kuinka he ovat niin pirun nopeita?

No, sanotaan, että Javascriptilla ei ollut {}tai new Map(), ja toteutetaan omamme DumbMap!

Huomautus monimutkaisuudesta

Ennen kuin saamme pallon liikkumaan, meidän on ymmärrettävä, kuinka funktion monimutkaisuus toimii: Wikipedialla on hyvä päivitys laskennan monimutkaisuuteen, mutta lisätään lyhyt selitys laiskaille.

Monimutkaisuus mittaa kuinka monta vaihetta toiminto vaatii - mitä vähemmän vaiheita, sitä nopeampi toteutus (tunnetaan myös nimellä "käynnissä oleva aika").

Katsotaanpa seuraava katkelma:

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

Laskennallinen monimutkaisuus (nyt yksinkertaisesti "monimutkaisuus") fnon O(1), mikä tarkoittaa, että se on vakio (voit lukea O(1)" hinta on yksi "): riippumatta siitä, mitkä argumentit välität, alustan, joka suorittaa tämän koodin, on tehtävä vain yksi operaatio (moninkertaistaa nosaksi m). Jälleen kerran, koska se on yksi operaatio, kustannuksiin viitataan O(1).

Monimutkaisuus mitataan olettaen, että funktion argumenteilla voi olla erittäin suuria arvoja. Katsotaanpa tätä esimerkkiä:

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

Luulisi sen monimutkaisuus on O(3), eikö?

Jälleen, koska monimutkaisuus mitataan erittäin suurten argumenttien yhteydessä, meillä on taipumus "pudottaa" vakioita ja pitää O(3)samaa kuin O(1). Joten jopa tässä tapauksessa sanomme, että monimutkaisuus fnon O(1). Riippumatta siitä, mikä arvo nja mitkä movat, teet aina kolme toimintoa - mikä taas on vakio kustannus (siis O(1)).

Nyt tämä esimerkki on hieman erilainen:

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

Kuten näette, silmukoitamme niin monta kertaa kuin arvo n, joka voi olla miljoonia. Tässä tapauksessa määritämme tämän funktion monimutkaisuuden O(n), koska sinun on suoritettava yhtä monta operaatiota kuin yhden argumenttisi arvo.

Muita esimerkkejä?

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

Tämä esimerkki silmukkaa 2 * nkertaa, mikä tarkoittaa monimutkaisuuden O(2n). Koska mainitsimme, että vakiot "jätetään huomiotta" laskettaessa funktion monimutkaisuutta, tämä esimerkki luokitellaan myös O(n).

Yksi vielä?

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

Tässä olemme silmukoita nja silmukoita uudelleen pääsilmukan sisällä, mikä tarkoittaa, että monimutkaisuus on "neliö" ( n * n): jos non 2, suoritamme s.push(m)4 kertaa, jos 3 suoritamme sen 9 kertaa ja niin edelleen.

Tässä tapauksessa funktion monimutkaisuuteen viitataan O(n²).

Viimeinen esimerkki?

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}

Tässä tapauksessa meillä ei ole sisäkkäisiä silmukoita, mutta silmukka kahdesti kahdella eri argumentilla: monimutkaisuus määritellään O(n+m). Kristallinkirkas.

Nyt kun olet juuri saanut lyhyen johdannon (tai päivityksen) monimutkaisuudesta, on erittäin helppo ymmärtää, että monimutkainen toiminto O(1)toimii paljon paremmin kuin yksi O(n).

Hash-pöydillä on O(1)monimutkaisuus: maallikoiden mukaan ne ovat erittäin nopeita . Siirrytään eteenpäin.

(Olen tavallaan makaamassa hash-pöydillä, aina O(1)monimutkainen, mutta lue vain;))

Rakennetaan (tyhmä) hash-taulukko

Hash-taulukossamme on 2 yksinkertaista menetelmää - set(x, y)ja get(x). Aloitetaan koodin kirjoittaminen:

Ja toteutetaan hyvin yksinkertainen, tehoton tapa tallentaa nämä avainarvoparit ja noutaa ne myöhemmin. Aloitamme ensin tallentamalla ne sisäiseen ryhmään (muista, että emme voi käyttää, {}koska toteutamme {}- mielessä puhallettu!):

Sitten on kyse vain oikean elementin saamisesta luettelosta:

Täydellinen esimerkkimme:

Meidän DumbMap on hämmästyttävää! Se toimii heti laatikosta, mutta miten se toimii, kun lisäämme suuren määrän avain-arvo-pareja?

Kokeillaan yksinkertaista vertailuarvoa. Yritämme ensin löytää ei-olemassa oleva elementti hash-taulukosta, jossa on hyvin vähän elementtejä, ja yritämme sitten samaa yhdessä suurella määrällä elementtejä:

Tulokset? Ei niin rohkaisevaa:

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

Toteutuksessamme meidän on selvitettävä kaikki sisällä olevat elementit this.list, jotta löydämme yhden vastaavalla avaimella. Kustannukset ovat O(n), ja se on melko kauheaa.

Tee se nopeasti (er)

Meidän on löydettävä tapa välttää luettelomme selaamista: aika laittaa hash takaisin hash-taulukkoon .

Oletko koskaan miettinyt, miksi tätä tietorakennetta kutsutaan hajautustaulukoksi ? Tämä johtuu siitä, että asettamis- ja saamisnäppäimissä käytetään hajautusfunktiota. Käytämme tätä toimintoa kääntääksesi avaimen kokonaislukuksi ija tallentaaksemme arvon isisäisen luettelomme hakemistoon . Koska elementin hakemisella sen indeksin perusteella luettelosta on vakiokustannukset ( O(1)), hash-taulukon kustannukset ovat myös O(1).

Kokeillaan tätä:

Tässä käytetään merkkijono-hash-moduulia, joka yksinkertaisesti muuntaa merkkijonon numeeriseksi hashiksi. Käytämme sitä elementtien tallentamiseen ja hakemiseen hash(key)luettelomme hakemistoon . Tulokset?

with lots of records in the map: 0.013ms

W - O - W. Tästä puhun!

Meidän ei tarvitse selata kaikkia luettelon elementtejä, ja elementtien noutaminen kohteesta DumbMapon erittäin nopeaa!

Haluan sanoa tämän mahdollisimman suoraviivaisesti: hajautus tekee hash-pöydistä erittäin tehokkaita . Ei taikuutta. Ei muuta. Nada. Vain yksinkertainen, älykäs, nerokas idea.

Oikean tiivistystoiminnon valitsemisen kustannukset

Tietenkin nopean hajautusfunktion valitseminen on erittäin tärkeää. Jos hash(key)juoksemme muutamassa sekunnissa, toimintamme on melko hidas sen monimutkaisuudesta riippumatta.

Samaan aikaan on erittäin tärkeää varmistaa, että hajautusfunktiomme ei tuota paljon törmäyksiä , koska ne vahingoittavat hajautuspöydän monimutkaisuutta.

Hämmentynyt? Katsotaanpa lähemmin törmäyksiä.

Törmäykset

Saatat ajatella: " Ah, hyvä hajautusfunktio ei koskaan tuota törmäyksiä! ”: No, palaa takaisin todelliseen maailmaan ja ajattele uudelleen. Google pystyi tuottamaan törmäyksiä SHA-1-hajautusalgoritmille, ja se on vain ajan tai laskentatehon kysymys, ennen kuin hajautusfunktio murtuu ja palauttaa saman hajautuksen kahdelle eri tulolle. Oletetaan aina, että hajautustoiminto tuottaa törmäyksiä, ja toteuta oikea suoja tällaisia ​​tapauksia vastaan.

Yritetään esimerkiksi käyttää hash()toimintoa, joka tuottaa paljon törmäyksiä:

Tämä toiminto käyttää 10 elementin ryhmää arvojen tallentamiseen, mikä tarkoittaa, että elementit todennäköisesti korvataan - ikävä vika DumbMap:

Ongelman ratkaisemiseksi voimme yksinkertaisesti tallentaa useita avainarvopareja samaan hakemistoon. Joten muutetaan hash-taulukkoamme:

Kuten huomaat, tässä palataan takaisin alkuperäiseen käyttöönottoon: tallenna luettelo avainarvopareista ja käy läpi ne kaikki. Tämä tulee olemaan melko hidasta, kun tietyllä luettelon indeksillä on paljon törmäyksiä.

Verrataan tätä käyttämällä omaa hash()funktiotamme, joka tuottaa indeksit 1-10:

with lots of records in the map: 11.919ms

ja käyttämällä hash-funktiota from string-hash, joka tuottaa satunnaiset indeksit:

with lots of records in the map: 0.014ms

Vau! Oikean tiivistystoiminnon valitsemisesta aiheutuu kustannuksia - riittävän nopeasti, jotta se ei hidasta suoritustamme itsestään, ja riittävän hyväksi, jotta se ei aiheuta paljon törmäyksiä.

Yleensä O (1)

Muistatko sanani?

Hashtableilla on O(1)monimutkaisuus

No, valehtelin: hash-taulukon monimutkaisuus riippuu valitsemastasi hajautustoiminnosta. Mitä enemmän törmäyksiä syntyy, sitä enemmän monimutkaisuus pyrkii kohti O(n).

Hajautustoiminto, kuten:

function hash(key) { return 0}

tarkoittaisi, että hash-taulukon monimutkaisuus on O(n).

Siksi laskennallisella monimutkaisuudella on yleensä kolme mittaria: parhaat, keskimääräiset ja pahimmat tapaukset. Hashtabeleilla on O(1)monimutkaisuus parhaimmissa ja keskimääräisissä tilanteissa, mutta ne kuuluvat O(n)pahimpaan tapaukseen.

Muista: hyvä hajautusfunktio on avain tehokkaaseen hajautustaulukkoon - ei muuta, ei vähempää.

Lisää törmäyksistä ...

Tekniikkaa, jota käytimme korjaamaan DumbMaptörmäystilanteessa, kutsutaan erilliseksi ketjutukseksi: tallennamme kaikki avaimet, jotka synnyttävät törmäyksiä, luetteloon ja silmukoidaan niiden läpi.

Toinen suosittu tekniikka on avoin osoite:

  • luettelomme jokaiseen hakemistoon tallennamme yhden ja yhden ainoan avain-arvo-parin
  • kun yrität tallentaa paria hakemistoon x, jos jo on avainarvopari, yritä tallentaa uusi pari osoitteeseenx + 1
  • jos x + 1otetaan, kokeile x + 2ja niin edelleen ...
  • haettaessa elementtiä, hajauta avain ja tarkista, vastaako tässä paikassa oleva elementti ( x) avainta
  • jos ei, yritä käyttää elementtiä paikassa x + 1
  • huuhtele ja toista, kunnes pääset luettelon loppuun tai kun löydät tyhjän hakemiston - se tarkoittaa, että elementtimme ei ole hash-taulukossa

Älykäs, yksinkertainen, tyylikäs ja yleensä erittäin tehokas!

UKK (tai TL; DR)

Rajaa hajautustaulukko tallentamamme arvot?

Ei, avaimet on tiivistetty, jotta niistä voidaan tehdä kokonaisluku i, ja sekä näppäimet että arvot tallennetaan iluettelon kohtaan.

Luovatko hajautustaulukoiden käyttämät hajautusfunktiot törmäyksiä?

Ehdottomasti - joten hash-taulukot toteutetaan puolustusstrategioilla, jotta vältetään ikävät virheet.

Käyttääkö hash-taulukko sisäisesti luetteloa vai linkitettyä luetteloa?

Se riippuu siitä, voivatko molemmat toimia. Esimerkeissämme käytämme JavaScript-taulukkoa ( []), jonka kokoa voidaan muuttaa dynaamisesti:

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

Miksi valitsit esimerkeiksi JavaScriptin? JS-taulukot OVAT hash-taulukoita!

Esimerkiksi:

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

Tiedän, hitto JavaScript.

JavaScript on “universaali” ja luultavasti helpoin ymmärrettävä kieli, kun tarkastellaan esimerkkikoodia. JS ei ehkä ole paras kieli, mutta toivon näiden esimerkkien olevan riittävän selkeitä.

Onko esimerkkisi todella hyvä hash-taulukon toteutus? Onko se todella niin yksinkertaista?

Ei, ei lainkaan.

Tutustu Matt Zeunertin "hash-taulukon käyttöönottoon JavaScriptissä", koska se antaa sinulle hieman enemmän kontekstia. Opittavaa on paljon enemmän, joten ehdotan myös, että tutustut:

  • Paul Kuben kurssi hash-pöydille
  • Oman hash-taulukon toteuttaminen erillisellä ketjuttamisella Java-sovelluksessa
  • Algoritmit, 4. painos - Hash-taulukot
  • Nopean hash-pöydän suunnittelu

Lopussa…

Hash-taulukot ovat erittäin fiksu idea, jota käytämme säännöllisesti: riippumatta siitä, luotko sanakirjan Pythonissa, assosiatiivisen taulukon PHP: ssä vai Mapin JavaScript-muodossa. Heillä kaikilla on samat käsitteet ja he työskentelevät kauniisti, jotta voimme tallentaa ja hakea elementin tunnisteella (todennäköisesti) vakiokustannuksilla.

Toivottavasti pidit tästä artikkelista ja voit vapaasti jakaa palautetta kanssani.

Erityiset kiitokset Joelle, joka auttoi minua tarkastelemalla tätä artikkelia.

Adios!