Struktury danych .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Szybkość, pamięć i kiedy z nich korzystać?

213

.NET ma wiele skomplikowanych struktur danych. Niestety niektóre z nich są dość podobne i nie zawsze jestem pewien, kiedy użyć jednego, a kiedy innego. Większość moich książek w języku C # i Visual Basic mówi o nich do pewnego stopnia, ale tak naprawdę nigdy nie wchodzą w szczegóły.

Jaka jest różnica między Array, ArrayList, List, Hashtable, Dictionary, SortedList i SortedDictionary?

Które są policzalne (IList - czy można wykonywać pętle „foreach”)? Które używają par klucz / wartość (IDict)?

Co z śladem pamięci? Szybkość wstawiania? Szybkość pobierania?

Czy są jakieś inne struktury danych, o których warto wspomnieć?

Wciąż szukam więcej szczegółów na temat użycia pamięci i szybkości (notacja Big-O).

Precel
źródło
12
Powinieneś rozbić to pytanie na części. Zadajesz dwadzieścia różnych rzeczy, z których połowa może dać prosta wyszukiwarka Google. Proszę być bardziej precyzyjnym; trudno jest pomóc, gdy twoje pytanie jest tak rozproszone.
33
Myślałem o zerwaniu z tym, ale zdałem sobie sprawę, że ktoś prawdopodobnie będzie w stanie skonsolidować wszystkie te odpowiedzi w jednym miejscu. W rzeczywistości, jeśli ktoś może wymyślić tabelę profilującą wszystko, może stać się wspaniałym zasobem na tej stronie.
Precel
9
Czy to pytanie można przekształcić w wiki?
BozoJoe
1
Ten artykuł MSDN obejmuje wiele z tych pytań, w tym drzewa, wykresy i zestawy, Obszerne badanie struktur danych
Ryan Fisher
1
Ryan, artykuły pod tym linkiem mają 14 lat (12 w momencie wysłania). Uwaga dodatkowa Czytałem je sam przez ostatni tydzień. ale nie zawierają też nowszej technologii i rozpaczliwie potrzebują aktualizacji. Oraz więcej wskaźników wydajności i przykładów.
htm11h

Odpowiedzi:

156

Z czubka mojej głowy:

  • Array* - reprezentuje oldskulową tablicę pamięci - coś w rodzaju aliasu dla normalnej type[]tablicy. Potrafi wyliczyć. Nie może rosnąć automatycznie. Zakładałbym bardzo szybką prędkość wstawiania i wycofywania.

  • ArrayList- automatycznie rosnąca tablica. Dodaje więcej kosztów ogólnych. Można wyliczyć., Prawdopodobnie wolniejszy niż normalny układ, ale wciąż dość szybki. Są one często używane w .NET

  • List- jedna z moich ulubionych - może być używana z ogólnymi, więc możesz mieć silnie typowaną tablicę, np List<string>. Poza tym zachowuje się bardzo podobnieArrayList

  • Hashtable- zwykły stary hashtable. Najgorszy przypadek od O (1) do O (n). Potrafi wyliczyć właściwości wartości i kluczy oraz wykonać pary klucz / wartość

  • Dictionary - to samo co powyżej, tylko silnie wpisane za pomocą generycznych, takich jak Dictionary<string, string>

  • SortedList- posortowana lista ogólna. Zwalniane przy wstawianiu, ponieważ musi dowiedzieć się, gdzie umieścić rzeczy. Może wyliczać. Prawdopodobnie to samo przy pobieraniu, ponieważ nie musi się uciekać, ale usuwanie będzie wolniejsze niż zwykła stara lista.

Zwykle używam Listi Dictionarycały czas - kiedy zaczniesz używać ich silnie napisanych za pomocą generyków, naprawdę trudno jest wrócić do standardowych nie-ogólnych.

Istnieje również wiele innych struktur danych - istnieje KeyValuePairwiele przydatnych rzeczy, SortedDictionaryktóre mogą być przydatne.

Sam Schutte
źródło
3
Tabela skrótowa to O (1), najgorszym przypadkiem (z kolizjami) może być O (n)
Justin Bozonier 18.1008
7
Istnieje wiele innych struktur danych, które musisz tutaj dodać. jak LinkedList, Skip List, Stack, Queue, Heap, Trees, Graphs. Są to również bardzo ważne struktury danych.
DarthVader,
2
ConcurrentDictionary dodany w .Net 4.0 zapewnia ogólny słownik z Thread Safety
Harindaka
2
Również BlockingCollection <T> zapewnia bezpieczną implementację producenta / konsumenta w wątku
Harindaka,
7
ArrayListużywa metod wirtualnych, ale List<T>nie stosuje . ArrayListzostał w dużej mierze zastąpiony List<T>kolekcjami standardowymi i Collection<T>klasą podstawową kolekcji niestandardowych. Hashtablezostał w dużej mierze zastąpiony przez Dictionary<TKey, TValue>. Polecam unikanie ArrayListi Hashtabledla nowego kodu.
Sam Harwell
29

Jeśli to możliwe, użyj ogólnych. To zawiera:

  • List zamiast ArrayList
  • Słownik zamiast HashTable
Adam Tegen
źródło
24

Po pierwsze, wszystkie kolekcje w .NET implementują IEnumerable.

Po drugie, wiele kolekcji jest duplikatami, ponieważ w wersji 2.0 frameworku dodano elementy generyczne.

Tak więc, chociaż kolekcje ogólne prawdopodobnie dodają funkcje, w przeważającej części:

  • Lista jest ogólną implementacją ArrayList.
  • Słownik jest ogólną implementacją Hashtable

Tablice to kolekcja o stałym rozmiarze, w której można zmienić wartość przechowywaną pod danym indeksem.

SortedDictionary to IDictionary, który jest sortowany na podstawie kluczy. SortedList to IDictionary, który jest sortowany na podstawie wymaganego IComparer.

Tak więc implementacje IDictionary (te obsługujące KeyValuePairs) to: * Hashtable * Dictionary * SortedList * SortedDictionary

Kolejną kolekcją dodaną w .NET 3.5 jest zestaw Hashset. Jest to kolekcja obsługująca operacje na zestawach.

Ponadto LinkedList jest standardową implementacją listy połączonych (lista jest listą tablic dla szybszego wyszukiwania).

Abe Heidebrecht
źródło
20

Oto kilka ogólnych wskazówek dla Ciebie:

  • Możesz używać foreachna typach, które implementują IEnumerable. IListjest zasadniczo IEnumberablez właściwościami Counti Item(dostęp do elementów za pomocą indeksu zerowego). IDictionaryz drugiej strony oznacza, że ​​możesz uzyskać dostęp do elementów według dowolnego indeksu z haszowaniem.

  • Array, ArrayListA Listwszystko realizować IList. Dictionary, SortedDictionaryi Hashtablewdrożyć IDictionary.

  • Jeśli używasz platformy .NET 2.0 lub nowszej, zalecane jest użycie ogólnych odpowiedników wymienionych typów.

  • Aby poznać złożoność czasu i przestrzeni różnych operacji na tych typach, należy zapoznać się z ich dokumentacją.

  • Struktury danych .NET znajdują się w System.Collectionsprzestrzeni nazw. Istnieją biblioteki typów, takie jak PowerCollections, które oferują dodatkowe struktury danych.

  • Aby uzyskać dokładne zrozumienie struktur danych, zapoznaj się z zasobami takimi jak CLRS .

czarne skrzydło
źródło
1
z msdn , wygląda na to, że sortedList zaimplementuj IDictionnary - nie IList
Haim Bendanan
Naprawiony. Dziękuję za komentarz. Wygląda na to, że SortedList utrzymuje listę kluczy / wartości, więc w zasadzie reprezentuje dane słownika. Nie pamiętam, jak ta klasa działała, kiedy po raz pierwszy napisałem odpowiedź ...
blackwing
9

Struktury danych .NET:

Więcej informacji na temat tego, dlaczego ArrayList i List są tak naprawdę różne

Tablice

Jak twierdzi jeden użytkownik, tablice są kolekcją „starej szkoły” (tak, tablice są uważane za kolekcję, ale nie są częścią System.Collections). Ale czym jest „stara szkoła” o tablicach w porównaniu z innymi kolekcjami, tj. Tymi, które wymieniłeś w swoim tytule (tutaj ArrayList i List (Of T))? Zacznijmy od podstaw, patrząc na tablice.

Na początek tablice w Microsoft .NET to „mechanizmy, które pozwalają traktować kilka [związanych logicznie] elementów jako jedną kolekcję” (patrz link do artykułu). Co to znaczy? Tablice przechowują poszczególne elementy (elementy) sekwencyjnie, jeden po drugim w pamięci z adresem początkowym. Korzystając z tablicy, możemy łatwo uzyskać dostęp do sekwencyjnie przechowywanych elementów zaczynających się pod tym adresem.

Poza tym i w przeciwieństwie do programowania 101 powszechnych koncepcji, tablice mogą być bardzo złożone:

Tablice mogą być jednowymiarowe, wielowymiarowe lub zniszczone (o tablicach postrzępionych warto przeczytać). Same tablice nie są dynamiczne: po zainicjowaniu tablica o rozmiarze n rezerwuje wystarczająco dużo miejsca do przechowywania n liczby obiektów. Liczba elementów w tablicy nie może rosnąć ani kurczyć się. Dim _array As Int32() = New Int32(100)rezerwuje wystarczającą ilość miejsca w bloku pamięci, aby tablica zawierała 100 obiektów typu pierwotnego Int32 (w tym przypadku tablica jest inicjowana tak, aby zawierała 0). Adres tego bloku jest zwracany do _array.

Zgodnie z artykułem specyfikacja języka wspólnego (CLS) wymaga, aby wszystkie tablice były zerowane. Tablice w .NET obsługują tablice niezerowe; jest to jednak mniej powszechne. W wyniku „powszechności” tablic zerowych Microsoft poświęcił wiele czasu na optymalizację ich wydajności ; dlatego macierze jednowymiarowe oparte na zerach (SZ) są „specjalne” - i naprawdę najlepsza implementacja tablicy (w przeciwieństwie do wielowymiarowych itp.) - ponieważ SZ mają specyficzne instrukcje języka pośredniego do manipulowania nimi.

Tablice są zawsze przekazywane przez odniesienie (jako adres pamięci) - ważny element układanki Array, którą należy znać. Podczas gdy sprawdzają granice (wyrzucą błąd), sprawdzanie granic można również wyłączyć w tablicach.

Ponownie, największą przeszkodą dla tablic jest to, że nie można ich zmieniać rozmiarów. Mają „stałą” pojemność. Przedstawiamy ArrayList i List (Of T) w naszej historii:

ArrayList - lista ogólna

ArrayList (wraz z List(Of T)- chociaż istnieją pewne krytyczne różnice tutaj wyjaśnione później) - to chyba najlepiej traktowane jako kolejnego dodatku do kolekcji (w szerokim tego słowa znaczeniu). ArrayList dziedziczy po interfejsie IList (potomek „ICollection”) interfejsu. Same ArrayLists są bardziej obszerne - wymagają większego obciążenia - niż Listy.

IListumożliwia implementacji traktowanie ArrayLists jako list o stałej wielkości (takich jak tablice); jednak oprócz dodatkowej funkcjonalności dodanej przez ArrayLists, nie ma rzeczywistych korzyści z używania ArrayLists, które mają stały rozmiar, ponieważ ArrayLists (ponad tablicami) w tym przypadku są znacznie wolniejsze.

Z mojego czytania, ArrayLists nie można postrzępić: „Używanie tablic wielowymiarowych jako elementów ... nie jest obsługiwane”. Znów kolejny gwóźdź do trumny ArrayLists. ArrayLists również nie są „wpisane” - co oznacza, że pod spodem wszystko, ArrayList jest po prostu Array dynamiczne obiektów: Object[]. Wymaga to dużej ilości boksu (niejawnego) i rozpakowania (jawnego) podczas implementacji ArrayLists, ponownie zwiększając ich obciążenie.

Nieuzasadniona myśl: myślę, że pamiętam albo czytając lub słysząc od jednego z moich profesorów, że ArrayLists są rodzajem drania koncepcyjnego, który próbuje przenieść się z Tablic do Kolekcji typu List, tj. Chociaż kiedyś był wielkim ulepszeniem Tablic, nie są już najlepszą opcją, ponieważ dokonano dalszego rozwoju kolekcji

List (Of T): What ArrayList stał się (i miał nadzieję, że będzie)

Różnica w użyciu pamięci jest na tyle znacząca, że ​​List (Of Int32) zużył 56% mniej pamięci niż ArrayList zawierający ten sam prymitywny typ (8 MB vs. 19 MB w powyższej demonstracji połączonej z dżentelmenem: ponownie, połączony tutaj ) - chociaż jest to wynik złożony z komputera 64-bitowego. Ta różnica naprawdę pokazuje dwie rzeczy: po pierwsze (1), „obiekt” typu Int32 w ramce (ArrayList) jest znacznie większy niż czysty typ pierwotny Int32 (List); po drugie (2) różnica jest wykładnicza w wyniku wewnętrznego działania 64-bitowej maszyny.

Jaka jest różnica i czym jest lista (Of T) ? MSDN definiuje List(Of T)jako „… silnie wpisaną listę obiektów, do których można uzyskać dostęp za pomocą indeksu”. Znaczenie ma tutaj bit „silnie typowany”: Lista (Of T) „rozpoznaje” typy i przechowuje obiekty jako ich typy. Tak więc an Int32jest przechowywane jako Int32a nie Objecttyp. Eliminuje to problemy spowodowane przez boksowanie i rozpakowywanie.

MSDN określa, że ​​ta różnica ma zastosowanie tylko podczas przechowywania typów pierwotnych, a nie typów referencyjnych. Zbyt duża różnica występuje naprawdę na dużą skalę: ponad 500 elementów. Co bardziej interesujące, w dokumentacji MSDN czytamy: „Korzystną dla Ciebie implementacją jest zastosowanie implementacji klasy List (Of T) zamiast klasy ArrayList ....”

Zasadniczo List (Of T) jest ArrayList, ale lepiej. Jest to „ogólny odpowiednik” ArrayList. Podobnie jak ArrayList, nie ma gwarancji, że zostanie posortowane do czasu posortowania (przejdź do rysunku). Lista (Of T) ma również kilka dodatkowych funkcji.

Tomasz
źródło
5

Współczuję temu pytaniu - również znalazłem (znajduję?) Oszałamiający wybór, więc postanowiłem naukowo sprawdzić, która struktura danych jest najszybsza (zrobiłem test przy użyciu VB, ale wyobrażam sobie, że C # będzie taki sam, ponieważ oba języki zrób to samo na poziomie CLR). Tutaj możesz zobaczyć niektóre wyniki testów porównawczych przeprowadzone przeze mnie (jest też dyskusja o tym, który typ danych najlepiej wykorzystać w jakich okolicznościach).

Andy Brown
źródło
3

Są dość dobrze zapisane w inteligencji. Po prostu wpisz System.Collections. lub System.Collections.Generics (preferowane), a otrzymasz listę i krótki opis tego, co jest dostępne.

Joel Coehoorn
źródło
3

Tabele skrótów / słowniki są wydajnością O (1), co oznacza, że ​​wydajność nie jest funkcją wielkości. To ważne, aby wiedzieć.

EDYCJA: W praktyce średnia złożoność czasu dla wyszukiwań Hashtable / Dictionary <> wynosi O (1).

Chris
źródło
5
Nie ma czegoś takiego jak „wydajność”. Złożoność zależy od operacji. Na przykład, jeśli wstawisz n elementów do Słownika <>, nie będzie to O (1) z powodu ponownego skrócenia.
Ilya Ryzhenkov
2
Do Twojej wiadomości, nawet po ponownym skróceniu, Dictionary nadal jest O (1). Rozważ scenariusz tuż przed rozszerzeniem słownika. Połowa elementów - tych, które zostały dodane od ostatniego rozszerzenia - zostanie raz zaszyfrowana. Połowa reszty zostanie dwukrotnie wypłukana. Połowa pozostałej części z tego trzy razy itd. Średnia liczba operacji haszujących wykonywanych na każdym elemencie będzie wynosić 1 + 1/2 + 1/4 + 1/8 ... = 2. Sytuacja bezpośrednio po rozwinięciu jest zasadniczo taka sama, ale każdy element został zaszyfrowany jeden dodatkowy czas (więc średnia liczba skrótów wynosi trzy). Wszystkie pozostałe scenariusze są pomiędzy tymi.
supercat
3

Kolekcje ogólne będą działać lepiej niż ich nie-ogólne odpowiedniki, zwłaszcza podczas iteracji wielu elementów. Wynika to z tego, że boksowanie i rozpakowywanie już nie występuje.

Russ Cam
źródło
2

Ważna uwaga na temat Hashtable vs. Dictionary dla systematycznej inżynierii handlu wysokiej częstotliwości: Problem bezpieczeństwa wątków

Hashtable jest bezpieczny dla wielu wątków. Słownikowe statyczne elementy słownika są bezpieczne dla wątków, ale nie można zagwarantować, że są to dowolne elementy instancji.

Zatem Hashtable pozostaje „standardowym” wyborem w tym względzie.

Obrabować
źródło
To częściowo prawda. Można go Hashtablebezpiecznie używać tylko z jednym pisarzem i wieloma czytnikami jednocześnie. Z drugiej strony, korzystanie Dictionaryz wielu czytników jest bezpieczne, o ile nie jest modyfikowane jednocześnie.
Bryan Menard
Zdecydowanie. Jednak w obszarze handlu jednocześnie odczytujemy dane z rynku na żywo i przeprowadzamy analizy zawierające dołączone wpisy. Zależy to również od liczby handlowców korzystających z systemu - jeśli to tylko ty, to oczywiście nie ma znaczenia.
Rob
1
.NET 4.0 zapewnia ConcurrentDictionary <TKey, TValue>
Rob
1

Istnieją subtelne i niezbyt subtelne różnice między zbiorami rodzajowymi i nietypowymi. Używają jedynie różnych podstawowych struktur danych. Na przykład Hashtable gwarantuje jeden pisarz-wiele czytelników bez synchronizacji. Słownik nie.

Ilya Ryzhenkov
źródło
1

Najpopularniejsze struktury i kolekcje danych C #

  • Szyk
  • ArrayList
  • Lista
  • Połączona lista
  • Słownik
  • HashSet
  • Stos
  • Kolejka
  • SortedList

C # .NET ma wiele różnych struktur danych, na przykład jedną z najczęstszych jest tablica. Jednak C # ma wiele bardziej podstawowych struktur danych. Wybór odpowiedniej struktury danych do użycia jest częścią napisania dobrze ustrukturyzowanego i wydajnego programu.

W tym artykule omówię wbudowane struktury danych C #, w tym nowe wprowadzone w C # .NET 3.5. Należy pamiętać, że wiele z tych struktur danych dotyczy innych języków programowania.

Szyk

Prawdopodobnie najprostszą i najczęstszą strukturą danych jest tablica. Tablica AC # jest w zasadzie listą obiektów. Jego cechami charakterystycznymi jest to, że wszystkie obiekty są tego samego typu (w większości przypadków) i jest ich określona liczba. Charakter tablicy pozwala na bardzo szybki dostęp do elementów na podstawie ich pozycji na liście (znanej również jako indeks). Tablica AC # jest zdefiniowana w następujący sposób:

[object type][] myArray = new [object type][number of elements]

Kilka przykładów:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Jak widać z powyższego przykładu, tablica może być zainicjalizowana bez elementów lub z zestawu istniejących wartości. Wstawianie wartości do tablicy jest proste, o ile pasują. Operacja staje się kosztowna, gdy jest więcej elementów niż rozmiar tablicy, w którym to momencie tablica musi zostać rozwinięta. Trwa to dłużej, ponieważ wszystkie istniejące elementy muszą zostać skopiowane do nowej, większej tablicy.

ArrayList

Struktura danych C #, ArrayList, jest tablicą dynamiczną. Oznacza to, że ArrayList może zawierać dowolną liczbę obiektów i dowolnego typu. Ta struktura danych została zaprojektowana w celu uproszczenia procesów dodawania nowych elementów do tablicy. Pod maską ArrayList to tablica, której rozmiar jest podwajany za każdym razem, gdy zabraknie miejsca. Podwojenie rozmiaru tablicy wewnętrznej jest bardzo skuteczną strategią, która w długim okresie zmniejsza kopiowanie elementów. Nie dostaniemy tutaj tego dowodu. Struktura danych jest bardzo prosta w użyciu:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Minusem struktury danych ArrayList jest to, że należy przywrócić pobierane wartości z powrotem do ich pierwotnego typu:

int arrayListValue = (int)myArrayList[0]

Źródła i więcej informacji można znaleźć tutaj :

leonidaa
źródło