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

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

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);
}

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.