unordered_map and unordered_set
Average O(1) lookups, custom hashes for pairs, rehash costs, and when to avoid hashing.
Hash tables in contests
unordered_set<K> and unordered_map<K,V> use hashing for expected O(1) insert, erase, find.
Ideal for: frequency tables, visited marks on large sparse ids, memoization keys, graph adjacency when labels are strings or big integers.
No order: iteration order is unspecified — do not rely on it for output format.
Example — frequency on integers:
unordered_map<int, int> cnt;
for (int x : a) cnt[x]++;
if (cnt[7] >= 2) { /* at least two 7's */ }Example — unordered_set for O(1) membership:
unordered_set<long long> seen;
seen.reserve(1 << 20);
for (long long x : queries) {
if (seen.count(x)) { /* duplicate */ }
seen.insert(x);
}Example — adjacency with hash map (sparse graph):
unordered_map<int, vector<int>> g;
g[u].push_back(v);Hashing pairs and vectors
Default hash exists for common types, not for pair<int,int> on all setups — competitors often use:
Struct hash combining with a large odd multiplier and XOR (splitmix-style), or Boost / policy tricks where allowed.
Safe contest pattern: map pair to long long key: ((long long)a << 32) ^ b if ranges fit — avoid collisions by verifying constraints.
reserve(n) on unordered_map reduces rehashes when you know approximate size.
Example — encode pair<int,int> as one key (when 0 ≤ a,b < 2^20):
auto key = [&](int a, int b) -> long long {
return (long long)a << 32 | (unsigned int)b;
};
unordered_map<long long, int> mp;
mp[key(r, c)] = val;Example — reserve before many inserts:
unordered_map<int, int> freq;
freq.reserve(n * 2); // bucket hint; reduces rehash
for (int i = 0; i < n; i++) freq[a[i]]++;Example — counting pairs (i,j) with hash:
unordered_map<long long, int> edge_cnt;
for (auto [u, v] : edges) {
if (u > v) swap(u, v);
long long k = (long long)u * 1000000007LL + v;
edge_cnt[k]++;
}Worst case and hacking
Adversarial inputs can trigger many collisions → degrades to O(n) per operation on some platforms.
Some judges allow custom hash (randomized seed per program run) to mitigate collision attacks:
struct chash {
size_t operator()(int x) const {
static const size_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return hash<int>{}(x ^ FIXED_RANDOM);
}
};
unordered_map<int,int,chash> mp;Know whether your contest permits this and test locally.
unordered_map vs map
Use unordered_map when you only need fast lookup and iteration order does not matter.
Use map when you need sorted keys or lower_bound on keys.
Memory: hash tables have overhead (buckets); for tiny n, vector or map can be competitive.
Example — same frequency task, two styles:
// Fast average, no order:
unordered_map<string, int> f1;
// Sorted output by key name:
map<string, int> f2;
for (auto& [w, c] : f1) f2[w] = c;
// or just use map from the start if you print sortedExample — unordered_map + vector for stable output order:
vector<string> order;
unordered_map<string, int> cnt;
for (string w : stream) {
if (!cnt[w]++) order.push_back(w); // first time seen
}
for (string w : order) cout << w << " " << cnt[w] << "\n";Complexity
Average: O(1) per operation. Worst: O(n) without mitigation on crafted input.
Rehashing: occasional O(n) work — amortized O(1) under reasonable assumptions.
Complexity Analysis
Time Complexity
O(1) average per operation; O(n) worst case without good hash
Space Complexity
O(n) entries plus bucket overhead
reserve(n) helps; custom hash helps on adversarial contests