de Alex Nadalin

Cât de frumos este {}?

Vă permite să stocați valorile după cheie și să le recuperați într-un mod foarte rentabil (O(1), mai multe despre aceasta mai târziu).

În această postare vreau să implementez un tabel hash foarte simplu și să arunc o privire asupra funcționării sale interioare pentru a explica una dintre cele mai ingenioase idei din domeniul informaticii.

Problema

Imaginați-vă că construiți un nou limbaj de programare: începeți prin a avea tipuri destul de simple (șiruri, numere întregi, flotante, …) și apoi continuați să implementați structuri de date foarte de bază. Mai întâi veniți cu matricea ([]), apoi apare tabelul hash (altfel cunoscut sub numele de dicționar, matrice asociativă, hashmap, hartă și … lista continuă).

V-ați întrebat vreodată cum funcționează? Cum sunt atât de repede?

Ei bine, să spunem că JavaScript nu a avut {} sau new Map(), și să implementăm propriul nostru DumbMap!

O notă despre complexitate

Înainte de a pune mingea în mișcare, trebuie să înțelegem cum funcționează complexitatea unei funcții: Wikipedia are o actualizare bună complexitate de calcul, dar voi adăuga o scurtă explicație pentru cei leneși.

Complexitatea măsoară câte pași sunt necesari pentru funcția noastră – cu cât sunt mai puțini pași, cu atât mai rapidă este execuția (cunoscută și sub denumirea de „timp de rulare”).

Să aruncăm o privire la următorul fragment:

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

Complexitatea de calcul (de acum pur și simplu „complexitate”) a fn este O(1), ceea ce înseamnă că este constant (puteți citi O(1) la fel de “costul este unul”): Indiferent de argumentele pe care le transmiteți, platforma care rulează acest cod trebuie să facă doar o operație (înmulțiți n în m). Din nou, deoarece este o operațiune, costul este menționat O(1).

Complexitatea se măsoară presupunând că argumentele funcției dvs. ar putea avea valori foarte mari. Să vedem acest exemplu:

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

Ai crede că complexitatea ei este O(3), dreapta?

Din nou, deoarece complexitatea este măsurată în contextul unor argumente foarte mari, avem tendința de a „scăpa” constantele și de a le lua în considerare O(3) la fel ca O(1). Deci, chiar și în acest caz, am spune că complexitatea fn este O(1). Indiferent de valoarea n și m sunteți, veți ajunge întotdeauna să faceți trei operații – care, din nou, este un cost constant (prin urmare O(1)).

Acum, acest exemplu este puțin diferit:

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

După cum vedeți, facem un looping de câte ori valoarea lui n, care ar putea fi în milioane. În acest caz, definim complexitatea acestei funcții ca fiind O(n), deoarece va trebui să faceți atâtea operații cât valoarea unuia dintre argumentele dvs.

Alte exemple?

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

Acest exemplu bucle 2 * n ori, adică complexitatea ar trebui să fie O(2n). Deoarece am menționat că constantele sunt „ignorate” atunci când se calculează complexitatea unei funcții, acest exemplu este, de asemenea, clasificat ca O(n).

Încă una?

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

Aici suntem în buclă n și buclă din nou în interiorul buclei principale, ceea ce înseamnă că complexitatea este „pătrată” (n * n): dacă n este 2, vom fugi s.push(m) De 4 ori, dacă 3 îl vom rula de 9 ori și așa mai departe.

În acest caz, complexitatea funcției este denumită O(n²).

Un ultim exemplu?

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}

În acest caz, nu avem bucle imbricate, dar buclăm de două ori pe două argumente diferite: complexitatea este definită ca O(n+m). Cristal clar.

Acum că tocmai ați primit o scurtă introducere (sau reîmprospătare) despre complexitate, este foarte ușor să înțelegeți că o funcție cu complexitate O(1) va funcționa mult mai bine decât unul cu O(n).

Mesele Hash au un O(1) complexitate: în termeni laici, sunt foarte repede. Sa trecem peste.

(Mă întind cam pe mesele de hash având mereu O(1)complexitate, dar citiți mai departe;))

Să construim un tabel hash (prost)

Tabelul nostru hash are 2 metode simple – set(x, y) și get(x). Să începem să scriem un cod:

Și să implementăm un mod foarte simplu, ineficient de a stoca aceste perechi cheie-valoare și de a le recupera mai târziu. Mai întâi începem prin a le stoca într-o matrice internă (amintiți-vă, nu putem folosi {} din moment ce implementăm {} – minte!):

Apoi, este pur și simplu o chestiune de a obține elementul potrivit din listă:

Exemplul nostru complet:

Al nostru DumbMap este uimitor! Funcționează chiar din cutie, dar cum va funcționa atunci când adăugăm o cantitate mare de perechi cheie-valoare?

Să încercăm un etalon simplu. Mai întâi vom încerca să găsim un element inexistent într-un tabel hash cu foarte puține elemente, apoi să încercăm același lucru într-unul cu o cantitate mare de elemente:

Rezultatele? Nu atât de încurajator:

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

În implementarea noastră, trebuie să parcurgem toate elementele din interior this.list pentru a găsi una cu cheia potrivită. Costul este O(n), și este destul de cumplit.

Fă-l rapid (er)

Trebuie să găsim o modalitate de a evita parcurgerea listei noastre: timpul de pus hash înapoi în masa de hash.

M-am întrebat vreodată de ce această structură de date este numită a hash masa? Asta pentru că pe tastele pe care le setați și le obțineți se folosește o funcție de hash. Vom folosi această funcție pentru a ne transforma cheia într-un număr întreg i, și stocați valoarea noastră la index i din lista noastră internă. Deoarece accesarea unui element, prin indexul său, dintr-o listă are un cost constant (O(1)), atunci tabelul hash va avea, de asemenea, un cost de O(1).

Să încercăm acest lucru:

Aici folosim șir-hash , care convertește pur și simplu un șir într-un hash numeric. Îl folosim pentru a stoca și prelua elemente la index hash(key) din lista noastră. Rezultatele?

with lots of records in the map: 0.013ms

W – O – W. Despre asta vorbesc!

Nu trebuie să parcurgem toate elementele din listă și să preluăm elemente din DumbMap este super rapid!

Permiteți-mi să pun acest lucru cât mai simplu posibil: hashing este ceea ce face ca mesele de hash să fie extrem de eficiente. Fără magie. Nimic mai mult. Nada. Doar o idee simplă, inteligentă, ingenioasă.

Costul alegerii funcției de hashing potrivite

Desigur, alegerea unei funcții de hashare rapidă este foarte importantă. Dacă a noastră hash(key) rulează în câteva secunde, funcția noastră va fi destul de lentă indiferent de complexitatea acesteia.

In acelasi timp, este foarte important să ne asigurăm că funcția noastră de hash nu produce multe coliziuni, deoarece acestea ar fi în detrimentul complexității tabelului nostru de hash.

Confuz? Să aruncăm o privire mai atentă asupra coliziunilor.

Coliziuni

Ai putea crede “Ah, o funcție bună de hash nu generează niciodată coliziuni!”: Bine, întoarce-te în lumea reală și gândește-te din nou. Google a reușit să producă coliziuni pentru algoritmul de hash SHA-1, și este doar o chestiune de timp, sau putere de calcul, înainte ca o funcție de hash să crape și să returneze același hash pentru 2 intrări diferite. Presupuneți întotdeauna că funcția dvs. de hash generează coliziuni și implementați apărarea potrivită împotriva acestor cazuri.

De exemplu, să încercăm să folosim un hash() funcție care generează o mulțime de coliziuni:

Această funcție folosește o serie de 10 elemente pentru a stoca valori, ceea ce înseamnă că este posibil ca elementele să fie înlocuite – o eroare neplăcută la noi DumbMap:

Pentru a rezolva problema, putem stoca pur și simplu mai multe perechi cheie-valoare la același index. Deci, să modificăm tabelul nostru hash:

După cum ați putea observa, aici ne întoarcem la implementarea noastră originală: stocați o listă de perechi cheie-valoare și parcurgeți fiecare dintre ele. Acest lucru va fi destul de lent atunci când există o mulțime de coliziuni pentru un anumit index al listei.

Să comparăm acest lucru folosind al nostru hash() funcție care generează indici de la 1 la 10:

with lots of records in the map: 11.919ms

și prin utilizarea funcției hash de la string-hash, care generează indexuri aleatorii:

with lots of records in the map: 0.014ms

Vai! Există costul alegerii funcției potrivite de hash – suficient de rapid încât să nu încetinească execuția noastră de la sine și suficient de bun încât să nu producă o mulțime de coliziuni.

În general O (1)

Îți amintești cuvintele mele?

Hashtables au un O(1) complexitate

Ei bine, am mințit: complexitatea unui tabel de hash depinde de funcția de hash pe care o alegeți. Cu cât generați mai multe coliziuni, cu atât tinde spre complexitate O(n).

O funcție de hash, cum ar fi:

function hash(key) {  return 0}

ar însemna că tabelul nostru hash are o complexitate de O(n).

Acesta este motivul pentru care, în general, complexitatea de calcul are trei măsuri: scenariile cele mai bune, medii și cele mai nefavorabile. Hashtables au un O(1) complexitate în scenariile de caz cele mai bune și medii, dar se încadrează în O(n)în cel mai rău scenariu al lor.

Tine minte: o funcție de hash bună este cheia unui tabel de hash eficient – nimic mai mult, nimic mai puțin.

Mai multe despre coliziuni …

Tehnica pe care am folosit-o pentru a remedia DumbMap în caz de coliziuni se numește înlănțuire separată: stocăm toate perechile de chei care generează coliziuni într-o listă și le parcurgem.

O altă tehnică populară este adresare deschisă:

  • la fiecare index din lista noastră pe care o stocăm una și una singură pereche cheie-valoare
  • când încerci să stochezi o pereche la index x, dacă există deja o pereche cheie-valoare, încercați să stocați noua noastră pereche la x + 1
  • dacă x + 1 este luat, încearcă x + 2 și așa mai departe…
  • atunci când extrageți un element, hash cheia și vedeți dacă elementul din acea poziție (x) se potrivește cu cheia noastră
  • dacă nu, încercați să accesați elementul în poziție x + 1
  • clătește și repetă până ajungi la sfârșitul listei sau când găsești un index gol – asta înseamnă că elementul nostru nu se află în tabelul hash

Inteligent, simplu, elegant și de obicei foarte eficient!

Întrebări frecvente (sau TL; DR)

Are un tabel hash valorile pe care le stocăm?

Nu, cheile sunt hashate astfel încât să poată fi transformate într-un număr întreg i, și ambele taste și valori sunt stocate în poziție i într-o listă.

Funcțiile de hash utilizate de tabelele de hash generează coliziuni?

Absolut – deci tabelele hash sunt implementate cu strategii de apărare pentru a evita bug-urile urâte.

Utilizează tabelele hash o listă sau o listă legată intern?

Depinde, ambele pot funcționa. În exemplele noastre, folosim matricea JavaScript ([]) asta poate fi redimensionate dinamic:

> a = []
> a[3] = 1
> a[ <3 empty items>, 1 ]

De ce ați ales JavaScript pentru exemple? Tablourile JS SUNT tabele hash!

De exemplu:

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

Știu, al naibii de JavaScript.

JavaScript este „universal” și probabil cel mai ușor limbaj de înțeles atunci când privești un exemplu de cod. JS s-ar putea să nu fie cel mai bun limbaj, dar sper că aceste exemple sunt suficient de clare.

Este exemplul dvs. o implementare foarte bună a unui tabel hash? Este chiar atât de simplu?

Nu deloc.

Aruncă o privire la “implementarea unui tabel hash în JavaScript” de Matt Zeunert, deoarece vă va oferi un pic mai mult context. Mai sunt multe de învățat, așa că aș sugera, de asemenea, să verificați:

În cele din urmă…

Mesele Hash sunt o idee foarte inteligentă pe care o folosim în mod regulat: indiferent dacă creați un dicționar în Python, un matrice asociativă în PHP sau a Hartă în JavaScript. Toți împărtășesc aceleași concepte și lucrează frumos pentru a ne permite să stocăm și să recuperăm elementul printr-un identificator, la un cost (cel mai probabil) constant.

Sper că ți-a plăcut acest articol și nu ezita să-mi împărtășești feedback-ul.

O mulțumire specială este pentru Joe care m-a ajutat trecând în revistă acest articol.

Adios!