unordered-map-frequency

An unordered map (hash map) for frequency counting uses std::unordered_map<Key, int> where each key is an element from the input and the mapped value is its occurrence count. Unlike a frequency array, the map only stores entries for elements that actually appear, and keys can be of any hashable type.

When the character range is unknown, large, or non-contiguous (e.g., mixed case, digits, Unicode), a frequency array becomes impractical. An unordered_map<char, int> stores only the characters that actually appear, with no ASCII math needed — freq[ch] works directly. The tradeoff is hashing overhead, potential collisions, and non-deterministic iteration order.

1. Declare unordered_map<char, int> freq
2. Iterate through the string: for(char ch : s) { freq[ch]++; }
3. The map automatically creates new key-value pairs for new characters
4. To query: iterate key-value pairs or check specific keys
5. No conversion needed — character is used as the key directly

• Average O(1) insertion and lookup (amortized, may degrade to O(n) with collisions)
• Only stores distinct elements — memory proportional to unique characters, not domain size
• Keys can be any hashable type: char, string, int, long long
• No ch - 'a' conversion needed — eliminates ASCII math entirely
• Iteration order is unspecified and non-deterministic

• Built from: Hash Map Flexibility — unordered_map supports diverse key types
• Built from: Hash Collision Overhead — the performance tradeoff of hash maps
• Builds into: Two-Phase Hashing Paradigm — maps are one implementation choice for Phase 1
• Builds into: Anagram Detection — maps are ideal when character set is unknown
• Contrasts with: Frequency Array — array is faster for small known ranges; map is more flexible
• Related: ASCII Math Elimination — maps eliminate the need for index conversion

• freq[ch]++ creates an entry with value 0 if the key does not exist, then increments — no manual insertion needed
• Repeated insertions may trigger rehashing, which is O(n) amortized but can be a latency spike
• unordered_map is not ordered — if you need sorted output, use map (O(log n) per operation) or sort the result
• For small datasets (like lowercase-only strings), a map is slower than a frequency array despite both being O(1) — the constant factors matter
• Memory per entry is higher than an array slot due to key storage, hash table overhead, and pointer chains