Hash maps concept

A hash map maps keys to values with average O(1) insert/lookup via a hash function and buckets. C++ std::unordered_map is the standard interview choice for frequency counts and two-sum.

How hashing works (sketch)

1. Hash key → bucket index
2. Store (key, value) in bucket; collisions handled by chaining or open addressing
3. Load factor triggers rehash—amortized O(1)

Typical uses

• Count frequencies
• Store complement for two-sum
• Memoization table in DP

Two-sum with hash map

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 7, 11, 15};
    int target = 9;
    std::unordered_map seen;
    for (int i = 0; i < (int)nums.size(); ++i) {
        int need = target - nums[i];
        if (seen.count(need)) {
            std::cout << seen[need] << ", " << i << "\n";
            break;
        }
        seen[nums[i]] = i;
    }
    return 0;
}

Important interview questions and answers

1. Q: unordered_map vs map?
   A: unordered_map average O(1) hash; map red-black tree O(log n) sorted keys.
2. Q: Worst-case hash?
   A: Many collisions degrade to O(n)—rare with good hash; interviews state average case.

Self-check

1. What is average lookup time for unordered_map?
2. How does two-sum use a hash map?

Tip: Two-sum with unordered_map is the template for O(n) complement lookups.