Hashing

Concept

Hashing maps keys to indices for O(1) average-case lookup, insertion, and deletion. In C++, unordered_map and unordered_set use hash tables internally. The most common competitive programming use is frequency counting — counting how many times each element appears in O(n).

When to Use

  • ▸Frequency counting (how many times does each element appear?)
  • ▸Checking if an element exists in a set in O(1)
  • ▸Two-sum problem (complement lookup)
  • ▸Counting distinct elements
  • ▸Grouping elements by some property

Intuition

A hash table is like a dictionary with instant lookup. Give it a key, it tells you the value immediately (on average). For frequency counting, walk through the array once and increment a counter for each element. For two-sum, store each number's index in a map, then for each number check if (target - number) exists. Both patterns turn O(n^2) brute force into O(n).

Complexity

Time
O(1) average per operation, O(n) worst case
Space
O(n)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- Frequency Counting ---
    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    unordered_map<int, int> cnt;
    for(int x : v){
        cnt[x]++;
    }

    for(auto &[key, val] : cnt){
        cout << key << ": " << val << "\n";
    }

    // --- Check Existence with unordered_set ---
    unordered_set<int> s(v.begin(), v.end());
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        if(s.count(x)) cout << "YES\n";
        else cout << "NO\n";
    }

    // --- Two Sum (find pair with given sum) ---
    // int target;
    // cin >> target;
    // unordered_map<int, int> seen;
    // for(int i = 0; i < n; i++){
    //     int comp = target - v[i];
    //     if(seen.count(comp)){
    //         cout << seen[comp] << " " << i << "\n";
    //         break;
    //     }
    //     seen[v[i]] = i;
    // }

    // --- map vs unordered_map ---
    // map<int, int>          — sorted keys, O(log n) per op
    // unordered_map<int, int> — unsorted, O(1) avg per op
    // set<int>               — sorted unique, O(log n) per op
    // unordered_set<int>     — unsorted unique, O(1) avg per op

    return 0;
}

// Sample Input:
// 7
// 3 1 2 3 1 3 2
// 3
// 3
// 5
// 1
//
// Sample Output (frequency):
// 2: 2
// 1: 2
// 3: 3
// YES
// NO
// YES