C# Collections: Arrays, List, Dictionary and HashSet

Choosing and explaining the right collection is a staple of C# interviews. This article covers the types you must know and the questions that come with them.

Array versus List<T>

A List<T> is a wrapper around an array. When the internal array is full, it allocates a bigger one (roughly double) and copies the items, so adding is amortized O(1). If you know the size in advance, pass a capacity (new List<int>(1000)) to avoid repeated resizing.

Choosing a collection

How a Dictionary works

A Dictionary<TKey, TValue> is a hash table:

1. It calls key.GetHashCode() and uses the result to choose a bucket.
2. If several keys land in the same bucket (a collision), it compares them with Equals() to find the right one.
3. Lookups, inserts and removals are O(1) on average. The worst case is O(n) if many keys collide.

That is why a key type must implement GetHashCode() and Equals() consistently: keys that are equal must produce the same hash code. A class that does not override them uses reference equality, so two "equal-looking" objects are different keys:

var classMap = new Dictionary<CoordClass, string>();
classMap[new CoordClass(1, 2)] = "A";
Console.WriteLine(classMap.ContainsKey(new CoordClass(1, 2)));    // False  (reference equality)

var recordMap = new Dictionary<CoordRecord, string>();
recordMap[new CoordRecord(1, 2)] = "A";
Console.WriteLine(recordMap.ContainsKey(new CoordRecord(1, 2)));  // True  (records compare by value)

public class CoordClass
{
    public CoordClass(int x, int y) { X = x; Y = y; }
    public int X { get; }
    public int Y { get; }
}

public record CoordRecord(int X, int Y);

Records and structs get value equality for free. For a normal class, override both Equals and GetHashCode, and keep the fields they use immutable: mutating a key after inserting it makes it unfindable.

Common dictionary operations:

var ages = new Dictionary<string, int> { ["Asha"] = 31, ["Ben"] = 24 };

if (ages.TryGetValue("Asha", out int age))     // safe lookup, no exception
    Console.WriteLine(age);                    // 31

Console.WriteLine(ages.GetValueOrDefault("Zed", -1));   // -1

ages["Carla"] = 45;                            // adds or overwrites
Console.WriteLine(ages.Count);                 // 3

ages["Zed"] throws KeyNotFoundException for a missing key, so use TryGetValue when a key might be absent.

HashSet<T>

A HashSet<T> stores unique items and answers "is it in there?" in O(1) on average. Its method returns if the item was already present, which makes it ideal for finding duplicates:

IEnumerable<T>, ICollection<T> and IList<T>

Accept the least specific type that does the job (usually or ), and return a concrete type that is useful to the caller.

The classic bug: changing a list while looping over it

over a detects that the collection changed and throws. Use , loop backwards with a loop, or build a new list.

Practise

1. Use a to count the letters in a word. See the character frequency snippet.
2. Make a class a dictionary key, then override and so lookups work.
3. Solve "two sum" with a dictionary: two sum snippet.