Hash Tables

Group by Key

Build buckets keyed by a shared field, preserving the first-seen key order.

Algorithm

Canonical pairs (a,1), (b,2), (a,3), (c,4), (b,5) print {a: [1, 3], b: [2, 5], c: [4]}. The replay uses the same input in every language, so this SQL DSA implementation can be compared directly with the rest of the DSA track.

bucket map Each key owns a list. A new key creates a bucket; a repeated key appends to the existing bucket.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
WITH pairs(ord, key, value) AS (
  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
),
grouped AS (
  SELECT key, GROUP_CONCAT(value, ', ') AS values_text, MIN(ord) AS first_ord
  FROM (SELECT * FROM pairs ORDER BY ord)
  GROUP BY key
)
SELECT '{' || GROUP_CONCAT(key || ': [' || values_text || ']', ', ') || '}'
FROM (SELECT * FROM grouped ORDER BY first_ord);

  1. pairs ← [(a, 1), (b, 2), (a, 3), (c, 4), (b, 5)]

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step[(a, 1), (b, 2), (a, 3), (c, 4), (b, 5)]pairs

  2. groups ← {}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{}groups

  3. groups ← {a: [1]}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{} → {a: [1]}groupsakey1value

  4. groups ← {a: [1], b: [2]}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{a: [1]} → {a: [1], b: [2]}groupsbkey2value

  5. groups ← {a: [1, 3], b: [2]}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{a: [1], b: [2]} → {a: [1, 3], b: [2]}groupsakey3value

  6. groups ← {a: [1, 3], b: [2], c: [4]}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{a: [1, 3], b: [2]} → {a: [1, 3], b: [2], c: [4]}groupsckey4value

  7. groups ← {a: [1, 3], b: [2, 5], c: [4]}

    1WITH pairs(ord, key, value) AS (2  VALUES (1, 'a', 1), (2, 'b', 2), (3, 'a', 3), (4, 'c', 4), (5, 'b', 5)
    values this step{a: [1, 3], b: [2], c: [4]} → {a: [1, 3], b: [2, 5], c: [4]}groupsbkey5value

  8. stdout ← {a: [1, 3], b: [2, 5], c: [4]}

    4grouped AS (5  SELECT key, GROUP_CONCAT(value, ', ') AS values_text, MIN(ord) AS first_ord6  FROM (SELECT * FROM pairs ORDER BY ord)
    values this step{a: [1, 3], b: [2, 5], c: [4]}stdout{a: [1, 3], b: [2, 5], c: [4]}groups

  9. bucket 1 after collision ← c -> a, degradation risk ← long chains can degrade lookup toward O(n)

    4grouped AS (5  SELECT key, GROUP_CONCAT(value, ', ') AS values_text, MIN(ord) AS first_ord6  FROM (SELECT * FROM pairs ORDER BY ord)
    values this stepa → c -> abucket 1 after collisionlong chains can degrade lookup toward O(n)degradation riskresize or rehash when load factor growsmitigationcnew key

Complexity

  • Time: O(n) average
  • Space: O(k + n) for buckets and values

Implementation notes

  • Keep output formatting deterministic. Do not rely on unordered hash-map printing when the lesson needs cross-language comparison.
  • The trace highlights the hash table state after each write and includes a collision contrast where one bucket chain grows, showing why long chains can degrade lookup and why real tables resize or rehash.