Dela via

Samlingar och datastrukturer

  • Artikel

Liknande data kan ofta hanteras effektivare 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 antingen enskilda element eller ett intervall med element i en samling.

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

Från och med .NET Framework 4 ger samlingarna i System.Collections.Concurrent namnområdet effektiva trådsäkra åtgärder för att komma åt samlingsobjekt från flera trådar. De oföränderliga samlingsklasserna i System.Collections.Immutable namnområdet (NuGet-paketet) är 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, 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. Detta minskar den kod som krävs för att använda samlingen. Samlingens prestanda kan dock påverkas negativt. För , om Count är mindre än Capacity, är det till exempel List<T>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 omallokeringar är att ange den ursprungliga kapaciteten till den uppskattade storleken för samlingen.

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

  • En konsekvent nedre 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. Array har en lägre gräns på noll som standard, men en annan nedre gräns kan definieras när du skapar en instans av klassen Array med hjälp Array.CreateInstanceav .

  • 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. De exponeras vanligtvis via SyncRoot medlemmarna och IsSynchronized . Dessa samlingar är inte trådsäkra som standard. Om du behöver skalbar och effektiv flertrådad åtkomst till en samling kan du använda någon av klasserna i System.Collections.Concurrent namnområdet eller överväga att använda en oföränderlig samling. Mer information finns i Thread-Valv Collections(Tråd-Valv-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 den här tabellen 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 samling 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ända objekt först in först ut (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Använda 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 kompromisser i prestanda. Använd följande tabell för att referera till hur olika föränderliga samlingstyper kan jämföras 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>, men gör ett dåligt jobb i en for loop, på grund av O(log n) tid för dess indexerare. Att räkna upp en ImmutableList<T> använda 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 enkel matris som List<T> använder. En matris kan indexeras mycket snabbt 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>. Det beror på att båda använder binära träd. Den stora skillnaden är naturligtvis 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.

Rubrik Beskrivning
Välja en samlingsklass Beskriver de olika samlingarna och hjälper dig att välja en för ditt scenario.
Vanliga samlingstyper 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 Beskriver användningen av generiska samlingstyper.
Jämförelser och sortering i samlingar Diskuterar användningen av likhetsjämförelser och sorteringsjämförelser i samlingar.
Sorterade samlingstyper Beskriver prestanda och egenskaper för sorterade samlingar
Samlingstyper för hashtable och ordlista Beskriver funktionerna i generiska och icke-generiska hash-baserade ordlistetyper.
Tråd-Valv-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.

Referens

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable