Se potrivește tabelul hash și gudronul din biblioteca de șabloane standard (STL). Cum este organizat masa de hash? Care structură de date va fi optimă pentru cantități mici de date?
În tabelul hash valoarea scade atunci când apelați tasta Diez. Valori ele însele sunt stocate în ordine nesortate. Deoarece tabela de dispersie utilizează o cheie pentru elementele de indexare, inserarea sau recuperarea datelor dureaza O (1) timp (ținând cont de numărul minim de coliziuni în tabele de dispersie). Tabelul hash, de asemenea, trebuie să se ocupe de potențial conflict. În acest scop, lanțul - lista legată de toate valorile și tastele sunt afișate la un anumit indice.
harta (STL) inserează perechi cheie / valoare într-un arbore binar de căutare bazat pe chei. Nu are nevoie să se ocupe de coliziuni și, din moment ce arborele este echilibrat, timpul de inserare și de căutare este O (log N).
Cum se implementează tabela de hash?
Tabelul hash este implementat ca o serie de liste legate. Când vrem să inserăm o pereche cheie / valoare, atunci, folosind funcția hash, afișăm cheia în indexul matricei. În acest caz, valoarea se încadrează în poziția indicată a listei legate.
Nu se poate spune că elementele unei liste asociate cu un indice special de matrice au aceeași cheie. Mai degrabă, funcția hashFunction (cheie) pentru aceste valori este aceeași. Prin urmare, pentru a obține valoarea corespunzătoare cheii, trebuie să stocăm în fiecare nod o cheie și o valoare.
Pentru a rezuma: tabela de distribuire este implementat ca o serie de liste legate, fiecare nod din lista conține două componente: valoarea cheii originale. Să enumere caracteristicile de implementare a tabelelor hash:
- Trebuie să utilizați o funcție hash bună pentru a vă asigura că cheile sunt distribuite corespunzător. Dacă cheile sunt slab distribuite, atunci vor exista multe coliziuni, iar viteza de găsire a elementului va scădea.
- Indiferent de cât de bun este funcția noastră de hash, vor apărea coliziuni și va trebui să le procesăm. Aceasta implică utilizarea unor liste de liste legate (sau altă metodă de rezolvare a problemei).
- Puteți implementa metode pentru a crește sau micșora dinamic dimensiunea tabelului de tip hash. De exemplu, atunci când raportul numărului de elemente la dimensiunea tabelului depășește o anumită valoare, ar trebui să măriți dimensiunea tabelului hash. Acest lucru înseamnă că va trebui să creați o tabelă de tip hash și să transferați înregistrările din acesta în cea veche. Deoarece acesta este un proces foarte laborios, trebuie să faceți tot posibilul pentru a vă asigura că dimensiunea mesei nu se schimbă prea des.
Ce poate înlocui o tabelă de tip hash atunci când lucrează cu cantități mici de date?
Puteți utiliza gudron (din STL) sau un arbore binar. Deși acest lucru va necesita O (log (n)) timp, cantitatea de date nu este mare, deci costurile de timp vor fi neglijabile.
Care este avantajul hărții?
Arborele are cel puțin un avantaj vizibil asupra mesei de tip hash. În hartă, puteți trece prin tastele ascendente sau descendente ale iteratorului și o puteți face rapid. Tabelul hash din acest plan pierde.
Trimiteți-le prietenilor: