目前在開放源碼領域，有好幾個 C 語言 hash map 函式庫的實作，uthash 是蠻常被提到的實作之一，它很簡單、好上手、以及有彈性的授權方式，乃是我將它應用在我帶領的許多專案裡的主要原因，至於記憶體使用量與雜湊速度也還算四平八穩。真的頗推薦於中、小型的專案裡使用。
關於 uthash
使用授權
uthash 的授權方式為 revised BSD license (授權宣告)，在使用上限制較少。
源碼下載
uthash 源碼可由 github 下載，原始碼網頁。
源碼安裝
uthash 源碼僅包含四個標頭檔，直接複製至專案裡或是修改編譯器參數引用即可。
- utarray.h。陣列函式庫。
- uthash.h。雜湊表函式庫。
- utlist.h。列表函式庫。
- utstring.h。字串函式庫。
範例
在此，我會使用一個簡單的實例來介紹 uthash 使用方式。這個範例是一個簡單的使用者資料庫，使用者可以透過人名搜尋資料庫，也可以新增、刪除使用者資料。
首先，要了解如何宣告相關的資料結構，供 uthash 處理。
步驟一：宣告資料結構
為了讓此資料結構可被 uthash 處理，必須在資料結構中加入特定欄位：「hh」(其資料型別為 UT_hash_handle)。
|
1 2 3 4 5 6 7 |
#include "uthash.h" struct user { int id; /* key */ char name[10]; UT_hash_handle hh; /* makes this structure hashable */ }; |
步驟二：宣告雜湊表
雜湊表的型別與自行定義的資料結構相同，不需另行宣告型別。但必須宣告變數（並初始化為 NULL）。
|
1 |
struct user *users = NULL; |
宣告完成後，即可於程式中操作雜湊表。
新增資料
透過 HASH_ADD_xxx()，即可新增資料。若想要把整數型別當作雜湊的欄位，可使用HASH_ADD_INT()。
|
1 2 3 4 5 6 7 8 9 |
void add_user(int user_id, char *name) { struct user *s; s = malloc(sizeof(*s)); s->id = user_id; strcpy(s->name, name); HASH_ADD_INT(users, id, s); } |
HASH_ADD_INT()需要3個參數。第一是雜湊表變數；第二為用來雜湊的資料欄「名稱」，最後帶入物件變數。
搜尋資料
HASH_FIND_xxx()，可用來搜尋存入雜湊表中的資料。在本範例，使用 id 來雜湊，所以呼叫 HASH_FIND_INT()。
HASH_FIND_INT() 需要三個變數。第一是雜湊表變數；第二為鍵值（key value），最後帶入物件變數。
|
1 2 3 4 5 6 7 |
struct user *find_user(int user_id) { struct user *s; HASH_FIND_INT(users, &user_id, s); return s; } |
若有搜尋到資料，物件變數會是一個合法的指標；不然就會被設為NULL。
刪除資料
透過 HASH_DEL() 可刪除資料。HASH_DEL() 僅需傳入兩個參數。第一是雜湊表變數；第二為該資料之指標。
|
1 2 3 4 |
void delete_user(struct user *user) { HASH_DEL(users, user); free(user); } |
使用限制
第一：鍵值不可重複
uthash 規定鍵值不可重複，若存入鍵值相同的資料會產生錯誤。所以在新增資料前必須先行檢查。
|
1 2 3 4 5 6 7 8 9 |
void add_user(int user_id, char *name) { struct user *s; HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */ if (s != NULL) return; s = (struct user*)malloc(sizeof(*s)); s->id = user_id; HASH_ADD_INT(users, id, s); /* id: name of key field */ } |
若已有鍵值相同的資料在雜湊表中，有兩個作法。第一，刪除舊有資料，再行新增。或是，僅更新資料內容。
|
1 2 3 4 5 6 7 8 9 10 |
void add_user(int user_id, char *name) { struct user *s; HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */ if (s == NULL) { s = (struct my_struct*)malloc(sizeof(*s)); s->id = user_id; HASH_ADD_INT( users, id, s ); /* id: name of key field */ } strcpy(s->name, name); } |
第二：uthash 不會幫忙管理物件的指標
將資料自雜湊表移除後，若確認資料不會再被用到，必須自行將其刪除。
|
1 2 3 4 |
void delete_user(struct user *user) { HASH_DEL(users, user); free(user); } |
進階使用
uthash 除了可利用整數為鍵值（key value）外，也可以將字串、指標甚至任意資料結構當成鍵值。詳細用法可參考官方網頁。