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 PHP DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.php 
<?php
$pairs = [["a", 1], ["b", 2], ["a", 3], ["c", 4], ["b", 5]];
$groups = [];
foreach ($pairs as [$key, $value]) {
    if (!array_key_exists($key, $groups)) {
        $groups[$key] = [];
    }
    $groups[$key][] = $value;
}
$parts = [];
foreach ($groups as $key => $values) {
    $parts[] = $key . ": [" . implode(", ", $values) . "]";
}
echo "{" . implode(", ", $parts) . "}" . PHP_EOL;
?>

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.
bucket map Each key owns a list. A new key creates a bucket; a repeated key appends to the existing bucket.