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[key] ?? 0 pattern.

Algorithm

Basic Implementation

basic.dart 
void main() {
  final words = <String>['fig', 'apple', 'fig', 'pear', 'apple', 'fig'];
  final count = <String, int>{};
  for (final word in words) {
    count[word] = (count[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

  • Dart: use the null-aware (count[word] ?? 0) + 1 for the canonical lesson. The Map.update / putIfAbsent shortcuts would hide the get-or-default pattern the lesson is teaching. Map<String, int> literal {} preserves insertion order, so the printed map matches the spec's first-seen ordering.
  • 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[word] ?? 0)` returns 0 when the key is absent.