Hash Tables

Frequency Count

Walk a sequence and count occurrences of each value in a hash map. Classic "get current count, add one, write back" loop. The canonical lesson for the count.get(key, 0) + 1 pattern.

Algorithm

Canonical input ["fig", "apple", "fig", "pear", "apple", "fig"] produces the final map {fig: 3, apple: 2, pear: 1}.

Basic Implementation

basic.py 
words = ["fig", "apple", "fig", "pear", "apple", "fig"]
count = {}
for word in words:
    count[word] = count.get(word, 0) + 1
print(count)

Complexity

  • Time: O(n) average
  • Space: O(k) for k distinct keys

Implementation notes

  • Python: use count.get(word, 0) + 1 for the canonical lesson. The optional collections.Counter shortcut hides the get-or-default pattern.
  • The replay shows the current word, its count before the update, and the full hash-map state after the write, matching the lesson spec.
get or default `count.get(word, 0)` returns 0 when the key is absent.