Hogyan lehet egy egyszerű hash táblázatot megvalósítani a JavaScript-ben

Milyen szép {}?

Lehetővé teszi az értékek kulcsonkénti tárolását és nagyon költséghatékony módon történő visszakeresését (erről O(1)bővebben később).

Ebben a bejegyzésben egy nagyon alapos hash táblázatot szeretnék megvalósítani, és áttekinteni a belső működését, hogy elmagyarázzam a számítástechnika egyik legzseniálisabb ötletét.

A probléma

Képzelje el, hogy új programozási nyelvet épít: elég egyszerű típusokkal (karakterláncok, egész számok, lebegők stb.) Kezdi, majd folytatja a nagyon alapvető adatstruktúrák megvalósítását. Először []előáll a tömb ( ), majd jön a hash tábla (más néven szótár, asszociatív tömb, hashmap, térkép és ... a lista folytatódik).

Elgondolkodott már azon, hogyan működnek? Hogy ilyen rohadtul gyorsak?

Nos, tegyük fel, hogy a JavaScript-nek nem volt {}vagy new Map(), és valósítsuk meg a sajátunkat DumbMap!

Megjegyzés a bonyolultságról

Mielőtt a labda gurulna, meg kell értenünk, hogyan működik egy funkció bonyolultsága: A Wikipédia jó frissítést nyújt a számítási bonyolultságról, de egy rövid magyarázatot adok a lustákra.

A komplexitás azt méri, hogy hány lépés szükséges a funkciónkhoz - minél kevesebb lépés van, annál gyorsabb a végrehajtás (más néven „futási idő”).

Vessünk egy pillantást a következő részletre:

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

A számítási komplexitás (ezentúl egyszerűen „komplexitás”) fnaz O(1), vagyis állandó (állandóan olvasható O(1): „ a költség egy ”): függetlenül attól, hogy milyen argumentumokat ad át, a kódot futtató platformnak csak egy műveletet kell végrehajtania (szorozzuk nbe m). Ismét, mivel ez egy művelet, a költségre hivatkozunk O(1).

A komplexitást úgy mérjük, hogy feltételezzük, hogy a függvény argumentumai nagyon nagy értékekkel bírnak. Nézzük meg ezt a példát:

function fn(n, m) { let s = 0

 for (i = 0; i < 3; i++) { s += n * m }

 return s}

Azt gondolnád, hogy összetettsége nem O(3)igaz?

Ismételten, mivel a bonyolultságot nagyon nagy érvek összefüggésében mérik, hajlamosak vagyunk konstansokat „ledobni”, és O(3)ugyanazt tekintjük O(1). Tehát ebben az esetben is azt mondanánk, hogy a bonyolult fnis O(1). Nem számít az értéke nés mértéke, végül három műveletet hajt végre - ami ismét állandó költség (ezért O(1)).

Ez a példa egy kicsit más:

function fn(n, m) { let s = []

 for (i = 0; i < n; i++) { s.push(m) }

 return s}

Amint látja, annyiszor hurkolunk, ahány értéke n, ami millió lehet. Ebben az esetben ennek a függvénynek a bonyolultságát definiáljuk O(n), mivel annyi műveletet kell végrehajtania, amennyit az egyik argumentum értéke tartalmaz.

További példák?

function fn(n, m) { let s = []

 for (i = 0; i < 2 * n; i++) { s.push(m) }

 return s}

Ez a példa ciklusokat 2 * njelent, vagyis a bonyolultságnak kell lennie O(2n). Mivel megemlítettük, hogy az állandókat „figyelmen kívül hagyják” a függvény bonyolultságának kiszámításakor, ezt a példát is a következők közé soroljuk O(n).

Még egy?

function fn(n, m) { let s = []

 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }

 return s}

Itt hurcolkodunk nés ismét hurcolkodunk a fő hurok belsejében, vagyis a bonyolultság „négyzetes” ( n * n): ha n2, akkor s.push(m)négyszer futunk , ha 3-nál 9-szer, stb.

Ebben az esetben a függvény komplexitására hivatkozunk O(n²).

Még egy utolsó példa?

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}

Ebben az esetben nincsenek egymásba ágyazott hurkok, de kétszer hurkolunk két különböző argumentumon: a bonyolultságot úgy definiáljuk O(n+m). Kristálytiszta.

Most, hogy a komplexitásról rövid ismertetést (vagy frissítést) kapott, nagyon könnyű megérteni, hogy egy bonyolult funkció O(1)sokkal jobban fog teljesíteni, mint egy O(n).

A hash asztalok O(1)összetettek: laikusok szerint szupergyorsak . Menjünk tovább.

(Olyan vagyok, hogy mindig O(1)összetett hash-táblákon fekszem , de csak olvass tovább;))

Készítsünk egy (néma) hash táblázatot

A hash-táblázatunk 2 egyszerű módszerrel rendelkezik - set(x, y)és get(x). Kezdjük el írni néhány kódot:

És valósítsunk meg egy nagyon egyszerű, nem hatékony módot ezeknek a kulcsérték-pároknak a tárolására és a későbbiekben történő visszakeresésére. Először egy belső tömbben tároljuk őket (ne felejtsük el, {}hogy a megvalósítás óta nem tudjuk használni {}- észbontva!):

Akkor egyszerűen arról van szó, hogy megszerezzük a megfelelő elemet a listából:

Teljes példánk:

A mi DumbMap csodálatos! Rögtön a dobozból működik, de hogyan fog teljesíteni, ha nagy mennyiségű kulcs-érték párot adunk hozzá?

Próbáljunk ki egy egyszerű benchmarkot. Először megpróbálunk egy nem létező elemet találni egy nagyon kevés elemet tartalmazó hash-táblában, majd megpróbáljuk ugyanazt egyben nagy elemmennyiséggel:

Az eredmények? Nem annyira biztató:

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

Megvalósításunk során át kell néznünk a benne this.listlévő összes elemet , hogy megtaláljuk a megfelelő kulcsot. Ennek költsége O(n)nagyon szörnyű.

Gyorsan (er)

Meg kell találni a módját, hogy elkerülje átkötése listánkon: ideje, hogy hash vissza a hash tábla .

Gondolkozott már azon, miért hívják ezt az adatszerkezetet hash- táblának? Ez azért van, mert egy kivonatoló funkciót használnak a beállított és megszerzett billentyűkön. Ezt a funkciót arra használjuk, hogy kulcsunkat egész számmá alakítsuk i, és értékünket ibelső listánk indexében tároljuk . Mivel egy elemnek az indexe alapján történő elérése a listáról állandó költséggel jár ( O(1)), akkor a hash tábla költsége is lesz O(1).

Próbáljuk ki ezt:

Itt a string-hash modult használjuk, amely egyszerűen átalakítja a karakterláncot numerikus kivonattá. Elemek tárolására és letöltésére használjuk hash(key)a listánk indexében . Az eredmények?

with lots of records in the map: 0.013ms

W - O - W. Erről beszélek!

Nem kell végignéznünk a lista összes elemét, és az elemek lekérése DumbMapszuper gyors!

Hadd tegyem ezt a lehető legegyszerűbben: a hash teszi a hash asztalokat rendkívül hatékonnyá . Nincs varázslat. Semmi több. Nada. Csak egy egyszerű, okos, ötletes ötlet.

A megfelelő hasító funkció kiválasztásának költsége

Természetesen a gyors hash funkció kiválasztása nagyon fontos. Ha hash(key)néhány másodperc múlva fut, a funkciónk komplexitásától függetlenül elég lassú lesz.

Ugyanakkor nagyon fontos megbizonyosodnunk arról, hogy a hash funkció nem okoz sok ütközést , mivel ezek károsak lennének a hash asztalunk összetettségére.

Zavaros? Vizsgáljuk meg közelebbről az ütközéseket.

Ütközések

Gondolhatod: „A jó hash funkció soha nem generál ütközéseket! ”: Nos, térj vissza a való világba, és gondolkodj újra. A Google képes volt ütközéseket előállítani az SHA-1 hash algoritmushoz, és csak idő, vagy számítási erő kérdése, mire egy hash függvény megreped és két különböző bemenetnél ugyanazt a kivonatot adja vissza. Mindig feltételezzük, hogy a kivonatoló funkció ütközéseket generál, és alkalmazza a megfelelő védelmet az ilyen esetek ellen.

Például próbáljunk meg olyan hash()funkciót használni , amely sok ütközést generál:

Ez a függvény 10 elemből álló tömböt használ az értékek tárolásához, ami azt jelenti, hogy az elemek valószínűleg kicserélődnek - csúnya hiba a következőkben DumbMap:

A probléma megoldása érdekében egyszerűen több kulcs-érték párot tárolhatunk ugyanabban az indexben. Tehát módosítsuk a hash-táblánkat:

Amint észreveheti, itt térünk vissza az eredeti megvalósításhoz: tároljon egy listát a kulcs-érték párokról, és mindegyiken áttekintse őket. Ez meglehetősen lassú lesz, ha sok ütközés történik a lista egy adott indexéhez.

Vizsgáljuk meg ezt a saját hash()függvényünkkel, amely 1 és 10 közötti indexeket generál:

with lots of records in the map: 11.919ms

és a hash függvény használatával string-hash, amely véletlenszerű indexeket generál:

with lots of records in the map: 0.014ms

Hú! A megfelelő hash funkció kiválasztásának költségei vannak - elég gyorsan ahhoz, hogy önmagában ne lassítsa a végrehajtásunkat, és elég jó ahhoz, hogy ne okozzon sok ütközést.

Általában O (1)

Emlékszel a szavaimra?

A hashtable-ok O(1)bonyolultak

Nos, hazudtam: a hash-tábla bonyolultsága a választott hash függvénytől függ. Minél több ütközést generál, annál inkább a bonyolultság felé hajlik O(n).

Olyan kivonatolási funkció, mint:

function hash(key) { return 0}

azt jelentené, hogy a hash tábla egy összetettsége O(n).

Éppen ezért a számítási bonyolultságnak általában három mértéke van: a legjobb, az átlagos és a legrosszabb eset. A hashtable-ok O(1)bonyolultak a legjobb és az átlagos esetekben, de O(n)a legrosszabb esetben is.

Ne feledje: a jó hash funkció a hatékony hash asztal kulcsa - se több, se kevesebb.

További információ az ütközésekről ...

Az DumbMapütközés esetén rögzített technikát külön láncolásnak nevezzük: az ütközéseket generáló kulcspárokat egy listában tároljuk, és azokon keresztül hurkolunk.

Egy másik népszerű technika a nyílt címzés:

• listánk minden egyes indexénél egy és egyetlen kulcs-érték pár tárolunk
• amikor megpróbál párokat tárolni az indexben x, ha már van kulcs-érték pár, akkor próbálja meg tárolni az új párunkat itt:x + 1
• ha x + 1elveszik, próbálkozzon x + 2és így tovább ...
• egy elem lekérésekor kivonatolja a kulcsot, és nézze meg, hogy az adott pozícióban lévő elem ( x) megegyezik-e a kulcsunkkal
• ha nem, akkor próbálja meg elérni az elemet a helyén x + 1
• öblítse le és ismételje, amíg a lista végére nem ér, vagy amikor üres indexet talál - ez azt jelenti, hogy az elemünk nem szerepel a hash táblázatban

Okos, egyszerű, elegáns és általában nagyon hatékony!

GYIK (vagy TL; DR)

Kivonatolja a hash tábla az általunk tárolt értékeket?

Nem, a kulcsokat kivonatolják, így egész számokká alakíthatók i, és mind a kulcsokat, mind az értékeket iegy lista pozíciójában tárolják .

A hash táblák által használt hash függvények ütközéseket generálnak?

Abszolút - tehát a hash táblákat védelmi stratégiákkal valósítják meg, hogy elkerüljék a csúnya hibákat.

A hash táblák belső vagy összekapcsolt listát használnak?

Attól függ, mindkettő működhet. []Példáinkban a dinamikusan átméretezhető JavaScript tömböt ( ) használjuk :

> a = []

> a[3] = 1

> a[ , 1 ]

Miért választotta a JavaScript-et a példákhoz? A JS tömbök hash táblák!

Például:

> a = [][]

> a["some"] = "thing"'thing'

> a[ some: 'thing' ]

> typeof a'object'

Átkozott JavaScript.

A JavaScript „univerzális”, és valószínűleg a legkönnyebben érthető nyelv, ha néhány mintakódot megnéz. Lehet, hogy a JS nem a legjobb nyelv, de remélem, hogy ezek a példák elég egyértelműek.

Az ön példája egy hash-tábla nagyon jó megvalósítása? Tényleg ennyire egyszerű?

Nem, egyáltalán nem.

Tekintse meg Matt Zeunert „hash-tábla megvalósítását a JavaScript-ben”, mivel ez egy kicsit több kontextust ad. Sokkal többet kell még megtanulni, ezért azt is javaslom, hogy nézze meg:

• Kube Pál tanfolyama hash asztalokról
• Saját hash-táblánk megvalósítása külön láncolással Java-ban
• Algoritmusok, 4. kiadás - Hash táblázatok
• Gyors hash asztal tervezése

A végén…

A hash táblák nagyon okos ötletek, amelyeket rendszeresen használunk: nem számít, hogy szótárat készít-e Pythonban, asszociatív tömböt a PHP-ben vagy egy térképet JavaScript-ben. Mindannyian ugyanazokat a koncepciókat osztják meg, és gyönyörűen dolgoznak azon, hogy az elemet azonosítóval tároljuk és lehívjuk (valószínűleg) állandó költséggel.

Remélem, tetszett ez a cikk, és nyugodtan ossza meg velem a visszajelzését.

Külön köszönet illeti Joe-t, aki segített nekem a cikk áttekintésével.

Adios!