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

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)

The pinned input is [fig, apple, fig, pear, apple, fig]. The diagrams show get-or-default, writeback, and final bucket contents.

Step 1 - First write creates a key

fig is absent, so get-or-default reads 0 and writes fig: 1.

After reading the first word fig.wordold countnew countmapfig01{fig: 1}

Step 2 - Existing keys increment

The second fig reads 1 and writes 2; apple has its own count.

After fig, apple, fig.scanfigapplepearafter fig100after apple110after fig210

Step 3 - Final counts

The full scan produces fig: 3, apple: 2, and pear: 1.

Final map for [fig, apple, fig, pear, apple, fig].bucket/keycountfig3apple2pear1

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.