目前在開放源碼領域,有好幾個 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)外,也可以將字串、指標甚至任意資料結構當成鍵值。詳細用法可參考官方網頁。