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

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

Basic Implementation

Basic.java 
import java.util.HashMap;
import java.util.Map;

public class Basic {
    public static void main(String[] args) {
        String[] words = {"fig", "apple", "fig", "pear", "apple", "fig"};
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }
        System.out.println(count);
    }
}

Complexity

  • Time: O(n) average
  • Space: O(k) where k is the number of distinct keys

Implementation notes

  • Java: Map<String, Integer> count = new HashMap<>(); with count.put(word, count.getOrDefault(word, 0) + 1). The count.merge(word, 1, Integer::sum) form is equally idiomatic but hides the read; the explicit form is used here so the lesson stays about the get-then-write idea.
  • The replay renders the map as a list of key/value rows and animates the count increment on each frame.
get-or-default `count.getOrDefault(word, 0)` returns the current count or `0`. Adding one and writing back is the canonical pattern.