Hash Tables

Hash Frequency Count

Count how many times each word appears in a list while preserving the insertion order of first appearances. The output is a dict-style line with the first-seen ordering.

Algorithm

Basic Implementation

basic.sql 
.mode list
.headers off
CREATE TABLE words(pos INTEGER PRIMARY KEY, word TEXT);
INSERT INTO words(pos, word) VALUES
  (0, 'fig'), (1, 'apple'), (2, 'fig'), (3, 'pear'),
  (4, 'apple'), (5, 'fig');

WITH first_seen AS (
  SELECT word, MIN(pos) AS first_pos FROM words GROUP BY word
),
counts AS (
  SELECT w.word AS word, COUNT(*) AS n, fs.first_pos AS first_pos
  FROM words w JOIN first_seen fs ON fs.word = w.word
  GROUP BY w.word, fs.first_pos
)
SELECT '{' || GROUP_CONCAT(word || ': ' || n, ', ') || '}'
FROM (SELECT word, n FROM counts ORDER BY first_pos);

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)
  • Space: O(k) for k distinct keys

Implementation notes

  • SQL: the input is staged in words(pos, word). A first_seen CTE computes MIN(pos) per word — that is the first-appearance index that drives the final ordering — and a paired counts CTE produces the running tally with COUNT(*).
  • Joining counts ordered by first_pos and wrapping it in GROUP_CONCAT(word || ': ' || n, ', ') reproduces the canonical {fig: 3, apple: 2, pear: 1} dict-style line shared by every other DSA book in the cohort.
  • A bare GROUP BY word ORDER BY COUNT(*) DESC would print the same counts but lose the first-seen ordering the lesson is teaching; the explicit first_seen CTE keeps that contract visible in the source.
tally Sum one per occurrence of each key.
first-seen ordering The output order is the order in which each key first appeared in the input, not the alphabetical order of the keys.