Choosing C# Collections: Dictionary, HashSet, Frozen

Revised November 2026. The Korean original of this article (July 19, 2021) mostly repeated the legacy collections article from the same month — ArrayList, Queue, Stack, Hashtable — and three of its examples did not compile on .NET 10 (error CS1003 from 2.3 f, error CS0103 from a Colsole typo). So this version has a new scope: choosing among the collections you should use today. The legacy classes and the cost of boxing now live in the basics article, and List<T> internals in C# List Internals.

This article is for developers who are comfortable with List<T> and Dictionary but are not sure when HashSet, SortedDictionary, PriorityQueue, FrozenDictionary or ImmutableArray is the better choice. The short version: look up by key with Dictionary/HashSet; if the data never changes after startup, use FrozenDictionary/FrozenSet; reach for SortedDictionary only when you continuously need key order. We measured lookup speed and build cost with 10,000 string keys so the advice has numbers behind it.

What we fixed from the 2021 version

The three examples for ArrayList, Queue and Stack had a space between a floating-point literal and its suffix, and the parser stopped right there:

Program.cs(11,32): error CS1003: Syntax error, ',' expected

Fixing 2.3 f to 2.3f uncovers the next problem, a misspelled Console:

Program.cs(16,17): error CS0103: The name 'Colsole' does not exist in the current context
Program.cs(17,17): error CS0103: The name 'Colsole' does not exist in the current context

With both fixed, the programs did what their comments said. ArrayList printed 10 / 2.3 / 30 followed by two Korean greeting strings, Queue printed 30 / 4.4 / ABC, and Stack printed ABC / 4.4 / 10. The Hashtable example already compiled and printed its three values in insertion order (direct key access, not enumeration, so order was not an issue there).

Three statements in the text also needed correcting:

• "Every collection in C# can hold variables of any type" is true only of the non-generic classes in System.Collections. Adding a string to a List<int> fails to compile with error CS1503.
• "A hash table key can be of any type" comes with conditions. null is never a valid key (ArgumentNullException), and a custom key type must override both Equals and GetHashCode, or two equal keys will be treated as different.
• The closing "help" section about stack, heap and data segments in C was off-topic and is removed. It claimed that int i = 10; int array[i]; cannot be compiled. Since C99 this is a variable-length array and compiles: with clang -std=c99, sizeof array printed 40. Only in C89 mode do you get warning: variable length arrays are a C99 feature.
• The four diagrams in the original (queue, stack, hash table, boxing) appeared to come from other material, so they were removed to avoid copyright problems. Queue and stack behavior is shown with real output in the legacy collections article, and every figure here is our own.

Dictionary and HashSet: the defaults

To find a value by key, use Dictionary<TKey, TValue>. To ask "is this in the set?", use HashSet<T>. Both are hash-based, so lookup time stays roughly flat as the collection grows.

HashSet<string> a = ["ios", "android", "web"];   // C# 12 collection expression
HashSet<string> b = ["web", "desktop"];
a.IntersectWith(b);
Console.WriteLine("HashSet Add dup -> " + b.Add("web") + ", intersect: " + string.Join(",", a));

HashSet Add dup -> False, intersect: web

HashSet.Add returns false instead of throwing when the item is already present, so "process each item only the first time" is a one-liner. You also get set operations: IntersectWith, UnionWith, ExceptWith.

Watch the enumeration order. A Dictionary you only add to appears to enumerate in insertion order, but freed slots are reused:

var d = new Dictionary<string, int> { ["a"] = 1, ["b"] = 2, ["c"] = 3 };
d.Remove("a"); d["d"] = 4;
Console.WriteLine(string.Join(",", d.Keys));

d,b,c

d came out first. The order is undefined by contract, so when order matters use SortedDictionary or sort explicitly.

SortedDictionary, LinkedList and PriorityQueue

SortedDictionary<TKey, TValue> keeps its keys sorted at all times; internally it is a balanced binary search tree.

SortedDictionary: apple,fig,pear

The keys went in as pear, apple, fig and came out in key order. The price is slower lookups than a hash table (measured below).

LinkedList<T> is a doubly linked list. Inserting or removing next to a node you already hold (LinkedListNode<T>) takes constant time. Finding a node by value with Find walks from the head, so unless you keep node references around — an LRU cache is the classic case — List<T> is the better default.

var ll = new LinkedList<int>([1, 2, 4]);
ll.AddAfter(ll.Find(2)!, 3);   // 1,2,3,4

PriorityQueue<TElement, TPriority> arrived in .NET 6; it did not exist in .NET 5, the current release when the original article was written. The smallest priority comes out first:

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 5); pq.Enqueue("urgent", 1); pq.Enqueue("normal", 3);
while (pq.TryDequeue(out var job, out var pri)) Console.Write($"{job}({pri}) ");

urgent(1) normal(3) low(5) 

Per the Microsoft Learn documentation, items with equal priority come out in no guaranteed order, and enumerating UnorderedItems does not follow priority. Use it wherever you repeatedly need "the most urgent thing next": job scheduling, Dijkstra's shortest path, merging sorted streams.

FrozenDictionary, FrozenSet and ImmutableArray

FrozenDictionary and FrozenSet (.NET 8, System.Collections.Frozen) cannot be modified after creation; in exchange, building one analyzes the keys and picks a lookup strategy. Printing the concrete type shows it:

Frozen: 2 True LengthBucketsFrozenDictionary`1

With short keys like "ko", "ja" and "en" it chose a length-bucket implementation. For the user-000123-… keys in the benchmark below it chose OrdinalStringFrozenDictionary_LeftJustifiedSubstring, which hashes only a slice of each key. Calling Add through the IDictionary interface throws NotSupportedException.

ImmutableArray<T> (System.Collections.Immutable) is an array that cannot change. Add leaves the original alone and returns a new array:

ImmutableArray<int> ia = [1, 2, 3];
var ib = ia.Add(4);   // ia = 1,2,3   ib = 1,2,3,4

ImmutableArray is a struct, so a default value has no backing array. IsDefault was True, and reading Length in that state threw NullReferenceException. Initialize fields with [] or ImmutableArray<int>.Empty.

A common mix-up is the read-only wrapper:

var src = new List<int> { 1, 2 };
IReadOnlyList<int> ro = src.AsReadOnly();
src.Add(3);
Console.WriteLine(ro.Count);   // 3

AsReadOnly() is just a window onto the original list, so it changes when the list changes. "The caller cannot modify it" is satisfied by a wrapper; "nobody can modify it" needs Immutable or Frozen.

Measured: lookups over 10,000 string keys

We loaded 10,000 string keys shaped like user-000123-1a2b3c4d into each collection, then performed 5 million lookups with keys drawn at random in advance (every key exists). Each collection was called through the same kind of lambda, so call overhead is identical across rows. .NET 10.0.14, Release build, Apple Silicon Mac; the value shown is the last of three runs after a warm-up.

Dictionary varied between 18 and 33 ns from run to run; the others were stable. Three takeaways:

• Frozen collections were about 1.5× faster to query and about 8× more expensive to build. At 1.8 ms for 10,000 keys that is irrelevant once at startup and wasteful per request.
• ImmutableDictionary was more than 4× slower than Dictionary. It is a tree, designed for cheaply producing modified copies that share structure. If all you need is a table that never changes, FrozenDictionary is the right tool.
• List.IndexOf took about 11 µs, nearly 500× slower than Dictionary, because it compares against up to 10,000 strings. A loop calling Contains on a list is usually the first thing worth switching to a HashSet.

Decision figure: which collection when

How to move legacy ArrayList and Hashtable code onto these types is in C# ArrayList, Hashtable: Boxing Cost and Migration, and filtering and grouping these collections is in LINQ basics.

Test environment: .NET SDK 10.0.403 / runtime 10.0.14, C# 14 (net10.0 default), macOS on an Apple Silicon Mac. C examples with Apple clang.