uthash簡(jiǎn)介及使用說(shuō)明

• 1. uthash簡(jiǎn)介

• 2. uthash的使用

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

  • 2.2 添加

  • 2.3 查找

  • 2.4 替換

  • 2.5 刪除

  • 2.6 循環(huán)刪除

  • 2.7 刪除哈希表所有元素

  • 2.8 計(jì)算哈希表元素個(gè)數(shù)

  • 2.9 遍歷哈希表中的所有項(xiàng)目

  • 2.10 排序哈希表

  • 2.11 完整代碼

• 3. 鍵值的各種類(lèi)型舉例

  • 3.1 整型鍵值

  • 3.2 字符串鍵值

  • 3.3 指針鍵值

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

• 4. 常用宏參考

  • 4.1 類(lèi)型宏

  • 4.2 通用宏

  • 4.4 參數(shù)說(shuō)明

1. uthash簡(jiǎn)介

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

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

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

??github下載鏈接：https://github.com/troydhanson/uthash

2. uthash的使用

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

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

#include"uthash.h"
structmy_struct{
intid;/*鍵值*/
charname[10];
UT_hash_handlehh;/*使能哈希表*/
};
structmy_struct*users=NULL;//*聲明哈希為NULL指針*/

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

2.2 添加

??HASH_ADD_INT表示添加的鍵值為int類(lèi)型。

??HASH_ADD_STR表示添加的鍵值為字符串類(lèi)型。

??HASH_ADD_PTR表示添加的鍵值為指針類(lèi)型。

??HASH_ADD表示添加的鍵值可以是任意類(lèi)型。

voidadd_user(intuser_id,char*name){
structmy_struct*s;
HASH_FIND_INT(users,&user_id,s);/*重復(fù)性檢查，當(dāng)把兩個(gè)相同key值的結(jié)構(gòu)體添加到哈希表中時(shí)會(huì)報(bào)錯(cuò)*/
if(s==NULL){
s=(structmy_struct*)malloc(sizeof*s);///*只有在哈希中不存在ID的情況下，我們才創(chuàng)建該項(xiàng)目并將其添加。否則，我們只修改已經(jīng)存在的結(jié)構(gòu)。*/
s->id=user_id;
HASH_ADD_INT(users,id,s);
}
strcpy(s->name,name);
}

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

2.3 查找

structmy_struct*find_user(intuser_id){
structmy_struct*s;
s=(structmy_struct*)malloc(sizeof*s);
HASH_FIND_INT(users,&user_id,s);/*s:返回值*/
returns;
}

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

2.4 替換

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

voidreplace_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)，必須具有指向它的指針。（如果只有鍵，請(qǐng)先執(zhí)行HASH_FIND以獲取結(jié)構(gòu)指針）。

voiddelete_user(structmy_struct*user){
HASH_DEL(users,user);/*user:將要?jiǎng)h除的結(jié)構(gòu)體指針*/
free(user);
}

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

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

2.6 循環(huán)刪除

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

voiddelete_all(){
structmy_struct*current_user,*tmp;

HASH_ITER(hh,users,current_user,tmp){
HASH_DEL(users,current_user);
free(current_user);
}
}

2.7 刪除哈希表所有元素

??如果只想刪除所有項(xiàng)目，但不釋放它們或進(jìn)行每個(gè)元素的清理，則可以通過(guò)一次操作更有效地做到這一點(diǎn)：

HASH_CLEAR(hh,users);

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

2.8 計(jì)算哈希表元素個(gè)數(shù)

unsignedintnum_users;
num_users=HASH_COUNT(users);
printf("thereare%uusers
",num_users);

??當(dāng)users為NULL時(shí)，HASH_COUNT會(huì)返回0。

2.9 遍歷哈希表中的所有項(xiàng)目

voidprint_users(){
structmy_struct*s;
for(s=users;s!=NULL;s=s->hh.next){
printf("userid%d:name%s
",s->id,s->name);
}
}

??還有一個(gè)hh.prev指針，可用于從任何已知項(xiàng)開(kāi)始向后迭代哈希。

??由于hh.prev和hh.next字段的緣故，可以在哈希中向前和向后迭代?？梢酝ㄟ^(guò)遍歷這些指針來(lái)訪(fǎng)問(wèn)哈希中的所有項(xiàng)目，因此哈希也是雙鏈表。

2.10 排序哈希表

HASH_SORT(users,name_sort);

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

intsort_function(void*a,void*b){
/*將a與b比較*/
if(areturn(int)-1;
if(a==b)return(int)0;
if(a>b)return(int)1;

}

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

intname_sort(structmy_struct*a,structmy_struct*b){
returnstrcmp(a->name,b->name);
}

intid_sort(structmy_struct*a,structmy_struct*b){
return(a->id-b->id);
}

voidsort_by_name(){
HASH_SORT(users,name_sort);
}

voidsort_by_id(){
HASH_SORT(users,id_sort);
}

2.11 完整代碼

/*
*@Description:UTHASH的使用
*@Version:V1.0
*@Autor:公眾號(hào)【嵌入式與Linux那些事】
*@Date:2020-2-22112
*@LastEditors:公眾號(hào)【嵌入式與Linux那些事】
*@LastEditTime:2020-2-22246
*/
#include/*gets*/
#include/*atoi,malloc*/
#include/*strcpy*/
#include"uthash.h"

structmy_struct{
intid;/*鍵值*/
charname[10];
UT_hash_handlehh;/*使能結(jié)構(gòu)體*/
};

structmy_struct*users=NULL;

voidadd_user(intuser_id,char*name){
structmy_struct*s;

HASH_FIND_INT(users,&user_id,s);
if(s==NULL){
s=(structmy_struct*)malloc(sizeof*s);
s->id=user_id;
HASH_ADD_INT(users,id,s);
}
strcpy(s->name,name);
}

structmy_struct*find_user(intuser_id){
structmy_struct*s;
s=(structmy_struct*)malloc(sizeof*s);
HASH_FIND_INT(users,&user_id,s);
returns;
}

voiddelete_user(structmy_struct*user){
HASH_DEL(users,user);
free(user);
}

voiddelete_all(){
structmy_struct*current_user,*tmp;

HASH_ITER(hh,users,current_user,tmp){
HASH_DEL(users,current_user);
free(current_user);
}
}

voidprint_users(){
structmy_struct*s;

for(s=users;s!=NULL;s=(structmy_struct*)(s->hh.next)){
printf("userid%d:name%s
",s->id,s->name);
}
}

intname_sort(structmy_struct*a,structmy_struct*b){
returnstrcmp(a->name,b->name);
}

intid_sort(structmy_struct*a,structmy_struct*b){
return(a->id-b->id);
}

voidsort_by_name(){
HASH_SORT(users,name_sort);
}

voidsort_by_id(){
HASH_SORT(users,id_sort);
}

intmain(intargc,char*argv[]){
charin[10];
intid=1,running=1;
structmy_struct*s;
unsignednum_users;

while(running){
printf("1.adduser
");
printf("2.add/renameuserbyid
");
printf("3.finduser
");
printf("4.deleteuser
");
printf("5.deleteallusers
");
printf("6.sortitemsbyname
");
printf("7.sortitemsbyid
");
printf("8.printusers
");
printf("9.countusers
");
printf("10.quit
");
gets(in);
switch(atoi(in)){
case1:
printf("name?
");
add_user(id++,gets(in));
break;
case2:
printf("id?
");
gets(in);id=atoi(in);
printf("name?
");
add_user(id,gets(in));
break;
case3:
printf("id?
");
s=find_user(atoi(gets(in)));
printf("user:%s
",s?s->name:"unknown");
break;
case4:
printf("id?
");
s=find_user(atoi(gets(in)));
if(s)delete_user(s);
elseprintf("idunknown
");
break;
case5:
delete_all();
break;
case6:
sort_by_name();
break;
case7:
sort_by_id();
break;
case8:
print_users();
break;
case9:
num_users=HASH_COUNT(users);
printf("thereare%uusers
",num_users);
break;
case10:
running=0;
break;
}
}

delete_all();
return0;
}

3. 鍵值的各種類(lèi)型舉例

3.1 整型鍵值

??當(dāng)鍵值為整型時(shí)，可以使用HASH_ADD_INT和HASH_FIND_INT。（對(duì)于所有類(lèi)型的鍵，其他操作（例如HASH_DELETE和）HASH_SORT都是相同的）。

3.2 字符串鍵值

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

??當(dāng)結(jié)構(gòu)體中的鍵值為字符串?dāng)?shù)組時(shí)

#include/*strcpy*/
#include/*malloc*/
#include/*printf*/
#include"uthash.h"

structmy_struct{
charname[10];
intid;
UT_hash_handlehh;
};


intmain(intargc,char*argv[]){
constchar*names[]={"joe","bob","betty",NULL};
structmy_struct*s,*tmp,*users=NULL;

for(inti=0;names[i];++i){
s=(structmy_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'sidis%d
",s->id);


HASH_ITER(hh,users,s,tmp){
HASH_DEL(users,s);
free(s);
}
return0;
}

??當(dāng)結(jié)構(gòu)體中的鍵值為字符串指針時(shí)

#include/*strcpy*/
#include/*malloc*/
#include/*printf*/
#include"uthash.h"

structmy_struct{
constchar*name;
intid;
UT_hash_handlehh;
};


intmain(intargc,char*argv[]){
constchar*names[]={"joe","bob","betty",NULL};
structmy_struct*s,*tmp,*users=NULL;

for(inti=0;names[i];++i){
s=(structmy_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'sidis%d
",s->id);

HASH_ITER(hh,users,s,tmp){
HASH_DEL(users,s);
free(s);
}
return0;
}

3.3 指針鍵值

#include
#include
#include"uthash.h"

typedefstruct{
void*key;
inti;
UT_hash_handlehh;
}el_t;

el_t*hash=NULL;
char*someaddr=NULL;

intmain(){
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
");

/*releasememory*/
HASH_DEL(hash,e);
free(e);
return0;
}

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

??在將項(xiàng)目添加到哈希或查找項(xiàng)目之前，必須將結(jié)構(gòu)體鍵值中的元素清零。

#include
#include
#include"uthash.h"

typedefstruct{
chara;
intb;
}record_key_t;

typedefstruct{
record_key_tkey;
UT_hash_handlehh;
}record_t;

intmain(intargc,char*argv[]){
record_tl,*p,*r,*tmp,*records=NULL;

r=(record_t*)malloc(sizeof*r);

memset(r,0,sizeof*r);/*結(jié)構(gòu)體鍵值清零*/
r->key.a='a';
r->key.b=1;
HASH_ADD(hh,records,key,sizeof(record_key_t),r);

memset(&l,0,sizeof(record_t));
l.key.a='a';
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);
}
return0;
}

4. 常用宏參考

4.1 類(lèi)型宏

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ù)說(shuō)明

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

??head：結(jié)構(gòu)指針變量，用作哈希的“頭”。如此命名是因?yàn)樗畛踔赶蛱砑拥焦Ｖ械牡谝豁?xiàng)。

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

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

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

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

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

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

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

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

審核編輯：湯梓紅