// ============================================================
// 通用哈希表：字符串 → 字符串数组
// 你只需要这三个操作：
//   hmap_put(h, key, val)      — key 的所有权交给表
//   hmap_size(h)               — 返回组数
//   hmap_extract(h, out, cols) — 把结果搬出来
// ============================================================

#define HM_CAP 10007  // 质数

static unsigned long hm_hash(const char* s) {
    unsigned long h = 5381;
    while (*s) h = h * 33 + *s++;
    return h % HM_CAP;
}

typedef struct HNode {
    char*  key;
    char** vals;
    int    len, cap;
    struct HNode* next;
} HNode;

typedef struct { HNode* b[HM_CAP]; } HMap;

// ── put ──────────────────────────────────────────────────────
static void hmap_put(HMap* m, char* key, char* val) {
    int i = (int)hm_hash(key);
    HNode* cur = m->b[i];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (cur->len == cur->cap) {
                cur->cap = cur->cap ? cur->cap * 2 : 4;
                cur->vals = realloc(cur->vals, cur->cap * sizeof(char*));
            }
            cur->vals[cur->len++] = val;
            return;
        }
        cur = cur->next;
    }
    HNode* n = malloc(sizeof(HNode));
    n->key = key; n->len = 0; n->cap = 4;
    n->vals = malloc(4 * sizeof(char*));
    n->vals[n->len++] = val;
    n->next = m->b[i];
    m->b[i] = n;
}

// ── size ─────────────────────────────────────────────────────
static int hmap_size(HMap* m) {
    int n = 0;
    for (int i = 0; i < HM_CAP; i++)
        for (HNode* c = m->b[i]; c; c = c->next) n++;
    return n;
}

// ── extract（搬数据 + 释放节点） ──────────────────────────────
static void hmap_extract(HMap* m, char*** out, int* cols) {
    int p = 0;
    for (int i = 0; i < HM_CAP; i++) {
        HNode* c = m->b[i];
        while (c) {
            out[p]   = c->vals;    // 直接接管数组
            cols[p]  = c->len;
            p++;
            HNode* t = c;
            c = c->next;
            free(t->key);
            free(t);
        }
    }
}

说实话，要求用一门没有哈希表的语言机考有点太难受了，感觉不得不背下来……