Kaip įdiegti paprastą maišos lentelę „JavaScript“

Kaip gražu {}?

Tai leidžia jums išsaugoti reikšmes pagal raktą ir jas gauti labai ekonomiškai efektyviu būdu ( O(1)daugiau apie tai rasite vėliau).

Šiame įraše noriu įdiegti labai paprastą maišos lentelę ir pažvelgti į jos vidinį veikimą, kad paaiškinčiau vieną išradingiausių informatikos idėjų.

Problema

Įsivaizduokite, kad kuriate naują programavimo kalbą: pirmiausia turite turėti gana paprastus tipus (eilutes, sveikus skaičius, plūdurius ir kt.), Tada pradėsite diegti labai pagrindines duomenų struktūras. Pirmiausia sugalvojate masyvą ( []), tada ateina maišos lentelė (kitaip vadinama žodynu, asociatyviuoju masyvu, maišos žemėlapiu, žemėlapiu ir ... sąrašas tęsiasi).

Ar kada susimąstėte, kaip jie veikia? Kaip jie taip velniškai greitai?

Na, tarkime, kad „JavaScript“ neturėjo {}arba new Map(), ir įgyvendinkime savo DumbMap!

Pastaba apie sudėtingumą

Prieš pradėdami rutulį, turime suprasti, kaip veikia funkcija: Vikipedija gerai atnaujina skaičiavimo sudėtingumą, bet aš pridėsiu trumpą paaiškinimą tingiems.

Sudėtingumas matuoja, kiek žingsnių reikalauja mūsų funkcija - kuo mažiau žingsnių, tuo greitesnis vykdymas (dar vadinamas „važiavimo laiku“).

Pažvelkime į šį fragmentą:

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

Skaičiavimo sudėtingumas (nuo šiol tiesiog „sudėtingumas“) fnyra O(1), tai reiškia, kad jis yra pastovus (galite skaityti O(1)kaip „ kaina yra viena “): nesvarbu, kokius argumentus perduotumėte, platforma, vykdanti šį kodą, turi atlikti tik vieną operaciją (padauginti nį m). Vėlgi, kadangi tai viena operacija, išlaidos nurodomos O(1).

Sudėtingumas matuojamas darant prielaidą, kad jūsų funkcijos argumentai gali turėti labai dideles reikšmes. Pažvelkime į šį pavyzdį:

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

Jūs manote, kad jo sudėtingumas yra O(3), tiesa?

Vėlgi, kadangi sudėtingumas vertinamas labai didelių argumentų kontekste, mes linkę „numesti“ konstantas ir laikyti O(3)tą patį kaip ir O(1). Taigi, net ir šiuo atveju sakytume, kad fnyra O(1). Nesvarbu, kokia yra vertė nir kokia myra, jūs visada atliekate tris operacijas, kurios vėlgi yra pastovios išlaidos (todėl O(1)).

Dabar šis pavyzdys yra šiek tiek kitoks:

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

Kaip matote, mes skaičiuojame tiek kartų, kiek jų vertė ngali siekti milijonus. Šiuo atveju mes apibrėžiame šios funkcijos sudėtingumą kaip O(n), nes jums reikės atlikti tiek operacijų, kiek vieno jūsų argumento vertė.

Kiti pavyzdžiai?

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

Šie pavyzdžiai kartoja 2 * nlaiką, o tai reiškia, kad sudėtingumas turėtų būti O(2n). Kadangi mes minėjome, kad skaičiuojant funkcijos sudėtingumą „ignoruojamos“ konstantos, šis pavyzdys taip pat klasifikuojamas kaip O(n).

Dar vieną?

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

Čia mes persijungiame nir vėl grįžtame į pagrindinę kilpą, o tai reiškia, kad sudėtingumas yra „kvadratas“ ( n * n): jei nyra 2, bėgsime s.push(m)4 kartus, jei 3 - 9 kartus ir t. T.

Šiuo atveju nurodomas funkcijos sudėtingumas O(n²).

Paskutinis pavyzdys?

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}

Šiuo atveju mes neturime įdėtų kilpų, tačiau du kartus perjungiame du skirtingus argumentus: sudėtingumas apibrėžiamas kaip O(n+m). Švarus.

Dabar, kai ką tik gavote trumpą įvadą (ar atnaujinimą) apie sudėtingumą, labai lengva suprasti, kad sudėtingą funkciją atliksite O(1)daug geriau nei su ja O(n).

„Hash“ lentelės yra O(1)sudėtingos: nespecialistiškai tariant, jos yra itin greitos . Eikime toliau.

(Aš kažkaip guliu ant maišos lentelių, visada O(1)sudėtingas, bet tiesiog skaitykite toliau;))

Sukursime (nebylų) maišos lentelę

Mūsų maišos lentelėje yra 2 paprasti metodai - set(x, y)ir get(x). Pradėkime rašyti kodą:

Įgyvendinkime labai paprastą, neefektyvų būdą šioms raktų ir reikšmių poroms išsaugoti ir vėliau jas gauti. Pirmiausia pradedame juos saugoti vidiniame masyve (atminkite, kad negalime naudoti, {}nes diegiame {}- protas prapūstas!):

Tada paprasčiausiai reikia gauti tinkamą elementą iš sąrašo:

Visas mūsų pavyzdys:

Mūsų DumbMap nuostabu! Tai veikia iš karto, bet kaip ji veiks, kai pridėsime daug raktų ir vertės porų?

Išbandykime paprastą etaloną. Pirmiausia bandysime rasti neegzistuojantį elementą maišos lentelėje, kurioje yra labai nedaug elementų, o tada bandysime tą patį viename su dideliu elementų kiekiu:

Rezultatai? Ne taip padrąsina:

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

Įgyvendindami turime perskaityti visus viduje this.listesančius elementus , kad rastume vieną su atitikimo raktu. Kaina yra O(n)ir gana baisi.

Padaryk tai greitai (er)

Turime rasti būdą, kaip išvengti perrašymo per sąrašą: laikas sugrąžinti maišos atgal į maišos lentelę .

Ar kada susimąstėte, kodėl ši duomenų struktūra vadinama maišos lentele? Taip yra todėl, kad jūsų nustatytuose ir gautuose klavišuose naudojama maišos funkcija. Mes naudosime šią funkciją norėdami paversti raktą į sveiką skaičių iir išsaugoti savo vertę isavo vidinio sąrašo rodyklėje . Kadangi prieiga prie elemento pagal jo indeksą iš sąrašo kainuoja pastoviai ( O(1)), maišos lentelė taip pat turės kainą O(1).

Išbandykime tai:

Čia mes naudojame eilutės maišos modulį, kuris tiesiog paverčia eilutę skaitmenine maiša. Mes naudojame jį kaupti ir gauti elementus hash(key)savo sąrašo rodyklėje . Rezultatai?

with lots of records in the map: 0.013ms

W - O - W. Apie tai kalbu!

Mums nereikia perskaityti visų sąrašo elementų, o elementus iš jų gauti DumbMapyra labai greita!

Leiskite man tai pasakyti kuo paprasčiau: maišos lentelės yra itin efektyvios maišant . Jokios magijos. Nieko daugiau. Nada. Tiesiog paprasta, sumani, geniali idėja.

Tinkamos maišos funkcijos parinkimo kaina

Žinoma, labai svarbu pasirinkti greitą maišos funkciją. Jei mūsų darbas hash(key)vyks per kelias sekundes, mūsų funkcija bus gana lėta, nepaisant jos sudėtingumo.

Tuo pačiu metu labai svarbu įsitikinti, kad mūsų maišos funkcija nesudaro daug susidūrimų , nes tai pakenktų mūsų maišos stalo sudėtingumui.

Sumišęs? Pažvelkime atidžiau į susidūrimus.

Susidūrimai

Galima pagalvoti: „ Ak, gera maišos funkcija niekada nesudaro susidūrimų! “: Na, grįžk į realų pasaulį ir pagalvok dar kartą. „Google“ galėjo susidurti su SHA-1 maišos algoritmo susidūrimais, ir tai tik laiko arba skaičiavimo galios klausimas, kol maišos funkcija įtrūksta ir grąžina tą patį maišos 2 skirtingiems įėjimams. Visada manykite, kad jūsų maišos funkcija sukelia susidūrimus, ir tinkamai apsaugokite nuo tokių atvejų.

Šiuo atveju pabandykime naudoti hash()funkciją, kuri sukuria daug susidūrimų:

Ši funkcija naudoja 10 elementų masyvą reikšmėms saugoti, o tai reiškia, kad elementai greičiausiai bus pakeisti - bjauri mūsų klaida DumbMap:

Norėdami išspręsti problemą, mes galime paprasčiausiai saugoti kelias raktų ir verčių poras tame pačiame indekse. Taigi pataisykime savo maišos lentelę:

Kaip pastebėjote, čia grįžtame prie pirminio diegimo: išsaugokite raktų ir verčių porų sąrašą ir peržiūrėkite kiekvieną iš jų. Tai bus gana lėta, kai susiduriama su tam tikru sąrašo rodikliu.

Palyginkime tai naudodami savo hash()funkciją, kuri generuoja indeksus nuo 1 iki 10:

with lots of records in the map: 11.919ms

ir naudojant maišos funkciją iš string-hash, kuri generuoja atsitiktinius indeksus:

with lots of records in the map: 0.014ms

Oi! Yra tinkamos maišos funkcijos parinkimo kaina - pakankamai greita, kad ji savaime nesumažintų mūsų vykdymo, ir pakankamai gera, kad nesudarytų daug susidūrimų.

Paprastai O (1)

Prisimeni mano žodžius?

„Hashtables“ yra O(1)sudėtingas

Na, aš melavau: maišos lentelės sudėtingumas priklauso nuo jūsų pasirinktos maišos funkcijos. Kuo daugiau susidūrimų generuojate, tuo labiau linkę į sudėtingumą O(n).

Maišymo funkcija, tokia kaip:

function hash(key) { return 0}

reikštų, kad mūsų maišos lentelė yra sudėtinga O(n).

Štai kodėl apskritai skaičiavimo sudėtingumą sudaro trys matai: geriausi, vidutiniai ir blogiausi atvejai. O(1)Geriausio ir vidutinio atvejo scenarijai sudėtingi, tačiau O(n)blogiausiu atveju jie yra sudėtingi .

Atminkite: gera maišos funkcija yra raktas į efektyvią maišos lentelę - nei daugiau, nei mažiau.

Daugiau apie susidūrimus ...

Metodas, kurį nustatėme DumbMapsusidūrimo atveju, vadinama atskira grandine: visas raktų poras, kurios generuoja susidūrimus, išsaugome sąraše ir per juos pereiname.

Kita populiari technika yra atviras adresavimas:

  • kiekviename mūsų sąrašo rodyklėje saugome vieną ir vieną vienintelę raktų ir verčių porą
  • bandydami laikyti porą prie indekso x, jei jau yra raktų ir verčių pora, pabandykite laikyti mūsų naują porąx + 1
  • jei x + 1yra paimtas, pabandykite x + 2ir pan ...
  • atsiimdami elementą, maiškite raktą ir patikrinkite, ar elementas toje vietoje ( x) atitinka mūsų raktą
  • jei ne, pabandykite pasiekti elementą toje vietoje x + 1
  • praskalaukite ir pakartokite, kol pateksite į sąrašo pabaigą arba rasite tuščią rodyklę - tai reiškia, kad mūsų elemento nėra maišos lentelėje

Protingas, paprastas, elegantiškas ir paprastai labai efektyvus!

DUK (arba TL; DR)

Ar maišos lentelėje yra maišos, kurias saugome?

Ne, raktai yra maišomi, kad juos būtų galima paversti sveikaisiais skaičiais i, ir raktai, ir reikšmės saugomi isąrašo vietoje.

Ar maišos lentelių naudojamos maišos funkcijos sukelia susidūrimus?

Visiškai - todėl maišos lentelės yra įgyvendinamos su gynybos strategijomis, kad būtų išvengta nemalonių klaidų.

Ar maišos lentelės naudoja sąrašą ar susietą sąrašą viduje?

Tai priklauso, abu gali dirbti. Pavyzdžiuose naudojame „JavaScript“ masyvą ( []), kurio dydį galima dinamiškai pakeisti:

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

Kodėl pavyzdžiams pasirinkote „JavaScript“? JS masyvai ARE maišos lentelės!

Pavyzdžiui:

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

Aš žinau, prakeiktas „JavaScript“.

„JavaScript“ yra „universali“ ir tikriausiai lengviausiai suprantama kalba, žiūrint į kodo pavyzdį. JS galbūt nėra geriausia kalba, bet tikiuosi, kad šie pavyzdžiai yra pakankamai aiškūs.

Ar jūsų pavyzdys yra tikrai geras maišos lentelės įgyvendinimas? Ar tikrai TAI paprasta?

Ne, visiškai ne.

Pažvelkite į Matto Zeunerto „maišos lentelės įdiegimą„ JavaScript ““, nes tai suteiks jums šiek tiek daugiau konteksto. Yra dar daug ko išmokti, todėl taip pat siūlyčiau patikrinti:

  • Paulo Kube kursas apie maišos lenteles
  • Savo „Hash“ lentelės įdiegimas naudojant atskirą grandinę „Java“
  • Algoritmai, 4-asis leidimas - „Hash“ lentelės
  • Greito maišos stalo projektavimas

Pabaigoje…

„Hash“ lentelės yra labai protinga idėja, kurią naudojame reguliariai: nesvarbu, ar kuriate žodyną „Python“, ar asociatyvų masyvą „PHP“, ar „Map“ - „JavaScript“. Jie visi turi tas pačias sąvokas ir puikiai dirba, kad galėtume išsaugoti ir gauti elementą pagal identifikatorių (greičiausiai) pastoviomis sąnaudomis.

Tikiuosi, kad jums patiko šis straipsnis, ir nedvejodami pasidalykite savo atsiliepimais su manimi.

Ypatingas ačiū Joe, kuris man padėjo peržiūrėdamas šį straipsnį.

Adios!