C# Reference ยท Collections
Capacity and resizing in .NET collections
How List, Dictionary, HashSet, StringBuilder and Queue grow in .NET: the Capacity property, EnsureCapacity, TrimExcess and when preallocating helps.
Most .NET collections store their items in an internal array. The number of items you stored is Count; the size of that array is Capacity. When you add an item and the array is full, the collection allocates a bigger array, copies the items and discards the old one. That copy is what makes growth cost O(n) on one add, and why adding is O(1) amortized.
If you know roughly how many items you will add, tell the collection up front. It avoids repeated allocations and copies, and it produces less garbage for the GC to collect.
var list = new List<int>(capacity: 1000); // one allocation list.EnsureCapacity(5000); // grow once, later list.TrimExcess(); // give back unused slots
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Syntax
public int Capacity { get; set; } // List<T>, StringBuilder public int EnsureCapacity(int capacity); // List<T>, Dictionary, HashSet, Queue<T>, Stack<T> public void TrimExcess(); // the same collections public List<T>(int capacity); // constructors take a capacity too
| Name | Description |
|---|---|
capacity |
The minimum number of items the collection should be able to hold without growing. |
Returns: EnsureCapacity returns the capacity after the call (on List<T> it returns the new Capacity; on hash-based collections it returns the new bucket-array capacity).
Errors: a negative capacity throws ArgumentOutOfRangeException. Assigning List<T>.Capacity a value smaller than Count also throws it.
Usage notes
List<T>starts empty with capacity 0, allocates 4 on the firstAdd, then doubles each time it fills up. Treat the exact numbers as an implementation detail, but the doubling pattern is why adds are amortized O(1).- Passing a capacity to a constructor reserves space; it does not add items.
new List<int>(100).Countis 0, and indexing[0]still throws. - For
DictionaryandHashSet, the real capacity is chosen from a table of prime sizes, so it is at least what you asked for but not equal to it. Resizing a hash table also rehashes every entry, which costs more than copying a list. TrimExcess()shrinks the backing array to the current count. Call it once after you finish building a long-lived collection, not in a loop.Clear()andRemovenever shrink capacity. A list that once held a million items keeps its million-slot array until you callTrimExcess()or drop it.ToList()andToArray()on a sequence whose count is known (arrays, lists) preallocate the exact size.- Preallocating too much wastes memory; preallocating a good estimate is a cheap, safe win for large collections.
Related
- List
- Dictionary<TKey,TValue>
- Collection complexity
- StringBuilder
- Lists in the tutorial