Day 13：Hash Table（Table）：bucket／雜湊／衝突策略取捨

延續 Day 12 的 mongory_array，筆者今天帶讀者把 mongory_table 的設計一次講清楚：bucket 與雜湊、碰撞（separate chaining）如何處理、何時 rehash、以及對外 API（get/set/del/each_pair）與慣用的 keys 輔助

設計目標與總覽

• 字串鍵（key）→ 值（mongory_value*）的雜湊表
• 初始 bucket 數量為質數（17）以降低碰撞機率
• 負載因子超標（0.75）時 rehash，擴容後重新安排 bucket
  • 負載因子：目前的數量(size)與最大容量(capacity)的佔比
• 碰撞採 separate chaining（每個 bucket 以 linked nodes 儲存）
• 配合記憶體池：節點與 key 字串統一由 pool 管理，不做逐一 free

Bucket 與雜湊策略

• 雜湊函式：djb2（hash = hash*33 + c）對應 hash_string
• bucket 容器：內部使用 mongory_array(直接復用自己的東西)
• index 使用 hash(key) % capacity 對 key 算出 hash 值後對 bucket 的數量(capacity）取餘數，以確定不會超出 bucket length
• initial capacity：17（質數），有助降低碰撞週期性
• separate chaining：每個 bucket 是 mongory_table_node* 的 linked nodes

碰撞處理與 CRUD

• 新增/更新（set）：
  • 命中同 key → 就地更新 value
  • 未命中 → 建立新節點，頭插入 bucket 串列（O(1)）
  • key 會以 mongory_string_cpy 複製一份進 pool，避免外部字串生命週期問題
• 讀取（get）：沿 bucket 串列比對字串，命中即回傳值，否則 NULL
• 刪除（del）：沿 bucket 串列步進，從鏈上移除節點（頭節點或中間）

何時 rehash（倍增到下一個質數）

• 規則：count > capacity * 0.75 時觸發
• 作法：
  1. 以 next_prime(capacity * 2) 找出下一個質數，以計算新容量
  2. 針對舊 bucket 陣列逐桶走訪，把每個節點重新以新容量計算 index 並前插入新 bucket
  3. 陣列本身以 mongory_array_resize 擴容，節點記憶體不搬家，只改鏈結
• 風險與取捨：
  • rehash 為 O(n)，但不頻繁，攤銷成本低
  • 若擴容失敗會寫入 pool->error，表仍可運作，但效能可能退化（維持高 load factor）

對外 API（物件風）

• mongory_table_new(pool)：建立表，內部建立 bucket 陣列並填 NULL
• table->set(table, key, value)：新增或更新
• table->get(table, key)：查詢，未命中回 NULL
• table->del(table, key)：刪除，回傳是否成功
• table->each(table, acc, callback)：逐對（key, value）走訪，callback(key, value, acc)，回傳 false 可提前終止
• mongory_table_merge(table, other)：以 other 的鍵值覆寫/補齊 table

最小可執行範例（C）

插入、查詢、刪除與列舉：

#include <mongory-core/foundations/memory_pool.h>
#include <mongory-core/foundations/table.h>
#include <mongory-core/foundations/value.h>
#include <stdio.h>

static bool print_pair(char *key, mongory_value *value, void *acc) {
  mongory_memory_pool *pool = (mongory_memory_pool *)acc;
  char *vs = value->to_str(value, pool);
  printf("%s => %s\n", key, vs);
  return true;
}

int main() {
  mongory_init();
  mongory_memory_pool *pool = mongory_memory_pool_new();

  mongory_table *t = mongory_table_new(pool);
  t->set(t, "name",  mongory_value_wrap_str(pool, "Jack"));
  t->set(t, "age",   mongory_value_wrap_int(pool, 18));
  t->set(t, "score", mongory_value_wrap_int(pool, 90));

  // 更新
  t->set(t, "score", mongory_value_wrap_int(pool, 95));

  // 查詢
  mongory_value *age = t->get(t, "age");
  printf("age=%lld\n", age->data.i64);

  // 列舉
  t->each(t, pool, print_pair);

  // 刪除
  t->del(t, "name");

  mongory_memory_pool_free(pool);
  mongory_cleanup();
  return 0;
}

資料一致性與序列化

• 一致性：set 會複製 key 到 pool，外部修改原字串不影響表內 key
• 生命週期：節點與 key 都由 pool 管理，刪除只調整鏈結，不回收個別節點，整體在 pool_free 時一次回收
• 序列化：
  • 以 table->each 走訪即可輸出（例如轉 JSON）
  • mongory_value->to_str 可協助把值轉可讀字串

複雜度與取捨

• 平均 get/set/del 為 O(1)，最壞落到 O(n)（單 bucket 長鏈）
• rehash 為 O(n)，以 0.75 作為觸發線可兼顧空間與速度
• 使用質數容量可減少碰撞週期性與模數偏差

測試清單（Unity）

• set/get/del：命中/未命中、覆寫更新、頭/中間刪除
• rehash：超過 0.75 後觸發，rehash 後查詢一致
• table->each：完整走訪、提前停止、空表與多 bucket 混合
• merge：覆蓋與補齊路徑，與 count 一致性
• 錯誤處理：刻意製造擴容失敗，pool->error 被寫入

小結與預告

• mongory_table 以簡潔穩健的策略處理碰撞與擴容，並與記憶體池天然貼合，讓上層 Matchers（特別是 Field 與條件文件解析）可以無痛地依 key 存取
• 下一篇 Day 14 會從架構圖層次整理 Matchers 與 Adapter 邊界，並補上 Regex/Custom 的示例與動機

專案（C Core）