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 — 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)Use Dictionary when:
Use HashSet when:
Use neither when:
// 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;
}