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);
#endifhashmap.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ไม่ freee->key— leak ทุก key (ASan จับได้)- ลืม rehash หลัง resize — entry อยู่ bucket ผิด
map_getหาไม่เจอ hash_keyคืนintแล้ว% num_bucketsเมื่อ hash เป็นค่าลบ — index ติดลบ ใช้size_tcallocแล้วคิดว่า 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