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.cpp 
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

int main() {
    std::vector<std::string> words = {"fig", "apple", "fig", "pear", "apple", "fig"};
    std::unordered_map<std::string, int> count;
    std::vector<std::string> seen;
    for (const std::string& word : words) {
        if (count.find(word) == count.end()) {
            seen.push_back(word);
        }
        count[word] = count[word] + 1;
    }
    std::cout << "{";
    for (size_t i = 0; i < seen.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << seen[i] << ": " << count[seen[i]];
    }
    std::cout << "}" << std::endl;
    return 0;
}

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

  • C++: std::unordered_map<std::string, int> is the canonical hash table. Indexing with count[word] default-initialises to 0, which is exactly the "get current count" half of the lesson.
  • The seen vector keeps the lesson's first-seen iteration order honest; std::unordered_map deliberately does not promise insertion order, and the lesson should not pretend otherwise.
  • The replay renders the map as a list of key/value rows in first-seen order and animates the count increment on each frame.
get-or-default `count[word]` returns the current count or default-initialises to `0`. Adding one in place is the canonical pattern.
first-seen order A small `std::vector<std::string> seen` records each key the first time it appears so the final printout is deterministic without exposing the hash-map's bucket order.