HashMaps & Sets

beginner4 problems· Prerequisites: Big O & Complexity, Arrays & Strings

How Hashing Works

A hash map (dictionary) stores key-value pairs. The key is hashed to compute an index into an internal array (buckets). Collisions (two keys hashing to the same index) are handled via separate chaining (linked list per bucket) or open addressing.

Operation	Average	Worst Case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

The worst case occurs when all keys collide (rare with a good hash function).

Dictionary and HashSet basicsC#

// Dictionary - key-value pairs
var dict = new Dictionary<string, int>();
dict["apple"] = 5;
dict["banana"] = 3;

// SAFE lookup - TryGetValue (avoids double lookup)
if (dict.TryGetValue("apple", out int count))
    Console.WriteLine(count); // 5

// ContainsKey + [] is TWO lookups - avoid this:
if (dict.ContainsKey("apple"))          // lookup 1
    Console.WriteLine(dict["apple"]);   // lookup 2

// HashSet - unique values
var set = new HashSet<int> { 1, 2, 3 };
set.Add(3);  // false - already exists
set.Contains(2); // true - O(1)

Key Patterns

These three patterns cover the majority of hash map / hash set interview problems.

Common patternsC#

// 1. Counting frequencies
int[] nums = { 1, 2, 2, 3, 3, 3 };
var counts = new Dictionary<int, int>();
foreach (var n in nums) {
    if (counts.TryGetValue(n, out int val))
        counts[n] = val + 1;
    else
        counts[n] = 1;
}

// 2. Deduplication
int[] duplicates = { 1, 2, 2, 3, 3, 3 };
var unique = new HashSet<int>(duplicates); // { 1, 2, 3 }

// 3. Two Sum pattern - complement lookup
bool HasPairSum(int[] arr, int target) {
    var seen = new HashSet<int>();
    foreach (var n in arr) {
        if (seen.Contains(target - n)) return true;
        seen.Add(n);
    }
    return false;
}

When to Use HashMaps vs Sets

Use Dictionary when:

You need to associate values with keys (counts, indices, cached results)
You need to quickly look up data by a key

Use HashSet when:

You only need to track presence/absence (deduplication)
You need fast membership testing

Use neither when:

Order matters (use List or SortedDictionary)
You need range queries (use tree-based structures)

Common Mistakes / Gotchas

Using mutable objects as keys If you modify a key after inserting it, you can never look it up again. Strings, numbers, and tuples are safe. Lists and objects are not.

"O(1) lookup means it's always instant" O(1) is the average case. Worst case (hash collisions) degrades to O(n). With a good hash function this is extremely rare.

Double lookup anti-pattern if (map.ContainsKey(key)) return map[key] is TWO hash lookups. Use TryGetValue / get() with a default instead.

HashSet vs HashMap confusion Use HashSet when you only need membership checks. Use HashMap when you need to associate values with keys (counts, indices, etc.).

Order is NOT guaranteed Hash maps and hash sets have no defined iteration order. If order matters, use a LinkedHashMap or TreeMap.

Common Interview Patterns

Frequency counter - count occurrences of each element
Complement lookup - store seen values and check for target - current
Deduplication - remove duplicates via HashSet
Two-pass - first pass builds map, second pass uses it
Sliding window with set - track unique characters in window