Let's revisit a problem from the Arrays module. Remember "Two Sum"? Given an array of numbers, find two numbers that add up to a target.
With just arrays, the naive solution checks every pair - O(n²). You can do better by sorting + two-pointer, but that's still O(n log n).
The question is: can we check "have I seen this value before?" in O(1)?
With an array, no - you'd have to scan the whole thing (O(n)). That's the fundamental limit of arrays: they organize data by position, not by value.
Enter the hash map. It rearranges data so you can look things up by value instead of by index. And it does it in O(1) time on average.
A hash map (also called dictionary, unordered map, or just "map") stores key-value pairs. You give it a key, it gives you the associated value - instantly.
Under the hood, it works like this:
What about collisions? Sometimes two different keys produce the same hash code. The map handles this by storing multiple entries in the same bucket (often using a linked list - we'll talk about those soon). With a good hash function, collisions are rare, so lookups stay O(1) on average.
| Operation | Average | Worst Case |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
The worst case happens when every key hashes to the same bucket - but this almost never happens with a good hash function.
// 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)Most hash map/set problems boil down to one of these three patterns.
// 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;
}Use a hash map (Dictionary/Map) when:
Use a hash set (Set) when:
Use neither when:
Using mutable objects as keys If you modify a key after inserting it into a hash map, you can never look it up again - its hash code has changed. Strings, numbers, and tuples are safe. Lists and custom objects (without proper hash/equality implementations) are not.
"O(1) means it's always instant" O(1) is the average case. In the worst case (all keys collide), it degrades to O(n). With a good hash function, this is extremely rare, but it's worth knowing it exists.
Double lookup anti-pattern
if (map.ContainsKey(key)) return map[key] - this performs TWO hash lookups. Use TryGetValue / .get() with a default instead.
Order is NOT guaranteed across all languages Hash maps and sets generally do not guarantee a particular iteration order (some languages like Python and JavaScript preserve insertion order in their built-in types, but others don't). If you need sorted keys or insertion-order preservation, use sorted/linked variants or check your language's guarantees.
Confusing HashMap with HashSet Ask yourself: do I need to store a value associated with this key (use HashMap), or do I just need to track whether it exists (use HashSet)?
You now have two tools in your toolbox: arrays for ordered, position-based data, and hash maps for O(1) value-based lookups.
But there's a gap. Arrays store elements in contiguous memory, and hash maps internally use an array of buckets — but entries are scattered across those buckets, not stored as a simple contiguous sequence. What if you need to insert or delete at the beginning frequently? With an array, that's O(n) - everything shifts. With a hash map, you generally can't rely on any positional ordering.
That's where Linked Lists come in. They sacrifice random access (indexing) for O(1) insertions and deletions — given you already have a reference to the position. They're also the foundation for more advanced structures like trees and graphs.
Next up: Linked Lists