Din Wikisource
Dacă adăugați frecvent valori noi la tabela hash, situația poate apărea atunci când tabela hash este complet populată și doriți să o verificați din nou. Dacă mărimea tabelului hash este mică, o depășire completă nu va cauza nici o dificultate. Pentru dimensiunea mare a tabelului hash, care necesită mult timp, iar dacă valorile vin foarte des, masa de multe ori pereheshirovat orice aloca sume imense de memorie, care nu pot fi necesare, și, prin urmare, pur și simplu au pierdut Reserve. De asemenea, într-o tabelă hash standard, poate apărea o coliziune (două valori diferite ajung în aceeași celulă). Pentru a rezolva aceste probleme și, de asemenea, pentru a nu aloca o mulțime de memorie suplimentară, aveți posibilitatea să utilizați hash extensibil.
[edit] Structura și algoritmul
Metoda hash extensibilă este aceea că o tabelă hash este reprezentată ca un director engleză și fiecare celulă va indica o găleată care are o anumită capacitate. Masa hash va avea o adâncime globală, iar fiecare dintre containere are o adâncime locală. Adâncimea globală indică câți dintre ultimii biți vor fi utilizați pentru a determina ce capacitate să introduceți valori. Și din diferența dintre adâncimea locală și adâncimea globală, se poate înțelege câte celule din catalog se referă la capacitate. Acest lucru poate fi demonstrat de formula unde este adâncimea globală, adâncimea locală și numărul celulelor care se referă. Pentru a căuta capacitatea, se utilizează un arbore digital.
Acum, luați în considerare algoritmul însuși dacă avem o anumită valoare:
- Translatăm valoarea într-o formă binară, uităm la ultimii biți și decidem la ce capacitate să trimitem valoarea.
- Dacă capacitatea are un spațiu liber, atunci vom pune valoarea acolo fără probleme, în cazul în care capacitatea la locul în care valoarea ar trebui să fie pusă este overflowed, atunci uita-te la adâncimea locală a capacitance:
- Dacă este mai mică decât adâncimea medie globală a containerului pentru a avea câteva indicii și am destul de pereheshirovat l, împărțind în același timp, în două și introduceți noile valori în două capacități care urmează să fie crescută în aceste capacități pe adâncimea locală.
- Dacă adâncimea locală este egală cu cea globală, vom crește adâncimea globală prin dublarea numărului de celule, a numărului de indicatori către capacitate și creșterea numărului ultimilor biți prin care distribuim valorile. Mai mult, adâncimea locală a capacității depășite devine mai mică și repetăm algoritmul precedent, adică am rememorat capacitatea, l-am împărțit în două containere și așa mai departe.
[edit] Exemplu
Luați în considerare algoritmul pentru un exemplu.
Să presupunem că avem un anumit director cu indicatorii noștri și dorim să adăugăm valori (vezi figura 1) unde este adâncimea globală, adâncimile locale ale containerelor și capacitatea rezervoarelor.
Prima intrare este o valoare. Imaginați-vă în formă binară :. Capătul corespunde celei de-a doua celule, așa că privim cel de-al doilea container. Există un spațiu liber în el și îl punem doar în el (vezi figura 2). Aceasta încheie lucrul cu.
Apoi intrarea are o valoare. Imaginați-vă în formă binară :. Această valoare se termină și ar trebui să meargă la primul container, dar primul container este complet umplut. Prin urmare, ne uităm la adâncimea locală a primei capacități, adică la. astfel încât după algoritmul descris mai sus, avem dubla numărul de celule de director, crește adâncimea la nivel mondial și apoi pentru a crește numărul de ultimii biți din care risipim valorile pe și pereheshirovat primul vas, împărțind-o în două, creșterea adâncimea locală și plasarea valoare pe containere noi (a se vedea figura №3). Aceasta încheie lucrul cu.
Ultimul primește o valoare. Imaginați-vă în formă binară :. Ultimii biți () corespund celui de al treilea rezervor, dar este, de asemenea complet umplut ca și în al doilea caz, dar adâncimea sa locală este mai mică decât adâncimea la nivel mondial, și, prin urmare, avem nevoie doar de pereheshirovat capacitate, împărțind-o în două, creșterea adâncimea locală și plasarea valoare pe containere noi (vezi figura 4). Aceasta încheie lucrul cu.
[edit] Utilizarea
Cel mai adesea, hașurile extensibile sunt folosite în bazele de date deoarece. Bazele de date pot fi extrem de mari, iar suprascrierea întregii baze de date va dura mult timp, în timp ce refuză accesul utilizatorilor la baza de date. Iar atunci când se folosește un hash extensibil, doar grupurile mici trebuie să depășească, ceea ce nu va încetini funcționarea bazei de date. De asemenea, hash extensibil funcționează bine într-un set de înregistrări care se schimbă dinamic într-un fișier stocat.
[edit] Vezi, de asemenea
[edit] Surse de informare
Articole similare
Trimiteți-le prietenilor: