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.

Algorithm

Basic Implementation

basic.js 
const words = ["fig", "apple", "fig", "pear", "apple", "fig"];
const count = new Map();
for (const word of words) {
    count.set(word, (count.get(word) || 0) + 1);
}
console.log(JSON.stringify(Object.fromEntries(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) where k is the number of distinct keys

Implementation notes

  • JavaScript: const count = new Map(); with count.set(word, (count.get(word) || 0) + 1). A plain object literal works too, but Map preserves insertion order explicitly.
  • The replay renders the map as a list of key/value rows and animates the count increment on each frame.
get-or-default `count.get(word) || 0` returns the current count or `0`. Adding one and writing back via `count.set` is the canonical pattern.