Structura de date Dicționar sugerează stocarea de perechi de tip cheie-valoare, și oferă o căutare rapidă cu ajutorul cheilor. În limbajul comun, asta înseamnă că în loc de elemente care primesc un index numeric, ca și în cazul array-ului, ele primesc un tip specific drept cheie (asta este semnificația literei K în conceptul Dictionary<K, T> (de la englezescul key – cheie); T semnifică tipul de valori stocate în dicționar) pentru accesarea elementelor. De cele mai multe ori, această cheie este un șir de caractere – iar acest lucru ne permite să oferim nume elementelor noastre. Așadar, în loc să accesăm cel de-al cincilea element al unui array utilizând chifra 4 ca și „cheie” (amintiți-vă, array-urile au baza indexurilor la 0, nu 1!), putem accesa al cincilea element prin valoarea pe care am dat-o cheii sale, care ar putea fi un cuvânt, de exemplu. Ca într-un dicționar real, căutăm un anumit cuvânt (care este „cheia”), iar când îl găsim, citim definiția acelui cuvânt (care este „valoarea” stocată pentru acel element). La fel ca într-un dicționar real, nu ni se permite să avem mai mult de un element cu aceeași cheie (într-un dicționar real, un cuvânt nu este definit de două ori).
Dicționarul, împreună cu lista, sunt cele mai importante și utilizate structuri de date (cu excepția poate a array-urilor). Implementarea cu o tabelă hash (clasa Dictionary<D, T>) are o adăugare , căutare și eliminare a elementelor foarte rapidă – complexitate constantă în medie. Operațiea acces prin index nu este disponibilă, deoarece elementele din tabelul hash nu au o ordine, adică au o ordine aproape aleatorie. Dictionary<K, T> păstrează elementele într-un array intern și pune fiecare element la poziția calculată de funcția hash. Astfel, array-ul este parțial umplut – în unele celule există o valoare, altele sunt goale. Dacă mai mult de un element trebuie plasat într-o singură celulă, elementele sunt stocate într-o listă asociată. Acest proces se numește înlănțuire. Aceasta este una dintre cele câteva modalități de a rezolva problema coliziunii. Când numărul de elemente din dicționar depășește 75% din capacitatea sa, dimensiunea sa este dublată și toate elementele ocupă noi poziții. Această operație are o complexitate liniară, dar este executată atât de rar, încât complexitatea amortizată rămâne o constantă. Tabelul Hash are o particularitate: dacă alegem o funcție de hash ineficientă, care provoacă multe coliziuni, operațiile de bază pot deveni foarte ineficiente și pot ajunge la complexitate liniară. Cu toate acestea, în practică acest lucru se întâmplă greu. Hash-table este considerată a fi cea mai rapidă structură de date, care oferă adăugarea și căutarea după cheie. Tabelul Hash din .NET Framework permite fiecărei chei să fie pusă o singură dată. Dacă adăugăm două elemente cu aceeași cheie în mod consecutiv, ultima va înlocui prima și în cele din urmă vom pierde un element. Această caracteristică importantă trebuie luată în considerare.
Din când în când, o cheie va trebui să păstreze mai multe valori. Această funcție nu este acceptată în mod standard, dar putem stoca valorile care se potrivesc cu această cheie într-o listă, ca o secvență de elemente. De exemplu, dacă avem nevoie de un tabel de tip hash Dictionary<int, string> în care acumulăm perechi {integer, string} cu duplicate, putem folosi Dictionary<int, List <string>>. Unele biblioteci externe conțin o structură de date gata disponibilă numită MultiDictionary<K, V>. Tabelul Hash este recomandat pentru a fi folosit de fiecare dată când avem nevoie de adăugare rapidă și de căutare rapidă pe chei. De exemplu, dacă trebuie să numărăm de câte ori fiecare cuvânt este întâlnit într-un set de cuvinte dintr-un fișier text, putem folosi Dictionary<string, int> – cheia va fi un anume cuvânt, valoarea – de câte ori avem a fost găsit. Utilizați un dicționar atunci când doriți să adăugați și să căutați după chei.
Deoarece dicționarele sunt tipuri generice, tipurile cheilor și valorilor trebuie să fie specificate la crearea unui dicționar, de exemplu:
|
1 |
Dictionary<string, int> dictionar = new Dictionary<string, int>(); |
Linia de cod de mai sus va crea un nou dicționar în care cheile vor fi șiruri de caractere (string), iar valorile memorate vor fi numere întregi (integer).
Adăugarea datelor într-un dicționar este similară cu adăugarea de valori într-o listă, cu excepția faptului că este nevoie de un argument cheie și valoare:
|
1 |
dictionar.Add("unu", 1); |
Odată ce datele sunt stocate în interiorul unui dicționar C#, utilizați valorile cheie ca indici pentru a obține valori. Contextual, o listă folosește numere drept chei (indici) pentru a obține valorile sale, în timp ce un dicționar utilizează cuvinte definite:
|
1 |
int unu = dictionar["unu"]; |
Traversarea unui dicționar (trecerea prin fiecare element) este dificilă, deoarece cheile pot fi orice în cadrul tipului său de date. Singura modalitate de a accesa toate valorile dintr-un dicționar este să cunoașteți toate cheile. Acesta este momentul în care proprietatea Keys ne poate fi de ajutor, deoarece ea deține o colecție a cheilor adăugate. Iată un exemplu de iterare printr-un dicționar C#:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//declara un nou dictionar cu chei de tip string si valori de tip int Dictionary<string, int> dictionar = new Dictionary<string, int>(); //adauga doua elemente dictionar.Add("unu", 1); dictionar.Add("doi", 2); //declara o noua lista de tip string prin convertirea proprietatii Keys a dictionarului List<string> chei = new List<string>(dictionar.Keys); //cicleaza prin noua lista for (int i = 0; i < chei.Count; i++) int j = dictionar[chei[i]]; |
Două lucruri de luat în considerare: timpul de inserție și timpul de căutare. Deoarece elementele nu sunt sortate automat, inserarea de elementele este mai rapidă. În mod similar, deoarece elementele nu sunt sortate, căutarea este mai complicată, ceea ce înseamnă că este mai lentă.
Pentru a înțelege mai bine modul în care un dicționar utilizează conceptul de chei și valori, să luăm următorul exemplu:
|
1 2 3 4 5 6 7 |
Dictionary<string, int> valoriFiziceComune = new Dictionary<string, int>(); valoriFiziceComune.Add("TemperaturaFierbereApa", 100); valoriFiziceComune.Add("TemperaturaInghetApa", 0); valoriFiziceComune.Add("ZeroAbsolut", -273); valoriFiziceComune.Add("PunctTopirePlumb", 327); Console.WriteLine(valoriFiziceComune["TemperaturaInghetApa"]); |
Deci, am declarat un nou Dicționar de tip string-int și am adăugat câteva constante fizice, cum ar fi temperatura de fierbere și de îngheț a apei. Am putea adăuga aceste valori și într-un array, dar ar deveni extrem de dificil să ne amintim ce reprezintă toate valorile, mai ales atunci când acestea devin multe. Și să nu mai vorbim de valori duplicate.. cine poate spune ce reprezintă fiecare? Deci, în acest caz, folosind un dicționar și dând nume semnificative cheilor, putem accesa cu ușurință valorile prin cheia lor corespunzătoare și de asemenea, știm ce reprezintă acele valori, în același timp. Singura regulă pe care trebuie să o respectăm este aceea de a nu adăuga chei duplicat. Dacă încercăm să adăugăm o cheie care există deja, Visual Studio va genera o excepție de tip System.ArgumentException: „Un element cu aceeași cheie a fost deja adăugat” (System.ArgumentException: ‘An item with the same key has already been added.’).
Cele mai importante metode ale clasei Dictionary sunt:
ContainsKey() – va verifica dacă o anumită cheie de tip string este prezentă în dicționar. Va returna True dacă cheia a fost găsită, sau False în caz contrar.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, int> dictionar = new Dictionary<string, int>(); dictionar.Add("mar", 1); dictionar.Add("fereastra", 5); // Verifica daca dictionarul contine acest string. if (dictionar.ContainsKey("mar")) { int valoare = dictionar["mar"]; Console.WriteLine(valoare); } // Verifica daca acest string exista. if (!dictionar.ContainsKey("portocala")) { Console.WriteLine(false); } } } |
TryGetValue() – Aceasta este de fapt modalitatea recomandată de a verifica dacă o cheie este prezentă într-un dicționar sau nu. Dacă cheia există, această funcție va returna valoarea elementului identificat de respectiva cheie.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, string> valori = new Dictionary<string, string>(); valori.Add("pisica", "felina"); valori.Add("caine", "caine"); // Foloseste TryGetValue. string test; if (valori.TryGetValue("pisica", out test)) // Returneaza true. Console.WriteLine(test); // Aceasta este valoarea pentru cheia pisica. if (valori.TryGetValue("pasare", out test)) // Returneaza false. Console.WriteLine(false); // Nu va fi executat. } } |
ContainsValue() – Această metodă nu are viteza de căutare constantă a metodei ContainsKey. În schimb, ea caută întreaga colecție de elemente. Este liniară în complexitate. Acesta va trece prin toate elementele din dicționar până când găsește o potrivire, sau până când nu mai există elemente care să poată fi verificate.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, int> d = new Dictionary<string, int>(); d.Add("pisica", 1); d.Add("caine", 2); if (d.ContainsValue(1)) Console.WriteLine(true); // True. } } |
Clear() – Aceasta va șterge toate perechile de tip cheie-valoare din dicționar. Același rezultat poate fi atins prin atribuirea valorii null dicționarului.
Remove() – Va elimina un element specific pe care îl transmitem ca argument al aceastei metode. În cazul în care cheia nu există, nici o operație nu va fi executată.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, int> d = new Dictionary<string, int>(); d.Add("pisica", 1); d.Add("caine", 2); d.Remove("caine"); // Elimina pisica. d.Remove("nimic"); // Nu face nimic. } } |
Count() – va returna un int reprezentând numărul de elemente din dicționar.
Equals() – Putem folosi această metodă pentru a verifica dacă două dicționare sunt identice.
Proprietatea cea mai utilizată a clasei Dicționar este:
Keys – Proprietatea Keys returnează o colecție de tip KeyCollection, nu o listă. Poate fi convertită într-o listă.
Rețineți că dacă încercăm să accesăm direct o cheie care nu există, vom obține o excepție numită KeyNotFoundException. Cu clasa dicționar trebuie să testați mai întâi dacă cheile există, cu metodele ContainsKey sau TryGetValue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
using System; using System.Collections.Generic; class Program { static void Main() { Dictionary<string, string> test = new Dictionary<string, string>(); test.Add("unu", "valoare"); string valoare; // Foloseste TryGetValue pentru a evita KeyNotFoundException. if (test.TryGetValue("doi", out valoare)) Console.WriteLine("Gasit"); else Console.WriteLine("Inexistent"); } } |
Tags: dictionar, structuri de date
