Przegląd typów kolekcji – ściąga
Wstęp
Pomijam fakt, że większość osób, którym robiłem techniczne review, jedyne typy kolekcji jakie znała to List<T>, Dictionary<K, V> i to właściwie wszystko (czasem jeszcze HashSet), to jest jeszcze jeden problem. Różne typy kolekcji są lepsze w niektórych przypadkach, a gorsze w innych. Głównie chodzi tutaj o performance. Ja wiem… Nie optymalizujemy za wcześnie. Niemniej jednak warto wiedzieć, które kolekcje sprawdzają się lepiej w konkretnych sytuacjach. W tym artykule robię zatem krótki przegląd większości kolekcji, jakie mamy do dyspozycji.
Dla maruderów
Nie opisuję tutaj rzeczy takich jak BitArray (i podobnych) ani kolekcji niegenerycznych. Niektóre klasy są wysoko wyspecjalizowane do konkretnych zadań (jak np. BitArray), a kolekcji niegenerycznych… po prostu nie powinniśmy raczej używać.
Jakie mamy kolekcje?
Pierwszy podział będzie ze względu na „thread safety”.
Kolekcje dla scenariuszy jednowątkowych
List<T>
To zdecydowanie najbardziej znana kolekcja w C#. Lista to po prostu tablica na sterydach i nic więcej. Elementy listy zajmują ciągły obszar w pamięci. Lista na dzień dobry rezerwuje sobie pewien obszar o wielkości określonej w Capacity (capacity to ilość elementów, jakie chcemy mieć, a nie wielkość wyrażona w bajtach). Gdy dodajemy nowe elementy i Capacity się kończy, wtedy lista rezerwuje nowy obszar w pamięci o rozmiarze Capacity * 2 (szczegół implementacyjny) i kopiuje tam swoje elementy. Itd. To oznacza, że dodawanie elementów do listy w pewnych sytuacjach może być kosztowne. Niemniej jednak jest najpopularniejszą kolekcją. Dostęp do elementu mamy przez jego indeks.
W skrócie:
- kolejność elementów zachowana
- elementy umieszczone w ciągłym miejscu w pamięci
- może zawierać duplikaty
- łatwy dostęp do poszczególnych elementów za pomocą indeksu
SortedList<K, V>
Lista sortowana. Coś w stylu połączenia List<V> z SortedDictionary<K, V>, chociaż nieco bliżej jej do słownika niż do listy. Elementy znajdują się wciąż w tablicach, czyli zajmują ciągłe miejsce w pamięci. Ale uwaga, kolekcja tak naprawdę zawiera dwie tablice – jedna trzyma klucze, druga wartości. Oczywiście wszystko ze sobą jest sprytnie zsynchronizowane. Uważam to jednak za szczegół implementacyjny, który być może kiedyś ulegnie zmianie.
Elementy są sortowane za pomocą klucza, czyli klucz powinien implementować interfejs IComparable<K>.
W skrócie:
- elementy sortowane na podstawie klucza
- elementy zajmują ciągłe miejsce w pamięci (osobne tablice dla kluczy i wartości)
- nie może zawierać duplikatów
- łatwy dostęp do poszczególnych elementów za pomocą indeksu
LinkedList<T>
To jest prawilna lista dwukierunkowa (kłaniają się struktury danych :)). Składa się z elementów (LinkedListNode<T>), które oprócz konkretnej wartości trzymają jeszcze referencje do następnego i poprzedniego elementu. Przez co pobieranie konkretnego elementu, np. 5tego może być nieco problematyczne, bo tak naprawdę wymaga przejścia przez wszystkie poprzednie elementy, aby uzyskać ten nas interesujący.
W skrócie:
- kolejność elementów zachowana
- elementy umieszczone w różnych miejscach w pamięci
- może zawierać duplikaty
- dostęp do poszczególnych elementów jest łatwy, ale może być wolniejszy
ObservableCollection<T>
To bardzo dobrze znają osoby piszące w WPF. Ta kolekcja po prostu daje Ci znać, kiedy coś się w niej zmieni. Tzn. element zostanie dodany, usunięty lub zamieniony. Pod spodem jest zwykła lista.
Queue<T>, Stack<T>
To po prostu typowa kolejka FIFO (queue) i stos LIFO (stack). Przydają się wtedy, kiedy chcemy się pozbyć elementu po zdjęciu go z kolekcji i chcemy mieć zapewniony konkretny porządek.
W skrócie:
- queue to kolejka FIFO, a stack to stos LIFO
- elementy umieszczone w ciągłym miejscu w pamięci
- może zawierać duplikaty
- element jest automatycznie zdejmowany po odczytaniu go z kolejki (stosu)
PriorityQueue<T, P>
Kolejka priorytetowa. Zawiera elementy typu T i priorytet typu P. Przydatna kiedy chcemy niektóre elementy w kolejce traktować priorytetowo.
W skrócie:
- kolejka z priorytetem
- brak kolejności elementów
- może zawierać duplikaty
- element jest automatycznie usuwany po odczytaniu go z kolejki
Dictionary<K, T>
Słownik to kolekcja, która przetrzymuje obiekty na podstawie jakiegoś klucza. Klucz jest obliczany za pomocą metody GetHashCode z obiektu typu K. A wartości to typy T. Wyróżnia się szybkim dostępem do danych. Oczywiście to jeszcze zależy jak napiszesz swoją metodę GetHashCode, ale trzymając się standardowych podejść, wszystko powinno być dobrze 🙂
Słownik może mieć tylko jeden wpis z danym kluczem. Jeśli spróbujemy dodać kolejny z kluczem, który już istnieje w słowniku, rzucony będzie wyjątek.
UWAGA! NIGDY nie przechowuj wartości zwracanej z GetHashCode między uruchomieniami aplikacji. Po zmianie wersji .NET (nawet minor albo build) może okazać się, że GetHashCode zwraca inne wartości. Microsoft nie daje gwarancji, że tak nie będzie. A i ja się miałem okazję kiedyś przekonać o tym, że nie można na tym polegać. GetHashCode jest użyteczne tylko w tej samej wersji frameworka.
W skrócie:
- brak kolejności elementów
- elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- szybki dostęp do elementu po kluczu
ReadOnlyDictionary<K, T>
Daję go w sumie jako ciekawostkę. To słownik tylko do odczytu. Każda zmiana elementów po utworzeniu tego słownika kończy się rzuceniem wyjątku. Ja zdecydowanie wolę posługiwanie się odpowiednim interfejsem (np. IReadOnlyDictionary) niż tym słownikiem.
SortedDictionary<K, T>
To po prostu słownik, który jest posortowany. Każdy element w słowniku jest sortowany na podstawie klucza. Jeśli klucz implementuje interfejs IComparable<K>, wtedy ten właśnie komparator jest używany do porównania wartości. Sortowanie odbywa się automatycznie po zmianie na liście elementów. Natomiast klucz musi być niezmienny.
Potrzebuje nieco więcej pamięci niż SortedList, za to operacje dodawania i usuwania elementów są szybsze.
W skrócie:
- elementy są posortowane względem klucza
- elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- szybki dostęp do elementu po kluczu
FrozenDictionary<K, V>
To jest nowość w .NET 8. Pisałem już o tym w tym artykule. Generalnie jest to słownik tylko do odczytu, który jest zoptymalizowany pod kątem szukania elementów. I naprawdę daje radę. Zresztą zobacz sobie porównanie w moim artykule o nowościach w .NET 8.
W skrócie:
- brak kolejności elementów
- elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- szybki dostęp do elementów po kluczu (szybszy niż w Dictionary<K, V>)
- TYLKO DO ODCZYTU
HashSet<T>
To jest zbiór niepowtarzalnych elementów o typie T. „Powtarzalność” jest sprawdzana na podstawie metody GetHashCode. Można go uznać za coś w rodzaju słownika bez wartości.
W skrócie:
- brak kolejności elementów
- elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- szybki dostęp po kluczu
SortedSet<T>
To, podobnie jak HashSet, też jest formą zbioru. Ale SortedSet to struktura drzewa binarnego (czerwono-czarne drzewo binarne). Elementy są posortowane zgodnie z przekazanym w konstruktorze Comparerem (lub domyślnym, jeśli nie przekazano).
Utrzymuje porządek sortowania bez dodatkowego narzutu podczas dodawania lub usuwania elementów. Nie daje jednak bezpośredniego dostępu do konkretnego elementu. Są oczywiście rozszerzenia, które to umożliwiają, np. IEnumerable.ElementAt, jednak związane jest to z przechodzeniem przez drzewo. Zatem używaj tylko wtedy, jeśli potrzebujesz mieć posortowane elementy, gdzie dodawanie i usuwanie nie daje dodatkowego narzutu.
- elementy posortowane według przekazanego lub domyślnego
Comparera - elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- brak bezpośredniego dostępu do konkretnego elementu
- struktura drzewiasta
FrozenSet<T>
Analogicznie jak FrozenDictionary. Tylko reprezentuje HashSet zoptymalizowany do odczytu.
W skrócie:
- brak kolejności elementów
- elementy umieszczone w różnych miejscach w pamięci
- nie może zawierać duplikatów
- szybki dostęp do elementów po kluczu (szybszy niż w
HashSet<T>) - TYLKO DO ODCZYTU
Immutable*<T>
Jest do tego kilka kolekcji niezmienialnych, które są oparte dokładnie na tych wymienionych wyżej. Jednak… nie można ich zmienić. To znaczy, że jeśli np. umożliwiają dodawanie lub usuwanie elementów, to tworzą i zwracają tym samym zupełnie nową kolekcję, a oryginalna pozostaje bez zmian. Czyli przy każdym dodaniu/usunięciu, cała kolekcja jest kopiowana.
Kolekcje dla scenariuszy wielowątkowych
Tutaj najpierw słowo wstępu. Istnieje namespace System.Collections.Concurrent i to klasami z tego namespace powinniśmy się posługiwać jeśli chodzi o wielowątkowość. Są jeszcze inne kolekcje w innych namespace’ach (starszych), jak np. SynchronizedCollection opisane niżej. Ale tych raczej powinniśmy unikać, chyba że naprawdę z jakiegoś powodu musimy tego użyć.
SynchronizedCollection<T>
Czuję się trochę w obowiązku wspomnieć o tym starym tworze. TEORETYCZNIE to coś w rodzaju Listy do scenariuszy wielowątkowych. Jednak jego „thread-safe” ogranicza się tylko do tego, że każda operacja jest zamknięta w instrukcji lock. A blokowany jest obiekt dostępny przez SyncRoot.
Ostatecznie może to prowadzić do problemów w sytuacjach wielowątkowych, ponieważ operacje nie są atomowe. Czyli jeśli przykładowo próbujesz wykonać dwie operacje, które zasadniczo logicznie są jedną, wtedy może to prowadzić do poważnych problemów. Przykład?
if(!collection.Contains(element))
collection.Add(element);
Tutaj po wywołaniu metody Contains, wątek może się przełączyć i ostatecznie możesz skończyć z kilkoma takimi samymi elementami w kolekcji.
ConcurrentBag<T>
O, to chyba zasługuje na osobny artykuł. Ale krótko mówiąc, to taka kolejka, która działa najlepiej we wzorcu Producer-Consumer. Słowo „kolejka” jest tutaj bardzo dobrym wyznacznikiem, bo ConcurrentBag to kolejka. Tyle że to nie jest to ani LIFO, ani FIFO – ot taka kolejka o nieokreślonej kolejności 🙂
Kilka wątków (A, B, C) może wkładać do niej elementy. Kolejka ma swoją własną listę elementów dla każdego wątku. Jeśli teraz pobieramy z niej elementy w wątku A, a ConcurrentBag nie ma elementów dla wątku A, wtedy „kradnie” element z puli innego wątku. Tak to mniej więcej można opisać. Więc najlepiej sprawdza się, gdy wątek często obsługuje własne zadania. Wtedy jest najbardziej efektywny.
W skrócie:
- brak zachowania kolejności elementów
- elementy umieszczone w różnych miejscach w pamięci
- może zawierać duplikaty
- brak dostępu do konkretnego elementu, można jedynie pobrać kolejny element z kolejki
ConcurrentStack<T>, ConcurrentQueue<T>
To zasadniczo są odpowiedniki zwykłego Stack i Queue, tyle że wątkowo bezpieczne. Tzn., że różne wątki mogą zapisywać i odczytywać elementy z kolejek w tym samym czasie. Oczywiście elementy będą zdejmowanie zgodnie z porządkiem kolejki.
W skrócie:
- queue to kolejka FIFO, a stack to stos LIFO
- elementy umieszczone w różnych miejscach w pamięci – w przeciwieństwie do jednowątkowych odpowiedników
- może zawierać duplikaty
- element jest automatycznie zdejmowany po odczytaniu go z kolejki (stosu)
BlockingCollection<T>
To też jest rodzaj kolejki, ale nie musi. W swojej domyślnej postaci, w środku ma ConcurrentQueue<T>. Podczas tworzenia można jej podać maksymalną ilość elementów. Wtedy, jeśli jakiś wątek będzie chciał dodać kolejny element (gdy już cała kolekcja jest zapełniona), wątek zostanie wstrzymany aż inny pobierze coś z kolekcji i zwolni miejsce. W drugą stronę zadziała to podobnie – jeśli wątek będzie chciał pobrać coś z pustej kolekcji, to będzie czekał.
Podczas tworzenia kolekcji można podać dowolny „kontener” dla itemów, który implementuje interfejs IProducerConsumerCollection<T>.
W skrócie:
- elementy mogą być różnie umieszczone w zależności od przekazanego wewnętrznego kontenera – domyślnie jest to
ConcurrentQueue - może zawierać duplikaty (jeśli wewnętrzny kontener na to pozwala)
- brak dostępu do dowolnego elementu – można tylko ściągnąć aktualny element
UWAGA! Tutaj występuje jeszcze taka metoda jak CompleteAdding(). Wywołanie jej mówi kolekcji: „Słuchaj misiu, już nikt Ci nigdy niczego nie doda, a jeśli będzie próbował, zdziel go w twarz wyjątkiem”. To kwestia optymalizacyjna. Jeśli kolekcja jest oznaczona w ten sposób, wtedy wątek, który próbuje coś pobrać przy pustej kolekcji, nie będzie czekał, bo wie, że już nic nie zostanie dodane.
ConcurrentDictionary<K, T>
Nie ma co tu dużo mówić. To po prostu zwykły słownik przeznaczony do scenariuszy wielowątkowych. Różne wątki mogą jednocześnie zapisywać i odczytywać elementy. Poza tym niczym szczególnym nie różni się od zwykłego Dictionary<K, T>.
To tyle jeśli chodzi o standardowe kolekcje, których możemy używać. Dzięki za przeczytanie artykułu. Jeśli czegoś nie zrozumiałeś albo znalazłeś w tekście jakiś błąd, koniecznie daj znać w komentarzu.
A, no i koniecznie podziel się tym artykułem z osobami, które znają jedynie listę i słownik 😉
