C语⾔开源uthash⽤法总结
uthash 是C的⽐较优秀的开源代码，它实现了常见的hash操作函数，例如查、插⼊、删除等等。该套开源代码采⽤宏的⽅式实现hash函数的相关功能，⽀持C语⾔的任意数据结构最为key值，甚⾄可以采⽤多个值作为key，⽆论是⾃定义的struct还是基本数据类型，需要注意的是不同类型的key其操作接⼝⽅式略有不同。
使⽤uthash代码时只需要包含头⽂件"uthash.h"即可。由于该代码采⽤宏的⽅式实现，所有的实现代码都在uthash.h⽂件中，因此只需要在⾃⼰的代码中包含该头⽂件即可。
Uthash的三个数据结构：
typedef struct UT_hash_bucket {
struct UT_hash_handle *hh_head;
unsigned count;
unsigned expand_mult;
} UT_hash_bucket;
UT_hash_bucket作⽤提供根据hash进⾏索引。
typedef struct UT_hash_table {
UT_hash_bucket *buckets;
unsigned num_buckets, log2_num_buckets;
unsigned num_items;
struct UT_hash_handle *tail;/* tail hh in app order, for fast append    */
ptrdiff_t hho;/* hash handle offset (byte pos of hash handle in element */
unsigned ideal_chain_maxlen;
unsigned nonideal_items;
unsigned ineff_expands, noexpand;
uint32_t signature;/* used only to find hash tables in external analysis */
#ifdef HASH_BLOOM
uint32_t bloom_sig;/* used only to test bloom exists in external analysis */
uint8_t *bloom_bv;
char bloom_nbits;
#endif
} UT_hash_table;
UT_hash_table可以看做hash表的表头。
typedef struct UT_hash_handle {
struct UT_hash_table *tbl;/* 指向hash表 */
void*prev;/* prev element in app order      */
void*next;/* next element in app order      */
struct UT_hash_handle *hh_prev;/* previous hh in bucket order    */
struct UT_hash_handle *hh_next;/* next hh in bucket order        */
void*key;/* ptr to enclosing struct's key  */
unsigned keylen;/* enclosing struct's key len    */
unsigned hashv;/*哈希值*//* result of hash-fcn(key)        */
} UT_hash_handle;
UT_hash_handle，⽤户⾃定义数据必须包含的结构。
1．uthash的效率
uthash的插⼊、查、删除的操作时间都是常量，当然这个常量的值受到key以及所选择的hash函数的影响，uthash共提供了7种函数，⼀般情况下选择默认的即可。如果对效率要求特别⾼时，可以再根据⾃⼰的需求选择适合⾃⼰的hash函数。
2、uthash的使⽤
在hash操作中，都是按照“键-值“对的⽅式进⾏插、查等操作，在uthash中，其基本数据结构就是⼀个包含“键-值“对的结构体，另外，该结构体中还包含⼀个uthash内部使⽤的hash处理句柄，如下代码所⽰：
#include"uthash.h"
struct my_struct {
int id;/* key */
char name[10];
UT_hash_handle hh;/* makes this structure hashable */
};
其中：
id是键（key）；
name是值（val），即⾃⼰要保存的数据域，这⾥可以根据⾃⼰的需要让它变成结构体指针或者其他
类型都可以；
hh是内部使⽤的hash处理句柄，在使⽤过程中，只需要在结构体中定义⼀个UT_hash_handle类型的变量即可，不需要为该句柄变量赋值，但必须在该结构体中定义该变量。
Uthash所实现的hash表中可以提供类似于双向链表的操作，可以通过结构体成员hh的 hh.prev和hh.next获取当前节点的上⼀个节点或者下⼀个节点。
3．Key类型为int的简单⽰例
1）定义⼀个键为int类型的hash结构体：
#include"uthash.h"
struct my_struct {
int ikey;/* key */
char value[10];
UT_hash_handle hh;
};
struct my_struct *g_users =NULL;
这⾥需要注意:
key的类型为int，key的类型不⼀样，后⾯的插⼊、查调⽤的接⼝函数就不⼀样，因此要求确保key的类型与uthash的接⼝函数⼀致。
必须提供 UT_hash_handle 变量 hh，⽆需为其初始化。
定义⼀个hash结构的空指针 g_users，⽤于指向保存数据的hash表，必须初始化为空，在后⾯的查、插等操作中，uthash内部会根据其是否为空⽽进⾏不同的操作。
2）实现⾃⼰的查接⼝函数：
struct my_struct *find_user(int user_ikey){
struct my_struct *s;
HASH_FIND_INT(g_users,&user_ikey, s);
return s;
}
其实现过程就是先定义⼀个hash结构体指针变量，然后通过 HASH_FIND_INT接⼝到该key所对应的hash结构体。这⾥需要注意：Uthash为整型key提供的查接⼝为 HASH_FIND_INT；
传给接⼝ HASH_FIND_INT的第⼀个参数就是在1）中定义的指向hash表的指针，传⼊的第⼆个参数是整型变量ikey的地址。
3）实现⾃⼰的插⼊接⼝函数：
void add_user(int user_ikey,char*value_buf){
struct my_struct *s;
HASH_FIND_INT(g_users,&user_ikey, s);/* 插⼊前先查看key值是否已经在hash表g_users⾥⾯了 */
if(s ==NULL){
s =(struct my_struct*)malloc(sizeof(struct my_struct));
s->ikey = user_ikey;
HASH_ADD_INT(g_users, ikey, s);/* 这⾥必须明确告诉插⼊函数，⾃⼰定义的hash结构体中键变量的名字 */
}
strcpy(s->value, value_buf);
}
由于uthash要求键（key）必须唯⼀，⽽uthash内部未对key值得唯⼀性进⾏很好的处理，因此它要求外部在插⼊操作时要确保其key值不在当前的hash表中，这就需要，在插⼊操作时，先查hash表看其值是否已经存在，不存在在时再进⾏插⼊操作，在这⾥需要特别注意以下两点：
插⼊时，先查，当键不在当前的hash表中时再进⾏插⼊，以确保键的唯⼀性。
需调⽤插⼊接⼝函数时需要明确告诉接⼝函数，⾃⼰定义的键变量的名字是什么。
4）实现删除接⼝
void delete_user(int user_ikey){
struct my_struct *s =NULL;
HASH_FIND_INT(g_users,&user_ikey, s);
if(s !=NULL){
HASH_DEL(g_users, s);
free(s);
}
}
删除操作的接⼝函数为HASH_DEL，只需要告诉该接⼝要释放哪个hash表（这⾥是g_users）⾥的哪个节点（这⾥是s），需要注意：释放申请的hash结构体变量，uthash函数只将结构体从hash表中移除，并未释放该结构体所占据的内存。
5）清空hash表
void delete_all(){
struct my_struct *current_user,*tmp;
HASH_ITER(hh, users, current_user, tmp){
HASH_DEL(g_users,current_user);
free(current_user);
}
}
这⾥需要注意：uthash内部提供了另外⼀个清空函数:
HASH_CLEAR(hh, g_users);
函数，但它不释放各节点的内存，因此尽量不要使⽤它.
6）统计hash表中的已经存在的元素数
该操作使⽤函数
HASH_COUNT
即可获取到当前hash表中的元素数，其⽤法为：
unsigned int num_users;
num_users =HASH_COUNT(g_users);
printf("there are %u items\n", num_users);
7）遍历元素
在开发过程中，可能需要对整个hash表进⾏遍历，这⾥可以通过
<
获取当前元素的下⼀个元素。具体遍历⽅法为：
struct my_struct *s,*tmp;
HASH_ITER(hh, g_users, s, tmp){
printf("user ikey %d: value %s\n", s->ikey, s->value);
/* ... it is safe to delete and free s here */
}
另外还有⼀种不安全的删除⽅法，尽量避免使⽤它：
void print_users(){
struct my_struct *s;
for(s=g_users; s !=NULL; s=s-&){
printf("user ikey %d: value %s\n", s->ikey, s->value);
}
}
4． 其他类型key的使⽤
本节主要关于key值类型为其他任意类型，例如整型、字符串、指针、结构体等时的⽤法。
注意：在使⽤key值为浮点类型时，由于浮点类型的⽐较受到精度的影响，例如：1.0000000002被认为与1相等，这些问题在uthash中也存在。
struct my_struct {
int id;/* key */
char name[10];
UT_hash_handle hh;/* makes this structure hashable */
};
typedef struct my_struct HashNode;
typedef struct my_struct *HashHead;
向hashtable中添加数据:
key是int，可以使⽤ HASH_ADD_INT
key是字符串，可以使⽤ HASH_ADD_STR
key是指针，可以使⽤ HASH_ADD_KEYPTR
其它，可以使⽤ HASH_ADD，上述实际都是调⽤这个⽅法，不过简化了参数void hashTabel_add(HashHead *head, HashNode *users){
// id是key的属性名字，虽然很奇怪，实际作为宏参数会被替换掉
// 可以看下⾯源码，intfield会替换换成&((add)->fieldname)
if(!find_user(*head, users->id))
HASH_ADD_INT(*head, id, users);
}
#define HASH_ADD_INT(head,intfield,add)\ HASH_ADD(hh,head,intfield,sizeof(int),add)
c语言struct头文件
#define HASH_ADD(hh,head,fieldname,keylen_in,add)\ HASH_ADD_KEYPTR(hh, head,&((add)->fieldname), keylen_in, add)
在hashtable中替换数据:
与添加差不多，会在添加前，删除key相同的节点，再添加新的节点
如果key是int，可以使⽤ HASH_REPLACE_INT
void replace_user(HashHead *head, HashNode *newNode){
HashNode *oldNode =find_user(*head, newNode->id);
if(oldNode)
HASH_REPLACE_INT(*head, id, newNode, oldNode);
}
遍历节点：
可以⽤循环或者使⽤ HASH_ITER
void print_user(HashHead head){
HashNode *s;
printf("size is %d\n",count_user(head));
for(s = head; s !=NULL; s = s-&){
printf("user id %d, name %s\n", s->id, s->name);
}
}
void print_user_iterator(HashHead head){
HashNode *s,*tmp;
printf("size is %d\n",count_user(head));
HASH_ITER(hh, head, s, tmp){
printf("user id %d: name %s\n", s->id, s->name);
/* ... it is safe to delete and free s here */
}
}
4.1． int类型key
前⾯就是以int类型的key作为⽰例，总结int类型key使⽤⽅法，可以看到其查和插⼊分别使⽤专⽤接⼝:HASH_FIND_INT和
HASH_ADD_INT。
4.2． 字符指针char类型key与字符数组char key[100]类型key
特别注意在Strting类型中，uthash对指针char和字符数组（例如char key[100]）做了区分，这两种情况下使⽤的接⼝函数时不⼀样的。在添加的时候，
key的类型为指针时使⽤接⼝函数HASH_ADD_KEYPTR，key的类型为字符数组时，使⽤接⼝函数HA
SH_ADD_STR，除了添加的接⼝不⼀样外，其他的查、删除、变量等接⼝函数都是⼀样的。
4.3．使⽤地址作为key
在uthash中也可使⽤地址做key进⾏hash操作，使⽤地址作为key值时，其类型为void*，这样它就可以⽀持任意类型的地址了。在使⽤地址作为key时，插⼊和查的专⽤接⼝函数为
HASH_ADD_PTR和HASH_FIND_PTR，其余接⼝是⼀样的。
4.3．其他⾮常⽤类型key
在uthash中还可使⽤结构体作为key，甚⾄可以采⽤组合的⽅式让多个值作为key，这些在其官⽅的⽹站张均有较详细的使⽤⽰例。在使⽤uthash需要注意以下⼏点：
在定义hash结构体时不要忘记定义UT_hash_handle的变量
需确保key值唯⼀，如果插⼊key-value对时，key值已经存在，再插⼊的时候就会出错。
不同的key值，其增加和查调⽤的接⼝函数不⼀样，具体可见第4节。⼀般情况下，不通类型的key，其插⼊和查接⼝函数是不⼀样的，删除、遍历、元素统计接⼝是通⽤的，特殊情况下，字符数组和字符串作为key值时，其插⼊接⼝函数不⼀样，但是查接⼝是⼀样的。5．完整程序例⼦
5.1．key类型为int的完整的例⼦
#include<stdio.h>/* gets */
#include<stdlib.h>/* atoi, malloc */
#include<string.h>/* strcpy */
#include"uthash.h"
struct my_struct {
int ikey;/* key */
char value[10];
UT_hash_handle hh;/* makes this structure hashable */
};
static struct my_struct *g_users =NULL;
void add_user(int mykey,char*value){
struct my_struct *s;
HASH_FIND_INT(users,&mykey, s);/* mykey already in the hash? */
if(s ==NULL){
s =(struct my_struct*)malloc(sizeof(struct my_struct));
s->ikey = mykey;
HASH_ADD_INT( users, ikey, s);/* ikey: name of key field */
}
strcpy(s->value, value);
}
struct my_struct *find_user(int mykey){
struct my_struct *s;
HASH_FIND_INT(users,&mykey, s);/* s: output pointer */
return s;
}
void delete_user(struct my_struct *user){
HASH_DEL(users, user);/* user: pointer to deletee */
free(user);
}
void delete_all(){
struct my_struct *current_user,*tmp;
HASH_ITER(hh, users, current_user, tmp){
HASH_DEL(users,current_user);/* delete it (users advances to next) */
free(current_user);/* free it */

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。