Dictionaries and Sets

Analogy categoryAnalogies

Dictionary<TKey, TValue> and HashSet<T>, both in System.Collections.Generic, are hash-table-based collections optimized for one purpose above all else: answering "do I have this?" or "what value is associated with this key?" in close to O(1) time, regardless of how many elements the collection holds. Internally, both compute a hash code for each key (or set element) via GetHashCode(), use that hash to determine a bucket, and then use Equals() to resolve collisions within that bucket. This is fundamentally different from a List<T>'s Contains, which must scan linearly, comparing every element one by one until a match is found or the list is exhausted — an O(n) operation.

🏏

Cricket analogy: Checking if a player is in the squad via a hash-table lookup is like scanning a jersey-number index to confirm MS Dhoni is #7, versus a List<T>.Contains scan checking every player on the team sheet one by one.

Dictionary basics

A Dictionary<TKey, TValue> stores unique keys mapped to values, and both keys and values can be any type. Adding a duplicate key via the indexer (dict[key] = value) overwrites the existing value, while calling Add(key, value) throws ArgumentException if the key already exists. TryGetValue is the idiomatic way to read a value that might not be present, avoiding both a KeyNotFoundException and the cost of checking ContainsKey followed by a separate lookup.

🏏

Cricket analogy: Setting dict[playerName] = runs is like updating Kohli's run tally on a scoreboard app, it just overwrites, while calling Add again for a listed player throws like a scorer refusing a duplicate entry; TryGetValue safely checks a substitute's stats without crashing.

csharp

public readonly record struct ProductCode(string Sku);

var inventory = new Dictionary<ProductCode, int>
{
    [new ProductCode("WIDGET-1")] = 42,
    [new ProductCode("GIZMO-9")] = 7,
};

if (inventory.TryGetValue(new ProductCode("WIDGET-1"), out int quantity))
{
    Console.WriteLine($"In stock: {quantity}");
}

// HashSet<T> — membership testing and de-duplication.
var restockedSkus = new HashSet<string> { "WIDGET-1", "GIZMO-9" };
restockedSkus.Add("WIDGET-1"); // no-op, already present

var lowStock = new HashSet<string>(
    inventory.Where(kvp => kvp.Value < 10).Select(kvp => kvp.Key.Sku));

// Set algebra.
var needsAttention = new HashSet<string>(restockedSkus);
needsAttention.IntersectWith(lowStock);

HashSet<T> and set operations

HashSet<T> stores unique elements with no associated value, essentially a Dictionary<T, bool> conceptually, and is ideal for de-duplication and membership testing. It also exposes true mathematical set operations: UnionWith, IntersectWith, ExceptWith, and SymmetricExceptWith, all of which mutate the set in place and mirror set theory operations you'd find in mathematics or SQL's UNION/INTERSECT/EXCEPT.

🏏

Cricket analogy: A HashSet of century-scorers this season supports UnionWith to combine two teams' centurions, IntersectWith to find players who centuried against both India and Australia, and ExceptWith to find who centuried only against India.

Both types have an Ordered counterpart worth knowing about: SortedDictionary<TKey,TValue> and SortedSet<T> maintain elements in sorted key order (via a red-black tree) at the cost of O(log n) operations instead of O(1), while OrderedDictionary (in newer .NET) preserves insertion order with hash-table performance. Choose these when iteration order matters, not the plain hash-based collections, whose enumeration order is unspecified and should never be relied upon.

The most common bug with dictionaries and sets is using a mutable key type, or a custom type that doesn't correctly override GetHashCode() and Equals(). If a key's hash code changes after it's been inserted (e.g. because a mutable field it derives from changed), the dictionary can no longer find it in its original bucket, effectively 'losing' the entry. Records and readonly structs that implement value-based equality (like ProductCode above) are ideal, safe dictionary keys because their equality and hash are stable and structural.

Choosing the right collection

Use Dictionary<TKey,TValue> whenever you need to associate values with unique keys and look them up frequently by key. Use HashSet<T> when you only care about membership or uniqueness, not an associated value — it uses less memory than a dictionary for the same purpose and communicates intent more clearly. Reach for the Sorted* variants only when you specifically need ordered iteration, since they trade O(1) for O(log n) performance.

🏏

Cricket analogy: Use a Dictionary to map player names to batting averages for frequent lookups, use a HashSet just to track which players have played a Test match this year, and reach for SortedDictionary only when the batting order must be strictly by average.

Dictionary<TKey,TValue> and HashSet<T> use hashing to achieve near-O(1) lookup, insert, and membership checks.
TryGetValue avoids exceptions and double lookups when a key might not exist.
HashSet<T> supports true set algebra: UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith.
Custom key types must correctly and consistently implement GetHashCode() and Equals(), ideally via immutable value types or records.
SortedDictionary/SortedSet maintain order at O(log n) cost; plain hash-based collections have unspecified enumeration order.
Mutating a key's hash-relevant fields after insertion effectively loses the entry inside the hash table.

Practice what you learned

1. Why is Dictionary<TKey,TValue> lookup typically much faster than List<T>.Contains for large collections?

2. What is the safest way to read a value from a Dictionary when the key might not exist?

3. What is the primary risk of using a mutable object as a Dictionary key?

4. Which method on HashSet<T> mutates the set to contain only elements present in both itself and another set?

5. When should you prefer SortedDictionary<TKey,TValue> over Dictionary<TKey,TValue>?

Was this page helpful?

Arrays and Lists

Generics Explained

Related Study Notes in Programming

Browse all study notes

Programming

Apache Spark Study Notes

Programming · 30 topics

Programming

Apache Flink Study Notes

Programming · 30 topics

Programming

Hadoop Study Notes

Programming · 30 topics

Programming

Snowflake Study Notes

Programming · 30 topics

Programming

Apache Airflow Study Notes

Programming · 30 topics

Programming

dbt (Data Build Tool) Study Notes

Programming · 30 topics

Topics covered

#CStudyNotes#Programming#DictionariesAndSets#Dictionaries#Sets#Dictionary#HashSet#DataStructures#StudyNotes#SkillVeris

Dictionaries and Sets