Group by Key - Bash DSA

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

Basic Implementation

basic.sh

#!/usr/bin/env bash
keys=(a b a c b)
values=(1 2 3 4 5)
declare -A groups=()
order=()
for i in "${!keys[@]}"; do
  key=${keys[$i]}
  value=${values[$i]}
  if [[ -z ${groups[$key]+set} ]]; then
    groups[$key]=$value
    order+=("$key")
  else
    groups[$key]="${groups[$key]}, $value"
  fi
done
parts=()
for key in "${order[@]}"; do
  parts+=("$key: [${groups[$key]}]")
done
joined=""
for part in "${parts[@]}"; do
  if [[ -n "$joined" ]]; then
    joined+=", "
  fi
  joined+="$part"
done
printf '{%s}\n' "$joined"

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.