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

Basic Implementation

basic.rs

use std::collections::HashMap;

fn main() {
    let pairs = [("a", 1), ("b", 2), ("a", 3), ("c", 4), ("b", 5)];
    let mut groups: HashMap<&str, Vec<i32>> = HashMap::new();
    let mut order: Vec<&str> = Vec::new();
    for (key, value) in pairs {
        if !groups.contains_key(key) {
            order.push(key);
        }
        groups.entry(key).or_insert_with(Vec::new).push(value);
    }
    let parts: Vec<String> = order.iter()
        .map(|key| {
            let values = &groups[key];
            let rendered = values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(", ");
            format!("{}: [{}]", key, rendered)
        })
        .collect();
    println!("{{{}}}", parts.join(", "));
}

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.