Uthash：C语言哈希表库

一、C语言哈希

哈希表是一种重要的数据结构，它可以在O(1)时间复杂度内完成常见的查找、插入、删除操作。在C语言中，我们也可以通过自己实现哈希表来完成这些操作。

哈希表的实现要点是通过哈希函数将关键字映射为数字索引，然后将该关键字存储在索引对应的位置上，这个位置也被称为哈希桶。哈希函数的好坏会直接影响哈希表的性能。例如，当哈希函数将所有的关键字都映射到同一个桶上时，哈希表就退化为一个线性表，查找、插入、删除操作的时间复杂度均为O(n)。

以下是一个简单的C语言哈希表的示例代码：

#define HASHSIZE 101
struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
};
static struct nlist *hashtab[HASHSIZE];
unsigned hash(char *);
struct nlist *lookup(char *);
struct nlist *install(char *, char *);

二、C语言哈希库

虽然我们可以自己实现一个哈希表，但是这并不是一个简单的任务，我们需要考虑哈希函数的设计、哈希桶的大小、哈希冲突的处理等问题。因此，有一些C语言的哈希库可以供我们使用，例如Uthash、GHash等。

Uthash是一个非常流行的C语言哈希库，它的使用非常简单，只需要将哈希表元素中的成员变量标记为UTHASH_HANDLE宏即可。下面是一个使用Uthash的示例代码：

#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 *user_name) {
    struct my_struct *s;
    s = (struct my_struct*)malloc(sizeof(struct my_struct));
    s->id = user_id;
    strcpy(s->name, user_name);
    HASH_ADD_INT(users, id, s);
}

struct my_struct *find_user(int user_id) {
    struct my_struct *s;
    HASH_FIND_INT(users, &user_id, s);
    return s;
}

三、C语言自带的哈希函数

在C语言中，我们也可以使用自带的哈希函数，例如djb2、sdbm、crc32等。这些哈希函数的性能已经经过充分的测试和优化，可以满足我们绝大部分的哈希表需求。下面是一个使用djb2哈希函数的示例代码：

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

四、Uthash使用案例

下面是一个使用Uthash实现哈希表的示例代码。该代码实现了一个简单的键值对存储系统，支持插入、查找、更新、删除操作。由于Uthash底层使用了内存池技术，所以根本不需要手动对内存进行管理。代码自带注释，便于理解。

#include "uthash.h"
#include 
#include 
   

struct my_struct_t {
    char name[20];
    int age;
    UT_hash_handle hh;
};

struct my_struct_t *users = NULL;

void add_user(const char *name, int age) {
    struct my_struct_t *s;
    // check if the user already exists
    HASH_FIND_STR(users, name, s);
    if (s == NULL) {
        // create a new user
        s = (struct my_struct_t*)malloc(sizeof(struct my_struct_t));
        strncpy(s->name, name, sizeof(s->name));
        s->age = age;
        HASH_ADD_STR(users, name, s);
        printf("Add user %s:%d successfully.\n", name, age);
    }
    else {
        printf("User %s already exists, age updated to %d.\n", name, age);
        // update the existing user
        s->age = age;
    }
}

struct my_struct_t *find_user(const char *name) {
    struct my_struct_t *s;
    HASH_FIND_STR(users, name, s);
    if (s == NULL) {
        printf("User %s not found.\n", name);
        return NULL;
    }
    printf("User %s:%d found.\n", s->name, s->age);
    return s;
}

void delete_user(struct my_struct_t *s) {
    HASH_DEL(users, s);
    free(s);
}

void print_all_users() {
    struct my_struct_t *s;
    for (s = users; s != NULL; s = (struct my_struct_t*)(s->hh.next)) {
        printf("user %s:%d\n", s->name, s->age);
    }
}

void free_all_users() {
    struct my_struct_t *current_user, *tmp;
    HASH_ITER(hh, users, current_user, tmp) {
        HASH_DEL(users, current_user);
        free(current_user);
    }
}

int main() {
    add_user("Alice", 20);
    add_user("Bob", 25);
    add_user("Charlie", 30);
    add_user("Bob", 35);
    find_user("Alice");
    find_user("Bob");
    print_all_users();
    delete_user(find_user("Bob"));
    print_all_users();
    free_all_users();
    return 0;
}