Dela via

Samlingar och datastrukturer

Liknande data kan ofta hanteras mer effektivt när de lagras och manipuleras som en samling. Du kan använda System.Array klassen eller klasserna i System.Collectionsnamnrymderna , System.Collections.Generic, System.Collections.Concurrentoch System.Collections.Immutable för att lägga till, ta bort och ändra enskilda element eller ett intervall med element i en samling.

Det finns två huvudtyper av samlingar. generiska samlingar och icke-generiska samlingar. Generiska samlingar är typsäkra vid kompilering. På grund av detta ger allmänna samlingar vanligtvis bättre prestanda. Allmänna samlingar accepterar en typparameter när de skapas. De kräver inte att du konverterar till och från typen Object när du lägger till eller tar bort element från samlingen. Dessutom stöds de flesta allmänna samlingar i Windows Store-appar. Icke-generiska samlingar lagrar objekt som Object, kräver gjutning och de flesta stöds inte för utveckling av Windows Store-appar. Du kan dock se icke-generiska samlingar i äldre kod.

I .NET Framework 4 och senare versioner ger samlingarna i System.Collections.Concurrent namnområdet effektiva trådsäkra åtgärder för åtkomst till samlingsobjekt från flera trådar. De oföränderliga samlingsklasserna i System.Collections.Immutable namnområdet (NuGet-paketet) är i sig trådsäkra eftersom åtgärder utförs på en kopia av den ursprungliga samlingen och den ursprungliga samlingen inte kan ändras.

Vanliga samlingsfunktioner

Alla samlingar innehåller metoder för att lägga till, ta bort eller hitta objekt i samlingen. Dessutom delar alla samlingar som direkt eller indirekt implementerar ICollection gränssnittet eller ICollection<T> gränssnittet följande funktioner:

Dessutom innehåller många samlingsklasser följande funktioner:

  • Egenskaper för kapacitet och antal

    Kapaciteten för en samling är antalet element som den kan innehålla. Antalet av en samling är antalet element som den faktiskt innehåller. Vissa samlingar döljer kapaciteten eller antalet eller båda.

    De flesta samlingar expanderas automatiskt i kapacitet när den aktuella kapaciteten nås. Minnet omallokeras och elementen kopieras från den gamla samlingen till den nya. Den här designen minskar den kod som krävs för att använda samlingen. Samlingens prestanda kan dock påverkas negativt. Till exempel för List<T>, om Count är mindre än Capacity, är det en O(1) åtgärd att lägga till ett objekt. Om kapaciteten behöver ökas för att rymma det nya elementet blir tillägg av ett objekt en O()-nåtgärd, där n är Count. Det bästa sättet att undvika dåliga prestanda som orsakas av flera omfördelningar är att ange den ursprungliga kapaciteten till samlingens uppskattade storlek.

    A BitArray är ett specialfall; dess kapacitet är densamma som dess längd, vilket är samma som dess antal.

  • En konsekvent lägre gräns

    Den nedre gränsen för en samling är indexet för det första elementet. Alla indexerade samlingar i System.Collections namnrymderna har en lägre gräns på noll, vilket innebär att de är 0-indexerade. Arrayhar en lägre gräns på noll som standard, men en annan lägre gräns kan definieras när du skapar en instans av klassen Array med .Array.CreateInstance

  • Synkronisering för åtkomst från flera trådar (System.Collections endast klasser).

    Icke-generiska samlingstyper i System.Collections-namnområdet ger viss trådsäkerhet med synkronisering, vilket vanligtvis exponeras via SyncRoot- och IsSynchronized-medlemmarna. Dessa samlingar är inte trådsäkra som standard. Om du behöver skalbar och effektiv åtkomst med flera trådar till en samling kan du använda en av klasserna i System.Collections.Concurrent namnområdet eller överväga att använda en oföränderlig samling. Mer information finns i Thread-Safe samlingar.

Välj en samling

I allmänhet bör du använda allmänna samlingar. I följande tabell beskrivs några vanliga samlingsscenarier och de samlingsklasser som du kan använda för dessa scenarier. Om du inte har använt allmänna samlingar tidigare hjälper följande tabell dig att välja den generiska samling som fungerar bäst för din uppgift:

Jag vill... Allmänna samlingsalternativ Alternativ för icke generisk kollektion Alternativ för trådsäker eller oföränderlig samling
Lagra objekt som nyckel/värde-par för snabb uppslag efter nyckel Dictionary<TKey,TValue> Hashtable

(En samling nyckel/värde-par som är ordnade baserat på nyckelns hashkod.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Komma åt objekt efter index List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Använd artiklar först in först ut (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Använd data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Komma åt objekt sekventiellt LinkedList<T> Ingen rekommendation Ingen rekommendation
Ta emot meddelanden när objekt tas bort eller läggs till i samlingen. (implementerar INotifyPropertyChanged och INotifyCollectionChanged) ObservableCollection<T> Ingen rekommendation Ingen rekommendation
En sorterad samling SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
En uppsättning för matematiska funktioner HashSet<T>

SortedSet<T>		 Ingen rekommendation ImmutableHashSet<T>

ImmutableSortedSet<T>

Algoritmisk komplexitet i samlingar

När du väljer en samlingsklass är det värt att överväga potentiella avvägningar i prestanda. Använd följande tabell för att referera till hur olika föränderliga samlingstyper jämförs i algoritmisk komplexitet med motsvarande oföränderliga motsvarigheter. Ofta är oföränderliga samlingstyper mindre högpresterande men ger oföränderlighet – vilket ofta är en giltig jämförande fördel.

Föränderlig Amorterad Värsta fall Oföränderliga Komplexitet
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.AddSökning O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> Sökning O(1) O(1) – eller strikt O(n) ImmutableDictionary<T> Sökning O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

A List<T> kan effektivt räknas upp med hjälp av antingen en for loop eller en foreach loop. Ett ImmutableList<T> gör däremot ett dåligt jobb i en for-slinga, på grund av dess O(log n) tid som indexerare. Att räkna upp en ImmutableList<T> med en foreach-loop är effektivt eftersom ImmutableList<T> använder ett binärt träd för att lagra sina data i stället för en matris som List<T> använder. En matris kan snabbt indexeras till, medan ett binärt träd måste gå nedåt tills noden med önskat index hittas.

Dessutom SortedSet<T> har samma komplexitet som ImmutableSortedSet<T> eftersom de båda använder binära träd. Den betydande skillnaden är att ImmutableSortedSet<T> använder ett oföränderligt binärt träd. Eftersom ImmutableSortedSet<T> även erbjuder en System.Collections.Immutable.ImmutableSortedSet<T>.Builder klass som tillåter mutation, kan du ha både oföränderlighet och prestanda.

Titel Beskrivning
Välja en samlingsklass Beskriver de olika samlingarna och hjälper dig att välja en för ditt scenario.
Samlingstyper som används ofta Beskriver vanliga generiska och icke-generiska samlingstyper som System.Array, System.Collections.Generic.List<T>och System.Collections.Generic.Dictionary<TKey,TValue>.
När du ska använda allmänna samlingar Diskuterar användningen av generiska samlingstyper.
Jämförelser och sorterar i samlingar Diskuterar användningen av likhetsjämförelser och sorteringsjämförelser i samlingar.
Sorterade samlingstyper Beskriver sorterade samlingars prestanda och egenskaper.
Samlingstyper för hashtabell och dictionär Beskriver funktionerna i generiska och icke-generiska hash-baserade ordlistetyper.
Tråd-säkra samlingar Beskriver samlingstyper som System.Collections.Concurrent.BlockingCollection<T> och System.Collections.Concurrent.ConcurrentBag<T> som stöder säker och effektiv samtidig åtkomst från flera trådar.
System.Collections.Immutable Introducerar oföränderliga samlingar och innehåller länkar till samlingstyperna.

Hänvisning

  • Last updated on