C โปรเจกต์: สร้าง hash map



hash map (dictionary) เป็นโครงสร้างข้อมูลที่ C ไม่มีให้ — สร้างเองเพื่อเข้าใจว่ามันทำงานยังไง โปรเจกต์นี้: key เป็น char *, value เป็น int

API

HashMap *map = map_new();
map_set(map, "apple", 3);
map_set(map, "banana", 5);
map_set(map, "apple", 10);      // อัปเดต

int v;
map_get(map, "apple", &v);      // v = 10
map_get(map, "cherry", &v);     // คืน -1 (ไม่มี)

map_delete(map, "banana");
printf("size = %zu\n", map_size(map));

// วนทุก entry
map_foreach(map, print_entry, NULL);

map_free(map);

แนวคิด: separate chaining

buckets:
  [0] ──► ("banana", 5) ──► NULL
  [1] ──► NULL
  [2] ──► ("apple", 10) ──► ("grape", 2) ──► NULL     ← สอง key hash ตรงกัน
  [3] ──► NULL
  ...
  • hash(key) % num_buckets = index ของ bucket
  • แต่ละ bucket เป็น linked list ของ entry ที่ hash ตรงกัน (การชน = collision)
  • ค้นหา: ไป bucket ที่ถูก แล้วเดิน list เทียบ key ด้วย strcmp

hashmap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include <stddef.h>

typedef struct HashMap HashMap;

HashMap *map_new(void);
void     map_free(HashMap *m);

int      map_set(HashMap *m, const char *key, int value);   // 0 = ok, -1 = OOM
int      map_get(const HashMap *m, const char *key, int *out);  // 0 = ok, -1 = ไม่มี
int      map_delete(HashMap *m, const char *key);           // 0 = ลบแล้ว, -1 = ไม่มี
int      map_has(const HashMap *m, const char *key);
size_t   map_size(const HashMap *m);

typedef void (*MapVisitFn)(const char *key, int value, void *ctx);
void     map_foreach(const HashMap *m, MapVisitFn fn, void *ctx);

#endif

hashmap.c

#include "hashmap.h"
#include <stdlib.h>
#include <stdint.h>     // SIZE_MAX
#include <string.h>

#define INITIAL_BUCKETS 16
#define MAX_LOAD_FACTOR 0.75

typedef struct Entry {
    char         *key;       // สำเนาที่ map เป็นเจ้าของ (ดู dup_str)
    int           value;
    struct Entry *next;
} Entry;

// -std=c17 ล้วนไม่มี strdup (เป็น POSIX ไม่ใช่ ISO C) — เขียนเองสั้น ๆ ให้ portable
static char *dup_str(const char *s)
{
    size_t n = strlen(s) + 1;
    char *d = malloc(n);
    if (d) {
        memcpy(d, s, n);
    }
    return d;
}

struct HashMap {
    Entry **buckets;
    size_t  num_buckets;
    size_t  size;            // จำนวน entry
};

// djb2 — hash function ที่ง่ายและกระจายดีพอสำหรับสตริงทั่วไป
static size_t hash_key(const char *key)
{
    size_t hash = 5381;
    for (const unsigned char *p = (const unsigned char *)key; *p; p++) {
        hash = ((hash << 5) + hash) + *p;   // hash * 33 + c
    }
    return hash;
}

HashMap *map_new(void)
{
    HashMap *m = malloc(sizeof(*m));
    if (!m) return NULL;

    m->buckets = calloc(INITIAL_BUCKETS, sizeof(Entry *));   // ทุกไบต์เป็น 0
    if (!m->buckets) {
        free(m);
        return NULL;
    }
    m->num_buckets = INITIAL_BUCKETS;
    m->size = 0;
    return m;
}

void map_free(HashMap *m)
{
    if (!m) return;
    for (size_t i = 0; i < m->num_buckets; i++) {
        Entry *e = m->buckets[i];
        while (e) {
            Entry *next = e->next;      // เก็บ next ก่อน free
            free(e->key);               // free key ที่ strdup ไว้
            free(e);
            e = next;
        }
    }
    free(m->buckets);
    free(m);
}

// ขยายตาราง 2 เท่า แล้ว rehash ทุก entry
static int map_resize(HashMap *m, size_t new_num_buckets)
{
    Entry **new_buckets = calloc(new_num_buckets, sizeof(Entry *));
    if (!new_buckets) return -1;

    for (size_t i = 0; i < m->num_buckets; i++) {
        Entry *e = m->buckets[i];
        while (e) {
            Entry *next = e->next;
            size_t idx = hash_key(e->key) % new_num_buckets;
            e->next = new_buckets[idx];     // ย้าย e ไปหัว bucket ใหม่
            new_buckets[idx] = e;
            e = next;
        }
    }

    free(m->buckets);
    m->buckets = new_buckets;
    m->num_buckets = new_num_buckets;
    return 0;
}

static Entry *find_entry(const HashMap *m, const char *key, size_t *out_idx)
{
    size_t idx = hash_key(key) % m->num_buckets;
    if (out_idx) *out_idx = idx;

    for (Entry *e = m->buckets[idx]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            return e;
        }
    }
    return NULL;
}

int map_set(HashMap *m, const char *key, int value)
{
    size_t idx;
    Entry *existing = find_entry(m, key, &idx);
    if (existing) {
        existing->value = value;           // อัปเดต
        return 0;
    }

    // ขยายถ้า load factor สูงเกิน
    if ((double)(m->size + 1) / m->num_buckets > MAX_LOAD_FACTOR) {
        if (m->num_buckets > SIZE_MAX / 2) return -1;
        if (map_resize(m, m->num_buckets * 2) != 0) return -1;
        idx = hash_key(key) % m->num_buckets;   // idx เปลี่ยนหลัง resize
    }

    Entry *e = malloc(sizeof(*e));
    if (!e) return -1;

    e->key = dup_str(key);                 // สำเนา key — ผู้เรียกไม่ต้องรักษา key ไว้
    if (!e->key) {
        free(e);
        return -1;
    }
    e->value = value;
    e->next = m->buckets[idx];             // เพิ่มที่หัว bucket
    m->buckets[idx] = e;
    m->size++;
    return 0;
}

int map_get(const HashMap *m, const char *key, int *out)
{
    Entry *e = find_entry(m, key, NULL);
    if (!e) return -1;
    *out = e->value;
    return 0;
}

int map_has(const HashMap *m, const char *key)
{
    return find_entry(m, key, NULL) != NULL;
}

int map_delete(HashMap *m, const char *key)
{
    size_t idx = hash_key(key) % m->num_buckets;
    Entry *e = m->buckets[idx];
    Entry *prev = NULL;

    while (e) {
        if (strcmp(e->key, key) == 0) {
            if (prev) prev->next = e->next;
            else      m->buckets[idx] = e->next;
            free(e->key);
            free(e);
            m->size--;
            return 0;
        }
        prev = e;
        e = e->next;
    }
    return -1;
}

size_t map_size(const HashMap *m) { return m->size; }

// callback ห้ามแก้/ลบ/free map ระหว่าง iteration — จะทำให้ pointer ภายในใช้ต่อไม่ได้
void map_foreach(const HashMap *m, MapVisitFn fn, void *ctx)
{
    for (size_t i = 0; i < m->num_buckets; i++) {
        for (Entry *e = m->buckets[i]; e; e = e->next) {
            fn(e->key, e->value, ctx);
        }
    }
}

เราเขียน dup_str เองแทน strdup เพราะ strdup เป็น POSIX ไม่ใช่ ISO C17 (เพิ่งเข้ามาตรฐานใน C23) — คอมไพล์ด้วย -std=c17 ล้วนจะไม่เห็น prototype ถ้าจะใช้ strdup ต้อง #define _POSIX_C_SOURCE 200809L ก่อน #include ทุกตัว หรือคอมไพล์ด้วย -std=gnu17

calloc ล้าง ไบต์เป็น 0 ทุกตัว — บนแพลตฟอร์มหลัก ๆ ทั้งหมด (x86, ARM, …) all-zero-bits ก็คือ null pointer จึงใช้ตั้ง bucket เป็น NULL ได้ แต่ ISO C ไม่รับประกันว่า “ทุกบิตเป็น 0” = null pointer เสมอไป ถ้าต้องพกไปทุกสถาปัตยกรรมจริง ๆ ให้วนตั้ง buckets[i] = NULL เอง (ทั้งตอนสร้างและ resize)

ตัวอย่างใช้งาน: นับความถี่ของคำ

#include "hashmap.h"
#include <stdio.h>
#include <ctype.h>
#include <limits.h>   // INT_MAX

static void print_entry(const char *key, int value, void *ctx)
{
    (void)ctx;
    printf("%-15s %d\n", key, value);
}

int main(void)
{
    HashMap *counts = map_new();
    if (!counts) return 1;

    char word[128];
    int rc = 0;
    while (scanf("%127s", word) == 1) {
        for (char *p = word; *p; p++) *p = (char)tolower((unsigned char)*p);

        int c = 0;
        map_get(counts, word, &c);        // c = 0 ถ้าไม่มี (map_get คืน -1 แต่ c ไม่ถูกแตะ — init 0)
        if (c == INT_MAX) {               // นับต่อไม่ได้แล้ว
            fprintf(stderr, "'%s' ถึงเพดานการนับ\n", word);
            continue;
        }
        if (map_set(counts, word, c + 1) != 0) {   // OOM — อย่าเงียบ
            fprintf(stderr, "หน่วยความจำไม่พอ\n");
            rc = 1;
            break;
        }
    }

    printf("คำไม่ซ้ำ: %zu\n\n", map_size(counts));
    map_foreach(counts, print_entry, NULL);

    map_free(counts);
    return rc;
}

scanf("%127s", ...) จำกัด buffer ถูกต้อง แต่คำที่ยาวเกิน 127 ตัวจะถูกตัดเป็นหลายคำ (อ่าน 127 ตัว แล้วรอบถัดไปอ่านที่เหลือเป็นคำใหม่) ถ้าต้องแม่นยำ ให้อ่านทีละตัวอักษรเองแล้วขยาย buffer หรือข้ามคำที่ยาวเกินไปทั้งคำ อย่านับมันเป็นสองคำ

gcc -std=c17 -Wall -Wextra -g -fsanitize=address,undefined wordcount.c hashmap.c -o wc
echo "the cat sat on the mat the cat" | ./wc
คำไม่ซ้ำ: 5

the             3
cat             2
sat             1
on              1
mat             1

ลำดับที่ map_foreach เดินออกมา ไม่รับประกัน — ขึ้นกับ hash และขนาดตาราง เครื่องคุณอาจได้คนละลำดับ ถ้าต้องการผลเรียง ให้เก็บ entry ลงอาร์เรย์แล้ว qsort ก่อนพิมพ์

เทสต์

#include "test.h"
#include "hashmap.h"
#include <stdio.h>     // snprintf

int main(void)
{
    TEST("hashmap");
    HashMap *m = map_new();
    int v;

    CHECK_EQ_INT(map_get(m, "x", &v), -1);
    CHECK_EQ_INT(map_set(m, "one", 1), 0);
    CHECK_EQ_INT(map_set(m, "two", 2), 0);
    CHECK_EQ_INT(map_get(m, "one", &v), 0);
    CHECK_EQ_INT(v, 1);

    CHECK_EQ_INT(map_set(m, "one", 100), 0);   // อัปเดต
    map_get(m, "one", &v);
    CHECK_EQ_INT(v, 100);
    CHECK_EQ_INT(map_size(m), 2);              // ไม่เพิ่ม

    // ใส่เยอะ ๆ เพื่อ trigger resize
    char key[16];
    for (int i = 0; i < 1000; i++) {
        snprintf(key, sizeof(key), "k%d", i);
        CHECK_EQ_INT(map_set(m, key, i), 0);
    }
    CHECK_EQ_INT(map_size(m), 1002);
    map_get(m, "k500", &v);
    CHECK_EQ_INT(v, 500);

    CHECK_EQ_INT(map_delete(m, "two"), 0);
    CHECK_EQ_INT(map_has(m, "two"), 0);
    CHECK_EQ_INT(map_delete(m, "two"), -1);

    map_free(m);
    TEST_SUMMARY();
}

ยังไม่ครอบคลุม: allocation failure, การถือ ownership ของ key หลังผู้เรียกแก้ buffer เดิม, map_foreach, และ collision แบบเจาะจง (สอง key ที่ hash % n ตรงกัน) เทสต์ที่ผ่านหมดไม่ใช่หลักฐานว่าไม่มีบั๊ก

เรื่องที่คนมักพลาด

  • ไม่ทำสำเนา key — เก็บ pointer ที่ผู้เรียกให้มาตรง ๆ ผู้เรียกแก้/free แล้ว key ในตาราง dangling
  • map_free ไม่ free e->key — leak ทุก key (ASan จับได้)
  • ลืม rehash หลัง resize — entry อยู่ bucket ผิด map_get หาไม่เจอ
  • hash_key คืน int แล้ว % num_buckets เมื่อ hash เป็นค่าลบ — index ติดลบ ใช้ size_t
  • calloc แล้วคิดว่า bucket เป็นขยะ — calloc ล้างไบต์เป็น 0 (= NULL บนทุกแพลตฟอร์มหลัก) ถ้าต้อง portable แบบ ISO เป๊ะ วนตั้ง = NULL เอง
  • load factor สูงมาก ไม่ resize — ทุก bucket ยาว ค้นหาช้าเป็น O(n)
  • find_entry เดิน list โดยไม่เทียบ strcmp — hash ตรงกันไม่ได้แปลว่า key เดียวกัน (collision)

สรุป

  • hash map: อาร์เรย์ของ bucket, hash(key) % n = index, แต่ละ bucket = linked list (separate chaining)
  • djb2: hash = hash * 33 + c — ง่ายและกระจายพอใช้; คืน size_t
  • collision: เดิน list เทียบ key ด้วย strcmp (hash ตรง ≠ key เดียวกัน)
  • resize เมื่อ size / num_buckets > 0.75 — ขยาย 2 เท่า + rehash ทุก entry
  • ownership: ทำสำเนา key ตอน set (dup_str — strdup เป็น POSIX ไม่ใช่ ISO C), free(e->key) + free(e) ตอน delete/free
  • map_free: เดินทุก bucket, เก็บ next ก่อน free

บทสุดท้าย โปรเจกต์ mini shell — fork/exec/wait, built-in command