Know this before you start: “Count frequencies with a hash map”
Counting with a hash map
A hash map (dict) stores key → value with O(1) lookups. Use the item as the key and how many times you've seen it as the value.
The idea
A hash map remembers pairs: a key and its value. Looking a key up, adding one, or changing its value takes O(1) on average, because the key's hash tells the map exactly where to look.
Counting is its most common job: walk the input once and add 1 to the count of each item. Afterwards you can answer “how many times does x appear?” instantly.
Python's dict does this with counts.get(x, 0) + 1, and collections.Counter does the whole thing in one line.
See it step by step
Count the letters of “banana”
- b → {b: 1}
- a → {b: 1, a: 1}; n → {b: 1, a: 1, n: 1}
- a → a: 2; n → n: 2; a → a: 3
- Final: {b: 1, a: 3, n: 2}. Now “is this an anagram?” or “what's most common?” is easy.
In code (Python)
from collections import Counter
def counts(items):
seen = {}
for x in items:
seen[x] = seen.get(x, 0) + 1
return seen
print(counts("banana")) # {'b': 1, 'a': 3, 'n': 2}
print(Counter("banana") == Counter("nabana")) # True: same letters, same countsO(n) time to count n items, O(k) space for k distinct items.
When you'll use it
- Anagrams, “most frequent”, “appears more than n / 2 times”, duplicates.
- Any time you'd otherwise count by scanning the list again and again.
Common mistakes
- Reading counts[x] for a key that isn't there (KeyError): use .get(x, 0).
- Sorting to count (O(n log n)) when a map does it in O(n).
