目录
- 前言
- 1、简单介绍
- C语言中的HashTable
- 支持的操作
- 复杂度
- 非库文件
- 2、用法
- 结构体定义
- 键值
- key的唯一性
- UT_hash_handle
- 内存消耗
- 结构体声明
- 添加
- 查询
- 删除
- 清空哈希表
- 统计hash表中的已经存在的元素数
- 遍历
- 排序
- key为int类型的完整示例
前言
本文旨在总结介绍C开源hash项目。文章大部分内容均来自uthash的英文使用文档。官方源码
uthash实现了常见的hash操作函数。使用uthash的代码时只需要包含头文件“uthash.h”即可。该套代码所有的实现都在uthash.h文件中,因此只需要在自己的代码中包含头文件即可。
1、简单介绍
C语言中的HashTable
在C语言中不提供hash,这个软件提供一种数据结构,使得C支持哈希操作。
支持的操作
在哈希表中支持以下操作
add delete find count iterate sort
复杂度
add delete find都是O(1)的时间复杂度。
非库文件
NO,它仅是个头文件:uthash.h。你仅需要将这个头文件复制到你工程中即可。
#include "uthash.h"
2、用法
结构体定义
定义一个结构体
#include "uthash.h"
struct my_struct {
int id;
char name[10];
UT_hash_handle hh;
};
键值
对于key的数据类型没有限制
key的唯一性
在向哈希表中增加项目时,必须确保key值是唯一的。因此,在向哈希表中添加项目是,必须确保key没有被使用。可以通过使用HASH_FIND来确定key值是否已经在哈希表中存在。
UT_hash_handle
该句柄必须存在结构体中,它的作用是使得该哈希结构体可以工作。
内存消耗
一个哈希表项目在32位操作系统中占用32个字节。在64位操作系统中占用56个字节。可以使用HASH_OVERHEAD来获取哈希表的开销大小(以字节为单位)
结构体声明
struct my_struct *users = NULL;
添加
key类型的不同,会导致调用的宏不同,在此我们以Key为int简单示例
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);
}
查询
需要通过键值去查询哈希表。在下面代码中,users是哈希表,&user_id是键值。s是返回值。
如果键值存在,则会查询并返回对应的结构体指针,否则返回NULL。
struct my_struct *find_user(int user_id) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s);
return s;
}
中间的变量是一个key的指针,不能直接传输一个字符串,而是需要将这个字符串赋值给一个变量,将变量的地址传输进去。
删除
从哈希表中删除一个结构体,必须已知一个指向该结构体的指针。(如果你仅有一个key,需要通过HASH_FIND去得到该结构体指针。
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);
}
}
统计hash表中的已经存在的元素数
unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);
如果users是NULL,这种情况count是0。
遍历
通过hh.next可以对整个哈希表从头至尾进行遍历。
void print_users() {
struct my_struct *s;
for (s = users; s != NULL; s = s->hh.next) {
printf("user id %d: name %s\n", s->id, s->name);
}
}
同时也可以使用hh.prev从某个节点向前进行遍历。
由于 hh.prev 和 hh.next 字段,可以前后遍历散列中的项目。 因此散列也是一个双向链表。
排序
HASH_SORT(users, name_sort);
第二个参数是一个指向比较函数的指针。 它必须接受两个指针参数(要比较的项目),并且如果第一个项目分别在第二个项目之前、等于或之后排序,则必须返回一个小于零、零或大于零的 int。 (这与标准 C 库中 strcmp 或 qsort 使用的约定相同)。
下面,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);
}
当哈希中的项目被排序时,第一个项目可能会改变位置。 在上面的例子中,用户可能在调用 HASH_SORT 后指向不同的结构。
key为int类型的完整示例
包含"uthash.h"头文件后,代码可以直接在CodeBlock上直接运行。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"
struct my_struct {
int id;
char name[10];
UT_hash_handle hh;
};
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;
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\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(" 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)) {
case 1:
printf("name?\n");
add_user(id++, gets(in));
break;
case 2:
printf("id?\n");
gets(in); id = atoi(in);
printf("name?\n");
add_user(id, gets(in));
break;
case 3:
printf("id?\n");
s = find_user(atoi(gets(in)));
printf("user: %s\n", s ? s->name : "unknown");
break;
case 4:
printf("id?\n");
s = find_user(atoi(gets(in)));
if (s) delete_user(s);
else printf("id unknown\n");
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\n", num_users);
break;
case 10:
running = 0;
break;
}
}
delete_all();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)