C语⾔哈希表uthash的使⽤⽅法详解（附下载链接）
⽂章⽬录
1. uthash简介
  由于C语⾔本⾝不存在哈希，但是当需要使⽤哈希表的时候⾃⼰构建哈希会异常复杂。因此，我们可以调⽤开源的第三⽅头⽂件，这只是⼀个头⽂件：uthash.h。我们需要做的就是将头⽂件复制到您的项⽬中，然后：#include “uthash.h”。由于uthash仅是头⽂件，因此没有可链接的库代码。
  使⽤uthash添加，查和删除通常是常数时间的操作，此哈希的⽬标是简约⾼效。它⼤约有1000⾏C。它会⾃动内联，因为它是作为宏实现的。
  uthash还包括三个额外的头⽂件，主要提供链表，动态数组和字符串。utlist.h为C结构提供了链接列表宏。utarray.h使⽤宏实现动态数组。utstring.h实现基本的动态字符串。
2. uthash的使⽤
2.1 定义结构体
  这⾥我们将id作为⼀个索引值，也就是键值，将name作为value。
#include"uthash.h"
struct my_struct {
int id;/* key */
char name[10];
UT_hash_handle hh;/* makes this structure hashable */
};
/*声明哈希为NULL指针*/
struct my_struct *users =NULL;/* important! initialize to 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;
/*重复性检查，当把两个相同key值的结构体添加到哈希表中时会报错*/
HASH_FIND_INT(users,&user_id, s);/* id already in the hash? */
/*只有在哈希中不存在ID的情况下，我们才创建该项⽬并将其添加。否则，我们只修改已经存在的结构。*/
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);
}
  HASH_ADD_INT函数中，第⼀个参数users是哈希表，第⼆个参数id是键字段的名称。最后⼀个参数s是指向要添加的结构的指针。
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: output pointer */
return s;
}
  在上述代码中，第⼀个参数users是哈希表，第⼆个参数是user_id的地址（⼀定要传递地址）。最后s是输出变量。当可以在哈希表中到相应键值时，s返回给定键的结构，当不到时s返回NULL。
2.4 替换
  HASH_REPLACE宏等效于HASH_ADD宏，HASH_REPLACE会尝试查和删除项⽬外。如果到并删除了⼀个项⽬，它还将返回该项⽬的指针作为输出参数。
void replace_user(HashHead *head, HashNode *newNode){c语言下载什么
HashNode *oldNode =find_user(*head, newNode->id);
if(oldNode)
HASH_REPLACE_INT(*head, id, newNode, oldNode);
}
2.5 删除
  要从哈希表中删除结构，必须具有指向它的指针。（如果只有键，请先执⾏HASH_FIND以获取结构指针）。
void delete_user(struct my_struct *user){
HASH_DEL(users, user);/* user: pointer to deletee */
free(user);/* optional; it's up to you! */
}
  同样，这⾥users是哈希表，user是指向我们要从哈希中删除的结构的指针。
  删除结构只是将其从哈希表中删除，并⾮free 。何时释放结构的选择完全取决于⾃⼰；uthash永远不会释放您的结构
2.6 循环删除
  HASH_ITER是⼀个宏定义，程序执⾏时被替换为⼀个循环。
void delete_all(){
struct my_struct *current_user,*tmp;
HASH_ITER(hh, users, current_user, tmp){
HASH_DEL(users,current_user);/* delete; users advances to next */
free(current_user);/* optional- if you want to free  */
}
}
2.7 删除哈希表所有元素
  如果您只想删除所有项⽬，但不释放它们或进⾏每个元素的清理，则可以通过⼀次操作更有效地做到这⼀点：
HASH_CLEAR(hh,users);
  之后，列表头（此处为users）将设置为NULL。
2.8 计算哈希表元素个数
unsigned int num_users;
num_users =HASH_COUNT(users);
printf("there are %u users\n", num_users);
  当users为NULL时，HASH_COUNT会返回0.
2.9 遍历哈希表中的所有项⽬
void print_users(){
struct my_struct *s;
for(s=users; s !=NULL; s=s-&){
printf("user id %d: name %s\n", s->id, s->name);
}
}
  还有⼀个hh.prev指针，可⽤于从任何已知项开始向后迭代哈希。
  由于hh.prev和hh.next字段的缘故，可以在哈希中向前和向后迭代。可以通过重复跟随这些指针来访问哈希中的所有项⽬，因此哈希也是双链表。
2.10 排序哈希表
HASH_SORT( users, name_sort );
  第⼆个参数是指向⽐较函数的指针。它必须接受两个指针参数（要⽐较的项⽬），并且如果第⼀个项⽬分别在第⼆个项⽬之前，等于或之后排序，则必须返回⼩于零，零或⼤于零的int。 （这与标准C库中的strcmp或qsort使⽤的约定相同）。
int sort_function(void*a,void*b){
/* compare a to b (cast a and b appropriately)
* return (int) -1 if (a < b)
* return (int)  0 if (a == b)
* return (int)  1 if (a > b)
*/
}
  name_sort和id_sort的两个排序函数⽰例。
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 完整代码
#include<stdio.h>/* gets */
#include<stdlib.h>/* atoi, malloc */
#include<string.h>/* strcpy */
#include"uthash.h"
struct my_struct {
int id;/* key */
char name[10];
UT_hash_handle hh;/* makes this structure hashable */
};
struct my_struct *users =NULL;
void add_user(int user_id,char*name){
struct my_struct *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);
}
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: 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 */
}
}
void print_users(){
struct my_struct *s;
for(s=users; s !=NULL; s=(struct my_struct*)(s-&)){
printf("user id %d: name %s\n", 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\n");
printf(" 2. add/rename user by id\n");
printf(" 3. find user\n");
printf(" 4. delete user\n");
printf(" 4. delete user\n");
printf(" 5. delete all users\n");
printf(" 6. sort items by name\n");
printf(" 7. sort items by id\n");
printf(" 8. print users\n");
printf(" 9. count users\n");
printf("10. quit\n");
gets(in);
switch(atoi(in)){
case1:
printf("name?\n");
add_user(id++,gets(in));
break;
case2:
printf("id?\n");
gets(in); id =atoi(in);
printf("name?\n");
add_user(id,gets(in));
break;
case3:
printf("id?\n");
s =find_user(atoi(gets(in)));
printf("user: %s\n", s ? s->name :"unknown");
break;
case4:
printf("id?\n");
s =find_user(atoi(gets(in)));
if(s)delete_user(s);
else printf("id unknown\n");
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("there are %u users\n", num_users);
break;
case10:
running=0;
break;
}
}
delete_all();/* free any structures */
return0;
}
3. 键值的各种类型举例
3.1 整型键值
  当键值为整型时，可以使⽤HASH_ADD_INT和HASH_FIND_INT。（对于所有类型的键，其他操作（例如HASH_DELETE 和）HASH_SORT都是相同的）。
3.2 字符串键值

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