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

Basic Implementation

basic.c

#include <stdio.h>
#include <string.h>

#define TABLE_SIZE 2
#define MAX_KEYS 5
#define MAX_VALUES 5

typedef struct Entry {
    const char *key;
    int values[MAX_VALUES];
    int value_count;
    struct Entry *next;
} Entry;

static size_t hash_key(const char *key) {
    size_t hash = 0;
    while (*key != '\0') {
        hash = hash * 31u + (unsigned char)*key;
        key++;
    }
    return hash % TABLE_SIZE;
}

static Entry *find_entry(Entry *bucket, const char *key) {
    for (Entry *entry = bucket; entry != NULL; entry = entry->next) {
        if (strcmp(entry->key, key) == 0) {
            return entry;
        }
    }
    return NULL;
}

static Entry *insert_entry(Entry *table[], Entry entries[], int *entry_count, const char *key) {
    size_t bucket = hash_key(key);
    Entry *entry = find_entry(table[bucket], key);
    if (entry != NULL) {
        return entry;
    }

    entry = &entries[*entry_count];
    entry->key = key;
    entry->value_count = 0;
    entry->next = table[bucket];
    table[bucket] = entry;
    (*entry_count)++;
    return entry;
}

static void print_groups(const Entry entries[], int entry_count) {
    printf("{");
    for (int i = 0; i < entry_count; ++i) {
        if (i > 0) {
            printf(", ");
        }
        printf("%s: [", entries[i].key);
        for (int j = 0; j < entries[i].value_count; ++j) {
            if (j > 0) {
                printf(", ");
            }
            printf("%d", entries[i].values[j]);
        }
        printf("]");
    }
    printf("}\n");
}

int main(void) {
    const char *keys[] = {"a", "b", "a", "c", "b"};
    int values[] = {1, 2, 3, 4, 5};
    size_t n = sizeof(values) / sizeof(values[0]);
    Entry entries[MAX_KEYS] = {0};
    Entry *table[TABLE_SIZE] = {0};
    int entry_count = 0;

    for (size_t i = 0; i < n; ++i) {
        Entry *entry = insert_entry(table, entries, &entry_count, keys[i]);
        entry->values[entry->value_count] = values[i];
        entry->value_count++;
    }

    print_groups(entries, entry_count);
    return 0;
}

Complexity

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

Implementation notes

C: this version builds a small separate-chaining hash table from explicit Entry records, bucket heads, and next pointers. TABLE_SIZE is kept small so the canonical input exercises a real collision path instead of a direct-address shortcut.
hash_key() chooses a bucket and strcmp() confirms equality inside the chain. Matching a key and choosing a bucket are separate operations.
Output formatting walks entries in first-seen order, not bucket order, so the printed result stays deterministic while the hash table remains honest.
The trace highlights the grouped 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.

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