Tablouri asociate.

Search:

Structuri de date abstracte.

Prezentarea structurii de date abstracte numita tablou asociat.

Cuprins:
1. Ce este un tablou asociat?.
2. Exemplu de tablouri asociate.
3. Structuri de date pentru structurile de date.
3.1 Utilizari eficiente ale tabloului asociat.
3.2 Listele asociate.
3.3 Prezentari speciale.
3.4. Multimap.
4. Suport in limbajele de programare.

1. Ce este un tablou asociat? >>>

Un tablou asociat este un tip de data abstracta compusa dintr-o colectie de termeni (chei) si o colectie de valori, unde fiecarui termen ii este asociat o valoare.Operatia de cautare a valorii asociate prin intermediul unui termen este numita indexare, si este cea mai importanta operatie efectuata intr-un tablou asociat.Legatura dintre un termen si valoarea lui este denumita uneori inregistrare sau asociere.De exemplu, daca valoarea asocitata la termenul "frankeman" este 23, astfel la locatia cu numarul 23 din tablou se va afla termenul "frankeman".Tablourile asociate sunt foarte strans legate de conceptiul matematic de functie cu domeniu finit.In consecinta, o utilizare importanta a tablourilor asocitate este in optimizare (memoizare).

Din perspectiva de utilizare a unui programator care foloseste un tablou asociat, poate fi vazut ca o generalizare a unui tablou: atat timp cat un tablou regulat inregistreaza valori de tip intreg la niste tipuri de obiecte albitrare (intregi, siruri de caractere,pinteri,valoarea logica "si",obiecte), un tablou asociat inregistreaza arbitrar tipuri de obiecte catre tipuri de obiecte arbitrare.

Operatiile care se folosesc in cadrul unui tablou asociat sunt:

*Adaugare: Asocierea unei termen nou la o noua valuare.
* Asezare: Asocierea unui termen vechi la o noua valoare.
* Stergere: Luarea valorii unui termen si stergerea lui din setul de termeni.
* Indexarea: Gasirea termenului cu valoarea cea mai mare (limita) tabloului.

2. Exemplu de tablouri asociate. >>>

Orice carte de telefon este un exemplu de tablou asociat, unde numele sunt termenii si numerele de telefon sunt valorile.Un alt exemplu poate fi un dictionar unde cuvintele sunt termenii iar definitiile sunt valorile.O baza de date este un tip de tablou asociat generalizat.

3. Structuri de date pentru tablourile asociate. >>>

Tablourile asociate sunt utile cand se foloseste indexarea (localizarea) ca fiindo operatie de baza.Din acest motiv, implementarile sunt destinate de obicei pentru a ridica eficienta care se aplica uneori la prelucrarea metodelor neeficiente de sortare prin insertie.

3.1 Utilizari eficiente. >>>
Aici sunt doua structuri de date folosite pentru a reprezenta tablourile asociative: tabelele de dispersie si arborii binari de cautare.O alta alternativa este skiplist, insa nu este o metoda des utilizata.Adventaje relative si dezavantajele includ:

* Tablourile de dispersie (hash tables) au avantajul de rapiditate medie si un timp de insertie O((1)), atat timp cat unele tipuri de arbori binari au o comportare ineficienta cu un interval de insertie O(log n) in loc de O(n).Tablourile de dispersie sunt variante folosite in sistemele in timp real, numai arborii binari pot fi necesari in sisteme de inalta securitate unde utilizatori intrusi ar putea avea acces la un plus de informatii care pot fi sustrase in cazul unei comportari ineficiente a tablourilor de dispersie, numai o structura bine pusa la punct poate inaltura acest pericol.Tablourile de dispersie sunt eficiente in tablouri de date de mari dimensiuni, unde o performanta reprezentata de functia O((1)) este importanta.
* Tablourile de dispersie pot avea un spatiu de stocare mai compact pentru termeni (elemente) cu valori mici, mai ales cand valorile sunt de forma binara.
* Aici sunt simple versiuni de arbori binari des intalniti,care sunt des intalniti in limbajele functionale.
* Construirea unui tablou de dispersie necesita o functie de dispersie protrivita pentru tipul termenilor cu care se lucreaza si care poate avea o scriere corecta dificila, atat timp cat arborii binari echilibrati necesita o aranjare integrala a termenilor.Pe de alta parte, cu tabelele de dispersie datele ar putea deveni ciclice sau partial ordonate fara sa intampina alte probleme.
* Arborii binari ordonati si listele de tip "Skip list" pastreaza ordinea termenilor -- permitand o iteratie eficienta in ordinea termenilor, sau sa contorizee numarul termenilor intr-un rang ordonat.

3.2 Listele asociate >>>
Un simplu, dar in general un ineficient tip de tablou asociat este reprezentat de o lista asociata, adesea numita prescurtat (din engleza) "alist", care cuprinde o simpla lista inlantuita ce cuprinde perechi de termeni-valori.Fiecare indexare executa o cautare liniara pentru a gasii in lista pereche a termenului cautat.
Avantajele listei asociate sunt:

* Nu necesita informatii suplimentare despre termeni, cum ar fi ordinea sau functia de dispersie.
* Pentru tablouri asocitate de dimensiuni mici, folositi in unele aplicatii, listele asociate pot lua mai putin timp de lucru si spatiu de memorie decat alte structuri de date.
* Metodele de insertie sunt facute intr-un timp exact prin inserarea unui nou termen in varful listei.

3.4 Prezentari speciale. >>>
Daca termenii tabloului sunt det acelasi tip, unul dintre acestia poate folosi structuri de date speciale pentru a imbunatati performanta.De exemplu, tablourile care contin termeni de tip intreg pot fi implementati folosind "arbori Patricia" sau tablouri de date numite "Judy",acestea putand oferii propriul spatiu de memorie ocupat pentru tablourile de dimensiuni mari.Deoarece acest tip de structura de data poate functiona bine si cu multe perechi de prefixe, acestia sunt folositi in particular in cadrul aplicatiilor unde o singura valoare este atribuita celor mai importante ranguri ai termenilor cu un prefix adaugat special pentru situatii speciale,cum ar fi de exemplu tablourile de tip "routing tables".Maparea termenilor de tip caracter poate fi ocolita prin comparatii suplimentare realizan o indexare prin folsirea arborilor binari.

4. Suport pentru limbajele de programare. >>>

Java
In Java tablourile asociate sunt implementate ca "harti", si sunt parte a colectilor ("Java CollectionFramework").Lansate prin versiunea Java J2SE 5.0 si introducerea genericelor in Java, colectiile pot avea un tip specific ca de exemplu un tabloul asociativ care cuprinde siruri de caractere poate fi specificat astfel:

Map%20carteTelefoane - new HashMap();
carteTelefoane.put("frankeman", "555-9999");
carteTelefoane.put("Jorjel Ghiontitu", "555-1999");
carteTelefoane.put("Jorjel Ghionteala", "555-9799");
carteTelefoane.put("Grigore Ghiontarel", "551-9999");

Metoda get este folosita pentru a accesa o untermen, de exemplu valoarea expresiei phoneBook.get("frankeman") este "555-9999".
Metoda foloseste o harta de dispersie pentru a cuprinde tabloul asociat, cu ajutorul constructorului clasei HashMap, oricum odata lansat codul foloseste numai metode provenite din interfata, una ar putea folosi un arborea binar perfect echilibrat prin constructorul clasei TreeMap (care implementeaza sub-interfata SortedMap, fara schimbarea definitiei variabilei sau a restului de cod, sau folosind un numar a unei structuri de date asociate care implementeaza interfata Map.

Functia de dispersie in Java provine de la metoda Object.hashCode().Initial fiecare clasa in Java sunt mostenite din clasa Object, fiecare obiect este o functie de dispersie.

Clasa Object poate sa contina deasemeni metoda equals(Object) aceasta verifica obiectul cu alt obiect.Hartile in Java se bazeaza pe obiectele care contin urmatorul contact dintre metodele hashCode si equals:

pentru metodele a si b:

* a.equals(b)==b.equals(a)
* if a.equals(b) then a.hashCode() == b,bashCode()

Pentru a mentine acest contact, o clasa care ofeara equals() trebuie de asemeni sa ofere si hashCode(),si vice versa, astfel ca acest hashCode() se bazeaza pe acealea si proprietati (sau subsetul de proprietati) ca si equals.

Un alt contact pe care aceasta harta il are cu obiectul este rezultatul metodelor hashCode() si equals() care nu schimba obiectul inserat in harta.Pentru acest motiv, este in general o buna utilizare a functiei de dispersie pe propietatile de baza ale obiectului in cauza.

C++
Si in limbajul de programare C++ exista o forma de tabloul asociat si este denumita std::map.

#include 
#include 

int main()
{
   std::map phone_book;
   phone_book["Aurel Chiuhandu"] = "555-9999";
   phone_book["Gigi Bobo"] = "555-1212";
   phone_book["Lulu Byby"] = "553-1337";
   return 0;
}

In C++, clasa std::map este o demonstratie care permite si lucrul cu termeni si valori care au tipul structurii de date diferit.Pentru a adauga o instanta in clasa map termenii trebuiesc sa fie de acelasi tip.Aceasta este valabil si pentru toate valorile.Desii clasa std::map este implementata folosind un arbore binar echilibrat,iar biblioteca SGI STL deasemeni ofera o functie std::hash_map care este un algorim benefic pentru tablourile asociate.

Inapoi la pagina principala