1. uthash簡介

2. uthash的使用

2.1 定義結(jié)構(gòu)體

2.2 添加

2.3 查找

2.4 替換

2.5 刪除

2.6 循環(huán)刪除

2.7 刪除哈希表所有元素

2.8 計算哈希表元素個數(shù)

2.9 遍歷哈希表中的所有項目

2.10 排序哈希表

2.11 完整代碼

3. 鍵值的各種類型舉例

3.1 整型鍵值

3.2 字符串鍵值

3.3 指針鍵值

3.4 結(jié)構(gòu)體鍵值

4. 常用宏參考

4.1 類型宏

4.2 通用宏

4.4 參數(shù)說明

1. uthash簡介??由于C語言本身不存在哈希，但是當需要使用哈希表的時候自己構(gòu)建哈希會異常復(fù)雜。因此，我們可以調(diào)用開源的第三方頭文件，這只是一個頭文件：uthash.h。我們需要做的就是將頭文件復(fù)制到項目中，然后：#include “uthash.h”。由于uthash僅是頭文件，因此沒有可鏈接的庫代碼。

使用uthash添加，查找和刪除通常是常數(shù)時間的操作，此哈希的目標是簡約高效，大約有1000行代碼。

uthash還包括三個額外的頭文件，主要提供鏈表，動態(tài)數(shù)組和字符串。utlist.h為C結(jié)構(gòu)提供了鏈接列表宏。utarray.h使用宏實現(xiàn)動態(tài)數(shù)組。utstring.h實現(xiàn)基本的動態(tài)字符串。

2. uthash的使用2.1 定義結(jié)構(gòu)體

這里我們將id作為一個索引值，也就是鍵值，將name作為value。

#include “uthash.h”

struct my_struct {

int id; /* 鍵值 */

char name［10］;

UT_hash_handle hh; /* 使能哈希表 */

};

struct my_struct *users = NULL; //*聲明哈希為NULL指針*/

注意：一定要包含UT_hash_handle hh;hh不需要初始化。它可以命名為任何名稱，但是我們一般都命名為hh。

2.2 添加

HASH_ADD_INT表示添加的鍵值為int類型。

HASH_ADD_STR表示添加的鍵值為字符串類型。

HASH_ADD_PTR表示添加的鍵值為指針類型。

HASH_ADD表示添加的鍵值可以是任意類型。

void add_user（int user_id， char *name） {

struct my_struct *s;

HASH_FIND_INT（users， &user_id， s）; /*重復(fù)性檢查，當把兩個相同key值的結(jié)構(gòu)體添加到哈希表中時會報錯*/

if （s==NULL） {

s = （struct my_struct *）malloc（sizeof *s）;///*只有在哈希中不存在ID的情況下，我們才創(chuàng)建該項目并將其添加。否則，我們只修改已經(jīng)存在的結(jié)構(gòu)。*/

s-》id = user_id;

HASH_ADD_INT（ users， id， s ）;

}

strcpy（s-》name， name）;

}

HASH_ADD_INT函數(shù)中，第一個參數(shù)users是哈希表，第二個參數(shù)id是鍵字段的名稱。最后一個參數(shù)s是指向要添加的結(jié)構(gòu)的指針。

2.3 查找

struct my_struct *find_user（int user_id） {

struct my_struct *s;

s = （struct my_struct *）malloc（sizeof *s）;

HASH_FIND_INT（ users， &user_id， s ）; /* s： 返回值 */

return s;

}

在上述代碼中，第一個參數(shù)users是哈希表，第二個參數(shù)是user_id的地址（一定要傳遞地址）。最后s是輸出變量。當可以在哈希表中找到相應(yīng)鍵值時，s返回給定鍵的結(jié)構(gòu)，當找不到時s返回NULL。

2.4 替換

HASH_REPLACE宏等效于HASH_ADD宏，HASH_REPLACE會嘗試查找和刪除項目外。如果找到并刪除了一個項目，它還將返回該項目的指針作為輸出參數(shù)。

void replace_user（HashHead *head， HashNode *newNode） {

HashNode *oldNode = find_user（*head， newNode-》id）;

if （oldNode）

HASH_REPLACE_INT（*head， id， newNode， oldNode）;

}

2.5 刪除

要從哈希表中刪除結(jié)構(gòu)，必須具有指向它的指針。（如果只有鍵，請先執(zhí)行HASH_FIND以獲取結(jié)構(gòu)指針）。

void delete_user（struct my_struct *user） {

HASH_DEL（users， user）; /* user： 將要刪除的結(jié)構(gòu)體指針 */

free（user）;

}

同樣，這里users是哈希表，user是指向我們要從哈希中刪除的結(jié)構(gòu)的指針。

刪除結(jié)構(gòu)只是將其從哈希表中刪除，并非free 。何時釋放結(jié)構(gòu)的選擇完全取決于自己；uthash永遠不會主動釋放結(jié)構(gòu)。

2.6 循環(huán)刪除

HASH_ITER是一個宏定義，程序執(zhí)行時被替換為一個循環(huán)。

void delete_all（） {

struct my_struct *current_user， *tmp;

HASH_ITER（hh， users， current_user， tmp） {

HASH_DEL（users，current_user）;

free（current_user）;

}

}

2.7 刪除哈希表所有元素

如果只想刪除所有項目，但不釋放它們或進行每個元素的清理，則可以通過一次操作更有效地做到這一點：

HASH_CLEAR（hh，users）;

之后，列表頭（此處為users）將設(shè)置為NULL。

2.8 計算哈希表元素個數(shù)

unsigned int num_users;

num_users = HASH_COUNT（users）;

printf（“there are %u users

”， num_users）;

當users為NULL時，HASH_COUNT會返回0。

2.9 遍歷哈希表中的所有項目

void print_users（） {

struct my_struct *s;

for（s=users; s ！= NULL; s=s-》hh.next） {

printf（“user id %d： name %s

”， s-》id， s-》name）;

}

}

還有一個hh.prev指針，可用于從任何已知項開始向后迭代哈希。

由于hh.prev和hh.next字段的緣故，可以在哈希中向前和向后迭代?？梢酝ㄟ^遍歷這些指針來訪問哈希中的所有項目，因此哈希也是雙鏈表。

2.10 排序哈希表

HASH_SORT（ users， name_sort ）;

第二個參數(shù)是指向比較函數(shù)的指針。它必須接受兩個指針參數(shù)（要比較的項目），并且如果第一個項目分別在第二個項目之前，等于或之后排序，則必須返回小于零，零或大于零的int。 （這與標準C庫中的strcmp或qsort使用的方法相同）。

int sort_function（void *a， void *b） {

/* 將a與b比較*/

if （a 《 b） return （int） -1;

if （a == b） return （int） 0 ;

if （a 》 b） return （int） 1;

}

name_sort和id_sort的兩個排序函數(shù)示例。

int name_sort（struct my_struct *a， struct my_struct *b） {

return strcmp（a-》name，b-》name）;

}

int id_sort（struct my_struct *a， struct my_struct *b） {

return （a-》id - b-》id）;

}

void sort_by_name（） {

HASH_SORT（users， name_sort）;

}

void sort_by_id（） {

HASH_SORT（users， id_sort）;

}

2.11 完整代碼

/*

* @Description： UTHASH的使用

* @Version： V1.0

* @Autor： 公眾號【嵌入式與Linux那些事】

* @Date： 2020-2-2 2112

* @LastEditors： 公眾號【嵌入式與Linux那些事】

* @LastEditTime： 2020-2-2 2246

*/

#include 《stdio.h》 /* gets */

#include 《stdlib.h》 /* atoi， malloc */

#include 《string.h》 /* strcpy */

#include “uthash.h”

struct my_struct {

int id; /* 鍵值 */

char name［10］;

UT_hash_handle hh; /* 使能結(jié)構(gòu)體 */

};

struct my_struct *users = NULL;

void add_user（int user_id， char *name） {

struct my_struct *s;

HASH_FIND_INT（users， &user_id， s）;

if （s==NULL） {

s = （struct my_struct *）malloc（sizeof *s）;

s-》id = user_id;

HASH_ADD_INT（ users， id， s ）;

}

strcpy（s-》name， name）;

}

struct my_struct *find_user（int user_id） {

struct my_struct *s;

s = （struct my_struct *）malloc（sizeof *s）;

HASH_FIND_INT（ users， &user_id， s ）;

return s;

}

void delete_user（struct my_struct *user） {

HASH_DEL（users， user）;

free（user）;

}

void delete_all（） {

struct my_struct *current_user， *tmp;

HASH_ITER（hh， users， current_user， tmp） {

HASH_DEL（users， current_user）;

free（current_user）;

}

}

void print_users（） {

struct my_struct *s;

for（s=users; s ！= NULL; s=（struct my_struct*）（s-》hh.next）） {

printf（“user id %d： name %s

”， s-》id， s-》name）;

}

}

int name_sort（struct my_struct *a， struct my_struct *b） {

return strcmp（a-》name，b-》name）;

}

int id_sort（struct my_struct *a， struct my_struct *b） {

return （a-》id - b-》id）;

}

void sort_by_name（） {

HASH_SORT（users， name_sort）;

}

void sort_by_id（） {

HASH_SORT（users， id_sort）;

}

int main（int argc， char *argv［］） {

char in［10］;

int id=1， running=1;

struct my_struct *s;

unsigned num_users;

while （running） {

printf（“ 1. add user

”）;

printf（“ 2. add/rename user by id

”）;

printf（“ 3. find user

”）;

printf（“ 4. delete user

”）;

printf（“ 5. delete all users

”）;

printf（“ 6. sort items by name

”）;

printf（“ 7. sort items by id

”）;

printf（“ 8. print users

”）;

printf（“ 9. count users

”）;

printf（“10. quit

”）;

gets（in）;

switch（atoi（in）） {

case 1：

printf（“name？

”）;

add_user（id++， gets（in））;

break;

case 2：

printf（“id？

”）;

gets（in）; id = atoi（in）;

printf（“name？

”）;

add_user（id， gets（in））;

break;

case 3：

printf（“id？

”）;

s = find_user（atoi（gets（in）））;

printf（“user： %s

”， s ？ s-》name ： “unknown”）;

break;

case 4：

printf（“id？

”）;

s = find_user（atoi（gets（in）））;

if （s） delete_user（s）;

else printf（“id unknown

”）;

break;

case 5：

delete_all（）;

break;

case 6：

sort_by_name（）;

break;

case 7：

sort_by_id（）;

break;

case 8：

print_users（）;

break;

case 9：

num_users=HASH_COUNT（users）;

printf（“there are %u users

”， num_users）;

break;

case 10：

running=0;

break;

}

}

delete_all（）;

return 0;

}

3. 鍵值的各種類型舉例3.1 整型鍵值

當鍵值為整型時，可以使用HASH_ADD_INT和HASH_FIND_INT。（對于所有類型的鍵，其他操作（例如HASH_DELETE和）HASH_SORT都是相同的）。

3.2 字符串鍵值

當鍵值為字符串時，具體要使用那個函數(shù)取決于結(jié)構(gòu)體中的鍵值為字符串數(shù)組還是字符串指針。 這一點很重要。當結(jié)構(gòu)體中的鍵值為字符串數(shù)組時，使用HASH_ADD_STR。鍵值為字符串指針時使用HASH_ADD_KEYPTR。接下來給出兩個例子參考。

當結(jié)構(gòu)體中的鍵值為字符串數(shù)組時

#include 《string.h》 /* strcpy */

#include 《stdlib.h》 /* malloc */

#include 《stdio.h》 /* printf */

#include “uthash.h”

struct my_struct {

char name［10］;

int id;

UT_hash_handle hh;

};

int main（int argc， char *argv［］） {

const char *names［］ = { “joe”， “bob”， “betty”， NULL };

struct my_struct *s， *tmp， *users = NULL;

for （int i = 0; names［i］; ++i） {

s = （struct my_struct *）malloc（sizeof *s）;

strcpy（s-》name， names［i］）;

s-》id = i;

HASH_ADD_STR（ users， name， s ）;

}

HASH_FIND_STR（ users， “betty”， s）;

if （s） printf（“betty‘s id is %d

”， s-》id）;

HASH_ITER（hh， users， s， tmp） {

HASH_DEL（users， s）;

free（s）;

}

return 0;

}

當結(jié)構(gòu)體中的鍵值為字符串指針時

#include 《string.h》 /* strcpy */

#include 《stdlib.h》 /* malloc */

#include 《stdio.h》 /* printf */

#include “uthash.h”

struct my_struct {

const char *name;

int id;

UT_hash_handle hh;

};

int main（int argc， char *argv［］） {

const char *names［］ = { “joe”， “bob”， “betty”， NULL };

struct my_struct *s， *tmp， *users = NULL;

for （int i = 0; names［i］; ++i） {

s = （struct my_struct *）malloc（sizeof *s）;

s-》name = names［i］;

s-》id = i;

HASH_ADD_KEYPTR（ hh， users， s-》name， strlen（s-》name）， s ）;

}

HASH_FIND_STR（ users， “betty”， s）;

if （s） printf（“betty’s id is %d

”， s-》id）;

HASH_ITER（hh， users， s， tmp） {

HASH_DEL（users， s）;

free（s）;

}

return 0;

}

3.3 指針鍵值

#include 《stdio.h》

#include 《stdlib.h》

#include “uthash.h”

typedef struct {

void *key;

int i;

UT_hash_handle hh;

} el_t;

el_t *hash = NULL;

char *someaddr = NULL;

int main（） {

el_t *d;

el_t *e = （el_t *）malloc（sizeof *e）;

if （！e） return -1;

e-》key = （void*）someaddr;

e-》i = 1;

HASH_ADD_PTR（hash，key，e）;

HASH_FIND_PTR（hash， &someaddr， d）;

if （d） printf（“found

”）;

/* release memory */

HASH_DEL（hash，e）;

free（e）;

return 0;

}

3.4 結(jié)構(gòu)體鍵值

在將項目添加到哈?；虿檎翼椖恐?，必須將結(jié)構(gòu)體鍵值中的元素清零。

#include 《stdlib.h》

#include 《stdio.h》

#include “uthash.h”

typedef struct {

char a;

int b;

} record_key_t;

typedef struct {

record_key_t key;

UT_hash_handle hh;

} record_t;

int main（int argc， char *argv［］） {

record_t l， *p， *r， *tmp， *records = NULL;

r = （record_t *）malloc（sizeof *r）;

memset（r， 0， sizeof *r）;/*結(jié)構(gòu)體鍵值清零*/

r-》key.a = ‘a(chǎn)’;

r-》key.b = 1;

HASH_ADD（hh， records， key， sizeof（record_key_t）， r）;

memset（&l， 0， sizeof（record_t））;

l.key.a = ‘a(chǎn)’;

l.key.b = 1;

HASH_FIND（hh， records， &l.key， sizeof（record_key_t）， p）;

if （p） printf（“found %c %d

”， p-》key.a， p-》key.b）;

HASH_ITER（hh， records， p， tmp） {

HASH_DEL（records， p）;

free（p）;

}

return 0;

}

4. 常用宏參考4.1 類型宏

HASH_ADD_INT（head， keyfield_name， item_ptr）

HASH_REPLACE_INT（head， keyfiled_name， item_ptr，replaced_item_ptr）

HASH_FIND_INT（head， key_ptr， item_ptr）

HASH_ADD_STR（head， keyfield_name， item_ptr）

HASH_REPLACE_STR（head，keyfield_name， item_ptr， replaced_item_ptr）

HASH_FIND_STR（head， key_ptr， item_ptr）

HASH_ADD_PTR（head， keyfield_name， item_ptr）

HASH_REPLACE_PTR（head， keyfield_name， item_ptr， replaced_item_ptr）

HASH_FIND_PTR（head， key_ptr， item_ptr）

HASH_DEL（head， item_ptr）

HASH_SORT（head， cmp）

HASH_COUNT（head）

4.2 通用宏

HASH_ADD（hh_name， head， keyfield_name， key_len， item_ptr）

HASH_ADD_BYHASHVALUE（hh_name， head， keyfield_name， key_len， hashv， item_ptr）

HASH_ADD_KEYPTR（hh_name， head， key_ptr， key_len， item_ptr）

HASH_ADD_KEYPTR_BYHASHVALUE（hh_name， head， key_ptr， key_len， hashv， item_ptr）

HASH_ADD_INORDER（hh_name， head， keyfield_name， key_len， item_ptr， cmp）

HASH_ADD_BYHASHVALUE_INORDER（hh_name， head， keyfield_name， key_len， hashv， item_ptr， cmp）

HASH_ADD_KEYPTR_INORDER（hh_name， head， key_ptr， key_len， item_ptr， cmp）

HASH_ADD_KEYPTR_BYHASHVALUE_INORDER（hh_name， head， key_ptr， key_len， hashv， item_ptr， cmp）

HASH_REPLACE（hh_name， head， keyfield_name， key_len， item_ptr， replaced_item_ptr）

HASH_REPLACE_BYHASHVALUE（hh_name， head， keyfield_name， key_len， hashv， item_ptr， replaced_item_ptr）

HASH_REPLACE_INORDER（hh_name， head， keyfield_name， key_len， item_ptr， replaced_item_ptr， cmp）

HASH_REPLACE_BYHASHVALUE_INORDER（hh_name， head， keyfield_name， key_len， hashv， item_ptr， replaced_item_ptr， cmp）

HASH_FIND（hh_name， head， key_ptr， key_len， item_ptr）

HASH_FIND_BYHASHVALUE（hh_name， head， key_ptr， key_len， hashv， item_ptr）

HASH_DELETE（hh_name， head， item_ptr）

HASH_VALUE（key_ptr， key_len， hashv）

HASH_SRT（hh_name， head， cmp）

HASH_CNT（hh_name， head）

HASH_CLEAR（hh_name， head）

HASH_SELECT（dst_hh_name， dst_head， src_hh_name， src_head， condition）

HASH_ITER（hh_name， head， item_ptr， tmp_item_ptr）

HASH_OVERHEAD（hh_name， head）

4.4 參數(shù)說明

hh_name：UT_hash_handle結(jié)構(gòu)中字段的 名稱。俗稱 hh。

head：結(jié)構(gòu)指針變量，用作哈希的“頭”。如此命名是因為它最初指向添加到哈希中的第一項。

keyfield_name：結(jié)構(gòu)中鍵字段的名稱。（對于多字段鍵，這是鍵的第一個字段）。

key_len：鍵字段的長度（以字節(jié)為單位）。例如，對于整數(shù)鍵，它是sizeof（int），而對于字符串鍵，它是strlen（key）。

key_ptr：對于HASH_FIND，這是指向要在哈希中查找的鍵的指針（由于它是指針，因此不能在此處直接傳遞文字值）。對于 HASH_ADD_KEYPTR，這是要添加的項的鍵的地址。

hashv：提供的鍵的哈希值。這是BYHASHVALUE宏的輸入?yún)?shù)。如果要重復(fù)查找相同的鍵，則重用緩存的哈希值可以優(yōu)化性能。

item_ptr：指向要添加，刪除，替換或查找的結(jié)構(gòu)的指針，或迭代期間的當前指針。這是HASH_ADD， HASH_DELETE和HASH_REPLACE宏的輸入?yún)?shù)，輸出參數(shù)為HASH_FIND 和HASH_ITER。（當HASH_ITER用于迭代時，tmp_item_ptr 是與item_ptr內(nèi)部使用的類型相同的另一個變量）。

replace_item_ptr：用于HASH_REPLACE宏。這是一個輸出參數(shù)，設(shè)置為指向替換的項目（如果沒有替換的項目，則設(shè)置為NULL）。

cmp：指向比較函數(shù)的指針，該函數(shù)接受兩個參數(shù)（指向要比較的項目的指針），并返回一個int值，該值指定第一個項目應(yīng)在第二個項目之前，等于還是之后排序（如strcmp）。

condition：接受單個參數(shù)的函數(shù)或宏（指向結(jié)構(gòu)的空指針，需要將其強制轉(zhuǎn)換為適當?shù)慕Y(jié)構(gòu)類型）。如果應(yīng)“選擇”結(jié)構(gòu)以將其添加到目標哈希中，則函數(shù)或宏的值應(yīng)為非零值。

原文標題：你知道uthash嗎？

文章出處：【微信公眾號：FPGA之家】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq