Masă Hash

Masă Hash
O mică agendă telefonică, ca exemplu de masă hash.
Clasă	Structură de date
Structură de date	Masă Hash
Cel mai rău caz spațial	Pe)
Optim	De multe ori
Manual

În informatică, un tabel hash , în tabelul hash italian, este o structură de date utilizată pentru a potrivi o cheie dată cu o valoare dată. Este utilizat pentru implementarea structurilor de date asociative abstracte, cum ar fi Map sau Set .

Este utilizat pe scară largă în metodele de căutare numite hashing, care este o extensie a căutării indexate prin chei care tratează problemele de căutare în care cheile de căutare nu au aceste proprietăți. O căutare bazată pe hashing este complet diferită de una bazată pe comparație: în loc să se deplaseze în structura dată în funcție de rezultatul comparațiilor dintre taste, încearcă să acceseze elementele din tabel direct prin operații aritmetice care transformă cheile în adresele tabelului.

Există diferite tipuri de algoritmi de hash. După cum sa menționat, într-un tabel de hash bine dimensionat, costul mediu de căutare al fiecărui element este independent de numărul de elemente. Hashing-ul este o problemă clasică în informatică; au fost propuși, studiați temeinic și utilizați în practică mulți algoritmi. Două metode foarte populare sunt hash static și hash extensibil și liniar, metode utilizate și de programele DBMS .

Descriere

Funcționare și implementare

Primul pas pentru a crea algoritmi de căutare hash este de a determina funcția hash : datele care trebuie indexate sunt transformate de o funcție hash specifică într-un număr întreg între și $m-1$ ${\ displaystyle m-1}$ $m-1$ care este folosit ca index într-o matrice de lungime m. Asumand $U$ ${\ displaystyle U}$ $U$ atât universul cheilor cât și $T[0...m-1]$ ${\ displaystyle T [0 ... m-1]}$ $T [0 ... m-1]$ un tabel hash, o funcție hash h, stabilește o potrivire între $U$ ${\ displaystyle U}$ $U$ și pozițiile din tabelul hash, deci:

$h\colon U\rightarrow \{0,1,\dots ,m-1\}$ ${\ displaystyle h \ colon U \ rightarrow \ {0,1, \ dots, m-1 \}}$ ${\ displaystyle h \ colon U \ rightarrow \ {0,1, \ dots, m-1 \}}$

În mod ideal, cheile diferite ar trebui transformate în adrese diferite, dar din moment ce nu există o funcție hash perfectă , adică total injectivă , este posibil ca două sau mai multe chei diferite să fie convertite în aceeași adresă. Cazul în care funcția hash aplicată la două taste diferite generează aceeași adresă se numește coliziune și poate fi tratată în diferite moduri. Alegerea unei funcții hash bune este esențială pentru a minimiza coliziunile și pentru a asigura performanțe optime în orice moment. Cel mai bun rezultat se obține cu funcții pseudo-aleatorii care distribuie uniform datele de intrare.

Cu toate acestea, foarte des, o funcție hash bună poate să nu fie suficientă: de fapt, performanța unui tabel hash este, de asemenea, puternic legată de așa-numitul factor de încărcare calculat ca ${\frac {\text{cardinalità insieme di chiavi da inserire}}{\text{dimensione massima della struttura}}}$ ${\ displaystyle {\ frac {\ text {cardinalitate set de chei de inserat}} {\ text {dimensiunea maximă a structurii}}}}$ ${\ displaystyle {\ frac {\ text {cardinalitate set de chei de inserat}} {\ text {dimensiunea maximă a structurii}}}}$ și care arată cât de probabil este un element nou să se ciocnească cu unul deja prezent în tabel. Această probabilitate este de fapt mai mare decât s-ar putea crede, așa cum demonstrează paradoxul zilei de naștere . Prin urmare, este bine să mențineți factorul de încărcare cât mai scăzut posibil (de obicei, o valoare de 0,75 este cea optimă) pentru a minimiza numărul de coliziuni. Acest lucru se poate face, de exemplu, prin redimensionarea tabloului de fiecare dată când este depășit factorul de încărcare dorit.

Managementul coliziunilor

Următoarele sunt cele mai populare metode de gestionare a coliziunilor.

Deschide Hash
Hash cu concatenare (sau cu listă de depășire) : pentru fiecare celulă a tabelului hash, o Listă (de obicei o listă legată ) este potrivită în locul unui element. În acest fel se adaugă un element în coliziune la lista corespunzătoare indexului obținut.

Deschide Hash

În adresarea deschisă, toate elementele sunt stocate în tabelul hash; adică fiecare celulă a tabelului conține un element al setului dinamic sau al constantei NULL. Când căutăm un element, examinăm sistematic celulele tabelului până când găsim elementul dorit sau până ne dăm seama că elementul nu se află în tabel.

Spre deosebire de înlănțuire, nu există liste sau articole stocate în afara mesei. Deci, în adresarea deschisă, tabelul hash se poate „umple” până la punctul în care nu mai pot fi făcute intrări.

Avantajul adresării deschise constă în faptul că exclude complet indicii, calculăm secvența celulelor care trebuie examinate ( inspecție ).

Un concept important în acest sens este așa-numitul hash uniform. Reprezintă hash ideal - adică fiecare celulă din tabel este la fel de probabil să conțină un element dat.

Există diferite tehnici de inspecție, cele mai frecvent utilizate trei tehnici sunt: inspecția liniară, inspecția pătratică și hashing dublu. Cu toate acestea, niciuna dintre aceste tehnici nu îndeplinește ipoteza uniformă de hash, deoarece niciuna dintre ele nu este capabilă să genereze mai mult de $m^{2}$ ${\ displaystyle m ^ {2}}$ ${\ displaystyle m ^ {2}}$ diferite secvențe de inspecție (în loc de $m!$ ${\ displaystyle m!}$ ${\ displaystyle m!}$ , așa cum este necesară uniformizarea hașului).

Tehnici de inspecție utilizate în mod obișnuit

Inspecție liniară

$h(k,i)=(h^{1}(k)+i){\pmod {m}}$ ${\ displaystyle h (k, i) = (h ^ {1} (k) + i) {\ pmod {m}}}$ ${\ displaystyle h (k, i) = (h ^ {1} (k) + i) {\ pmod {m}}}$

Când se întâlnește o coliziune, tot ce faci este să folosești indexul următor celui care se ciocnește, până când se găsește un spațiu liber.

Inspecție quadratică

$h(k,i)=(h^{1}(k)+c_{1}i+c_{2}i^{2}){\pmod {m}}$ ${\ displaystyle h (k, i) = (h ^ {1} (k) + c_ {1} i + c_ {2} i ^ {2}) {\ pmod {m}}}$ ${\ displaystyle h (k, i) = (h ^ {1} (k) + c_ {1} i + c_ {2} i ^ {2}) {\ pmod {m}}}$

Când se întâlnește o coliziune, tot ce se face este să folosiți indicele de coliziune pătrat cu normalizare în raport cu dimensiunea tabelului indexului obținut, până când se găsește o casetă liberă.

Hashing dublu

$h(k,i)=(h_{1}(k)+ih_{2}(k)){\pmod {m}}$ ${\ displaystyle h (k, i) = (h_ {1} (k) + ih_ {2} (k)) {\ pmod {m}}}$ ${\ displaystyle h (k, i) = (h_ {1} (k) + ih_ {2} (k)) {\ pmod {m}}}$ unde, de exemplu, putem plasa $h_{1}(k)=k{\pmod {m}}$ ${\ displaystyle h_ {1} (k) = k {\ pmod {m}}}$ ${\ displaystyle h_ {1} (k) = k {\ pmod {m}}}$ Și $h_{2}(k)=1+(k{\pmod {m^{1}}})$ ${\ displaystyle h_ {2} (k) = 1 + (k {\ pmod {m ^ {1}}})}$ ${\ displaystyle h_ {2} (k) = 1 + (k {\ pmod {m ^ {1}}})}$ .

Dacă se întâlnește o coliziune la hashing o cheie, atunci rezultatul unei noi funcții hash este adăugat la indexul obținut (în general diferit de primul și care are indexul obținut anterior ca parametru) și se încearcă inserarea în noul index astfel obținut, reaplicând a doua funcție până când se găsește o celulă liberă.

Hashing static

Hash-ul static folosește conceptul de cupă, care este setul de pagini care conțin etichete de înregistrare a datelor. Dacă o pagină principală de bucket este plină, se creează o pagină de depășire. Pentru a căuta eticheta corespunzătoare cheii $k$ ${\ displaystyle k}$ $k$ ( $M=$ ${\ displaystyle M =}$ $M =$ numărul cupei) se folosește următoarea formulă hash $h(k)={\mbox{bucket}}$ ${\ displaystyle h (k) = {\ mbox {bucket}}}$ $h (k) = {\ mbox {bucket}}$ căreia îi aparține eticheta. Funcția hash $h$ ${\ displaystyle h}$ $h$ acționează asupra câmpului cheie căutare înregistrare $r$ ${\ displaystyle r}$ $r$ și trebuie să distribuie valorile peste $0,...,M-1$ ${\ displaystyle 0, ..., M-1}$ $0, ..., M-1$ ( $M.$ ${\ displaystyle M}$ $M.$ găleată). Performanța căutării depinde în mare măsură de funcție $h$ ${\ displaystyle h}$ $h$ .

Paginile de bucket primare, în hash static, sunt alocate consecutiv. Acest lucru poate duce la problema lanțurilor lungi de deversare care degradează performanța, deoarece nu avem pagini adiacente.

Exemplu de funcție Hash

$h(k)=(a*k+b){\bmod {M}}$ ${\ displaystyle h (k) = (a * k + b) {\ bmod {M}}}$ $h (k) = (a * k + b) {\ bmod {M}}$ (cu $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ constante)

Hash extensibil

Practic este o îmbunătățire a hashului static, deoarece, pe lângă introducerea găleților de preaplin, permite dublarea numărului de găleți și reorganizarea etichetelor. Singura problemă constă în reorganizarea etichetelor, deoarece aceasta necesită mult timp. Există două soluții. Primul (hash extensibil) gestionează un director de pointeri către gălețile primare, al doilea (hash liniar) vă permite să rezolvați problema fără a utiliza directoare, dar cu o familie de funcții hash. În hash extensibil vorbim despre adâncimea directorului și ne referim la numărul minim de biți care permite reprezentarea numărului de elemente conținute în director.

Hash liniar

Hash liniar, așa cum sa menționat în paragraful anterior, vă permite să rezolvați problema lanțurilor lungi de revărsare fără a utiliza directoare. Ideea de bază este de a utiliza o familie de funcții hash $h_{0},h_{1},...h_{n}$ ${\ displaystyle h_ {0}, h_ {1}, ... h_ {n}}$ $h_ {0}, h_ {1}, ... h_ {n}$ unde este $h_{i}$ ${\ displaystyle h_ {i}}$ $Salut}$ are o gamă care este jumătate din cea a $h_{i}+1$ ${\ displaystyle h_ {i} +1}$ $h_ {i} +1$ . Aceasta înseamnă că gama de $h_{1}$ ${\ displaystyle h_ {1}}$ $h_ {1}$ Și $2^{1}N$ ${\ displaystyle 2 ^ {1} N}$ $2 ^ {1} N$

Exemplu

De sine $N=32$ ${\ displaystyle N = 32}$ $N = 32$ atunci numărul minim de biți pentru reprezentarea numărului este 5. Prin urmare $h_{0}=h{\bmod {2}}^{0}N$ ${\ displaystyle h_ {0} = h {\ bmod {2}} ^ {0} N}$ $h_ {0} = h {\ bmod 2} ^ {0} N$ acesta este $h_{0}=h{\bmod {3}}2$ ${\ displaystyle h_ {0} = h {\ bmod {3}} 2}$ $h_ {0} = h {\ bmod 3} 2$ Următoarea caracteristică $h_{2}$ ${\ displaystyle h_ {2}}$ $h_ {2}$ va avea autonomie $5+1$ ${\ displaystyle 5 + 1}$ $5 + 1$ și poate reprezenta găleți de la 0 la 63. Funcția hash va fi după cum urmează $h_{1}=h{\bmod {2}}^{1}*32$ ${\ displaystyle h_ {1} = h {\ bmod {2}} ^ {1} * 32}$ $h_ {1} = h {\ bmod 2} ^ {1} * 32$

Bilanț spațiu / timp

Pe baza dimensiunii matricei în care are loc căutarea și stocarea informațiilor, există un tabel al complexității de calcul a timpului necesar pentru căutarea în sine. Cu cât este mai mult spațiu disponibil, cu atât este nevoie de mai puțin timp în cel mai rău caz.

Spaţiu	Vreme
$m=1$ ${\ displaystyle m = 1}$ $m = 1$	$O(n)$ ${\ displaystyle O (n)}$ $Pe)$
$m<n$ ${\ displaystyle m <n}$ $m <n$	$O(1+\alpha )$ ${\ displaystyle O (1+ \ alpha)}$ $O (1+ \ alfa)$
$m\gg n$ ${\ displaystyle m \ gg n}$ $m \ d n$	$O(1)$ ${\ displaystyle O (1)}$ $O (1)$

La $n$ ${\ displaystyle n}$ $n$ corespunde numărului de elemente prezente în matrice, de ex $m$ ${\ displaystyle m}$ $m$ numărul de locuri disponibile în timp ce $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ este factorul de încărcare.

Analiza costurilor scanării

Numărul de pași care trebuie efectuați pentru o scanare completă a tabelului este dat în cazul mediu de:

Rezultatul căutării	Scanare liniară	Hashing dublu / scanare quadratică
Cheie găsită	${{1} \over {2}}+{{1} \over {2-2\alpha }}$ ${\ displaystyle {{1} \ over {2}} + {{1} \ over {2-2 \ alpha}}}$ ${{1} \ over {2}} + {{1} \ over {2-2 \ alpha}}$	${{-\log _{e}(1-\alpha )\,} \over {\alpha }}$ ${\ displaystyle {{- \ log _ {e} (1- \ alpha) \,} \ over {\ alpha}}}$ ${{- \ log _ {e} (1- \ alpha) \,} \ over {\ alpha}}$
Cheia nu a fost găsită	${{1} \over {2}}+{{1} \over {(2-2\alpha )^{2}}}$ ${\ displaystyle {{1} \ over {2}} + {{1} \ over {(2-2 \ alpha) ^ {2}}}}$ ${{1} \ over {2}} + {{1} \ over {(2-2 \ alpha) ^ {{2}}}}$	${{1} \over {1-\alpha }}$ ${\ displaystyle {{1} \ over {1- \ alpha}}}$ ${{1} \ peste {1- \ alpha}}$

unde α este factorul de sarcină.

Bibliografie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi . Jackson Books, 2003, ISBN 88-256-1421-7 .

Elemente conexe

Tabel de haș distribuit

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe tabelul hash

linkuri externe

( IT ) Fabrizio Luccio , Note privind tabelele hash ( PDF ), pe didawiki.di.unipi.it . Adus la 20 iunie 2017 .

Controlul autorității	GND ( DE ) 1046573225

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

V · D · M Structuri de date
Tipuri	Colecție · Container
Abstract	Matrice asociativă ( Multimap ) · Listă · Stivă · Coadă ( Deque ) · prioritate coadă · Septembrie ( multiset · disjoint-set )
Matrice	Matrice de biți · Tampon circular · Matrice dinamică · Masă Hash · Matrice rar
Conectați	Lista asociațiilor · Lista Linked · Lista Omite · desfășură lista inlantuita · XOR listă înlănțuită
Copaci	B-tree · binar de căutare Arbore ( Arbore AA · Arbore AVL · arbore rosu-negru · binar de căutare copac echilibrat · copac evazat ) · Heap ( Heap binar · binom Heap · Heap Fibonacci ) · Merkle copac · copac SPQR · Arbore PQ · Binar copac indexat
Grafice	Diagrama binară de decizie · Digraf aciclic · Automat finic deterministic aciclic
Împărțirea copacilor informație spatiala	Copac Quadrament · M-tree · R-arbore ( R * arbore · R + copac ) · X-tree
Lista structurilor de date