↓跳到主要内容

uthash 学习笔记

·264 字·2 分钟
目录

uthash 是一个 C 语言的哈希表函数库，支持哈希表的各种操作，包括添加，删除，查找，排序等。你可以在 github 上下载到它的源码：

这个函数库在使用时只需要包含 uthash.h 头文件即可，没有二进制的库文件。

1. 数据结构 #

uthash 的哈希表是由多个结构体组成的双向链表实现的，一个结构体就是一个键值对，例如：

#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[10];
    UT_hash_handle hh;         /* makes this structure hashable */
};
  • id 就是键（key），名称和数据类型没有限制；
  • name 就是值（value），也可以是任何数据类型；
  • hh 是内部使用的 hash 处理句柄，UT_hash_handle 字段必须存在于你的结构中。它用于内部记录，使哈希表正常工作，它不需要初始化。可以被命名为任何标识符；

哈希句柄在 32 位系统中每个元素消耗约 32 个字节，在 64 位系统中每个元素消耗 56 个字节。其他的开销成本–桶和表–相比之下可以忽略不计。你可以使用 HASH_OVERHEAD 来获取哈希表的开销大小，单位是字节。

2. 基本操作 #

完整的例子可以在源码下的 tests/exapmle.c 文件中找到，可以执行 make example 进行编译。

2.1 声明 #

定义一个结构体类型的空指针，即声明了一个哈希表：

struct my_struct *users = NULL;

此时的哈希表示空的，我们需要先表中添加数据元素，在整个生命周期中，这个指针都指向链表的头结点。

2.2 添加 #

首先需要初始化一个数据元素，也就是定义一个 struct my_struct 变量，并分配空间，然后调用 HASH_ADD （这里我们使用方便的宏 HASH_ADD_INT，它为 int 类型的 key 提供了简化的用法）方法，将其添加到哈希表中：

void add_user(int user_id, char *name) {
    struct my_struct *s;

    s = malloc(sizeof(struct my_struct));
    s->id = user_id;
    strcpy(s->name, name);
    HASH_ADD_INT( users, id, s );  /* id: name of key field */
}

HASH_ADD_INT 的第一个参数是哈希表的指针，第二个参数是结构体中 key 的变量名，最后一个参数是需要加入哈希表的元素。一个元素添加到哈希表后，就不能修改它的 key 的值，必须从哈希表中删除后，才能修改。

2.3 查询 #

可以调用 HASH_FIND （这里我们使用方便的宏 HASH_ADD_INT，它为 int 类型的 key 提供了简化的用法）查询某个 key 的 value ：

struct my_struct *find_user(int user_id) {
    struct my_struct *s;

    HASH_FIND_INT( users, &user_id, s );  /* s: output pointer */
    return s;
}

第一个参数是哈希表的指针，第二个参数是 key 的值，第三参数是返回的结果，就是给定 key 的结构体指针，如果没找到，就返回 NULL 。

通常在添加之前要查询一下 key 是否已经存在，避免发生冲突。

2.4 删除 #

要从哈希表中删除一个元素，必须先获取这个元素的指针（可以用 HASH_FIND），然后调用 HASH_DEL ：

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 就是要删除的元素，删除后，uthash 不会自动释放 user 指向的内存，可以调用 free() 手动释放，可以继续其他工作，比如修改这个键值对。

当删除的是哈希表的第一个元素时，users 的值是会改变的，它会继续指向新的头结点。

如果要删除所有元素，可以调用 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  */
  }
}

如果清空哈希表时，并不想释放所有元素的空间，可以直接调用：

HASH_CLEAR(hh, users);

之后，users 就会变为空指针。

2.5 统计 #

获取哈希表中元素总数时，可以调用 HASH_COUNT ：

unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);

如果哈希表是空的，会返回 0 。

↑