Note de curs, clasele 9-10, 5 iunie 2014

From Algopedia
Jump to: navigation, search

Tabele hash

Generalități

to hash = a tăia în bucățele mici (în special mâncarea, în special carnea și cartofii). Vezi și hash browns.

De la orice structură de date dorim să suporte un set limitat de operații într-un timp cât mai bun. De exemplu, de la un heap dorim, în esență, operațiile insert și delete-min. Știm să implementăm aceasta în timp O(log n).

De la un hash table dorim, în O(1), operațiile:

  • insert(key, value): adaugă perechea (cheie, valoare) la structură;
  • delete(key): șterge din structură cheia și valoarea ei asociată;
  • search(key): returnează valoarea asociată cu cheia sau NULL dacă cheia nu există în structură.

Dincolo de operațiile de bază există diverse variante:

  • cheile pot fi unice sau nu, respectiv două perechi (cheie, valoare) pot avea aceeași cheie
  • cheile sunt numerice sau de alt tip (șiruri de caractere, în special)
  • valoarea poate fi ea însăși NULL, caz în care specificațiile operației search trebuie modificate

Multe limbaje oferă suport nativ pentru tabele hash, numite și dicționare. De exemplu, în Javascript:

var agenda = {
  'andrei': '0721.111.111',
  'barbu': '0722.222.222',
  'cosmin': '0723.333.333'
};

agenda['doru'] = '0724.444.444';

alert(agenda['barbu']);

Exemple

Un exemplu practic este o agendă telefonică. Cheile sunt nume de persoane, valorile sunt numere de telefon, iar operația cea mai frecventă este să căutăm o persoană după nume pentru a-i afla numărul de telefon. (Telefoanele moderne folosesc structuri de date mai bogate, care permit căutarea după porțiuni de nume, după inițiale, după fragmente din numărul de telefon etc.).

Un alt exemplu sunt cache-urile de orice fel. De exemplu, calculatorul vostru are un mic cache de DNS. Când vizitați prima oară un URL, sistemul face o căutare în serverele DNS pentru a afla IP-ul acelui URL. Sistemul ține acest IP în cache o vreme (de ordinul orelor). În acest cache, cheile sunt nume de domenii, iar valorile sunt IP-uri (numere pe 4 octeți, în esență).

Un exemplu mai interesant este un dicționar pe hârtie. Faptul că dicționarul este ordonat este o urmare a limitărilor noastre omenești. Nu știm cum să tipărim un dicționar, altfel decât ordonat, pentru a facilita căutarea. De fapt, ce ne interesează de obicei este sensul unui singur cuvânt, nu și al vecinilor săi.

Subliniem că ordonarea nu este o proprietate necesară pentru o tabelă hash. Operațiile next, previous, min, max se pot implementa, dar practic folosesc o structură suplimentară (un arbore echilibrat, de exemplu) cu pointeri spre și dinspre tabela hash.

Adresare directă

Când spațiul cheilor este mic, putem folosi un vector caracteristic. V[k] reține valoarea asociată cheii k, sau eventual un pointer către ea, dacă valorile pot fi mari.

Evident, operațiile insert, delete și search durează O(1) în cazul cel mai rău

Funcții hash

Când spațiul cheilor este uriaș, nu putem să alocăm un vector suficient de mare (iar dacă am putea, mare parte din el ar fi risipit). De aceea, dorim să mapăm universul cheilor, U, într-un spațiu pe care ni-l permitem. Această mapare se face cu o funcție hash:

h:U\to \lbrace 0,1,2,...,m-1\rbrace

La modul idealist, putem scrie codul:

value* t[MAX_M];

int h(key k) {
  // Returnează un număr din intervalul [0, MAX_M)
  // Vom discuta mai jos variante de funcții hash bune
}

void insert(key k, value* v) {
  t[h(k)] = v;
}

void delete(key k) {
  t[h(k)] = NULL;
}

value* search(key k) {
  return t[h(k)];    // returnează NULL dacă nu avem o valoare
}

Desigur, există un elefant în încăpere. Dacă stocăm n perechi (cheie, valoare), atunci două chei pot produce valori hash egale. Acest fenomen se numește coliziune. Este ca și cum aș căuta numărul lui Andrei, dar telefonul mi-ar indica numărul lui Barbu, pentru că din întâmplare h('Andrei') == h('Barbu'). Frecvența coliziunilor este dată de

  • calitatea funcției hash. Dacă h(k) returnează mereu 0, toate cele n perechi vor avea aceeași valoare hash.
  • raportul între n și m. Dacă n > m, oricât de bună ar fi funcția hash, vom avea coliziuni.

Cea mai simplă abordare a coliziunilor este prin înlănțuire. t[x] nu va mai reține doar o valoare, ci lista tuturor perechilor (cheie, valoare) pentru care h(cheie) = x.

value* search(key k) {
  list* l = t[h(k)];
  while (l && (l->key != k)) {
    l = l->next;
  }
  return l ? l->value : NULL;
}

Analiza complexității pentru tabele hash cu rezolvarea coliziunilor prin înlănțuire

Pentru căutare, definim factorul de încărcare \alpha =n/m. Presupunem că funcția hash este uniformă, adică toate cele m valori hash sunt echiprobabile. Atunci, în medie, fiecare din cele m sloturi va stoca \alpha chei. Complexitatea unei căutări va fi \Theta (1+\alpha ) în cazul mediu, dar poate fi O(n) în cazul cel mai defavorabil.

Inserarea presupune o căutare în prealabil: trebuie să aflăm dacă tabela conține deja cheia dată. Dacă da, îi modificăm valoarea. Dacă nu, anexăm perechea (cheie, valoare) la lista potrivită.

Și ștergerea presupune o căutare pentru a găsi perechea (cheie, valoare) de șters.

Coliziunile au un efect cumulativ nedorit. Cu cât sunt mai multe chei în același slot, cu atât timpul de căutare al tuturor acelor chei crește. Deci pentru o creștere liniară a mărimii listelor, timpul de căutare (cu succes) crește pătratic. De aceea este important ca funcția hash să fie cât mai uniformă.

  • Discuție despre statul la coadă. La un magazin, în 50% din cazuri nu este nimeni la coadă, iar în 50% din cazuri trebuie să aștept 5 minute la coadă. Totuși, percepția mea este că „tot timpul este coadă la magazin”. De ce? Pentru că, dacă nu este coadă, plec imediat, pe când dacă este coadă, am 5 minute să mă gândesc la cât de rele sunt serviciile în magazin.

Rezultă un compromis pentru alegerea lui m funcție de n. Dacă m este mare, crește consumul de memorie. Dacă m este mic, crește numărul de coliziuni.

Paradoxul zilelor de naștere: când ne așteptăm să vedem prima coliziune? Răspuns: când inserăm circa {\sqrt  {m}} chei.

  • Discuție despre URL fingerprints la Google.

Funcții hash

Cum alegem o funcție hash cât mai uniformă? Desigur, valorile hash depind de cheile inserate în tabelă, deci, de la un punct încolo, coliziunile sunt în afara controlului nostru. Dar ne putem strădui.

Prin împărțire

Dacă cheile de la intrare sunt alese uniform, putem lua

h(k)=k\,{\bmod  \,}m

Observații despre alegerea lui m:

  • Trebuie să permită folosirea informațiilor despre întregul număr k. De exemplu, m = 1024 este o alegere proastă, căci folosește doar ultimii 10 biți ai lui k.
  • La fel și m = 100.000 sau altă putere a lui 10
  • m = 99.999
  • se recomandă un număr prim cât mai departe de o putere a lui 2, cum ar fi 24019 (relativ echidistant între 16.384 și 32.768).
    • comanda Linux factor este prietenul vostru pentru a testa dacă un număr este prim.

Prin înmulțire

Metoda multiplicativă alege un număr real 0 < A < 1, apoi definește:

h(k)=\lfloor m(kA\,{\bmod  \,}1)\rfloor

Să explicăm această alegere.

  • kA\,{\bmod  \,}1 este partea de după virgulă a lui kA, deci un număr între 0 și 1.
  • prin înmulțirea cu m și luarea părții întregi, împărțim intervalul [0, 1) în m intervale de mărime 1 / m corespunzătoare celor m sloturi din hash table
  • dacă A este ales bine, atunci kA\,{\bmod  \,}1 „împrăștie” universul cheilor U în intervalul [0, 1), relativ uniform.
  • Knuth recomandă o valoare A apropiată de ({\sqrt  {5}}-1)/2=0.618...

Pentru o implementare rapidă, trebuie să evităm operațiile pe numere reale. Alegem m=2^{p} și A=s/2^{w}.

Exemplu: fie w=10, deci dorim ca s/2^{{10}}\approx ({\sqrt  {5}}-1)/2. Atunci s=632 și A=632/2^{1}0. Fie m=2^{{6}}, deci tabela noastră are 64 de sloturi. Acum fie k=123.

  • kA\,{\bmod  \,}1={\frac  {123\cdot 632}{2^{{10}}}}\,{\bmod  \,}1={\frac  {77736}{2^{{10}}}}\,{\bmod  \,}1={\frac  {77736\,{\bmod  \,}2^{{10}}}{2^{{10}}}}={\frac  {936}{2^{{10}}}}
  • h(k)=\lfloor 2^{{6}}{\frac  {936}{2^{{10}}}}\rfloor =\lfloor {\frac  {936}{2^{{4}}}}\rfloor =936\gg 4=58

Probleme

  • LRU cache
  • Se dă un arbore cu rădăcină reprezentat printr-un vector de tați. Să se găsească înălțimea arborelui.
  • Se dau V(n), S. Să se spună dacă există a, b în V pentru care a + b = S.

În limita timpului