C语言HashTable/HashSet库汇总

在https://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c里介绍了很多个相关的库。经过个人筛选，综合考虑执行效率、文档完善程度、支持的数据类型三方面，选择了uthash。
官方文档详见：http://troydhanson.github.io/uthash/userguide.html

*如果想当HashSet用，只需要value随便赋值即可

*如果只需要String类型的key和value，还可以考虑strmap

*之所以没选择python内置的libcfu（下载地址，官方文档），是因为它在Android的环境上编译时很多的问题。

简要范例 (详见官方文档)

1. 初始化

#include "uthash.h"

struct my_struct {
    int id; // key
    char name[10]; //value
    UT_hash_handle hh; // 必须有，让这个结构体hashable
};

struct my_struct *users = NULL; // 重要，必须初始化为NULL

2. 添加

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); // id: key的名字
    }
    strcpy(s->name, name);
}

3. 查找

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

4. 删除

void delete_user(struct my_struct *user) {
    HASH_DEL(users, user);
    free(user); //可选
}

参考官网的demo源码

#include <stdio.h>   /* printf */
#include <stdlib.h>  /* atoi, malloc */
#include <string.h>  /* strcpy */
#include "uthash.h"

struct my_struct {
    int id;                    /* key */
    char name[21];
    UT_hash_handle hh;         /* makes this structure hashable */
};

struct my_struct *users = NULL;

void add_user(int user_id, const 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 is the key field */
    }
    strcpy(s->name, name);
}

struct my_struct *find_user(int user_id)
{
    struct my_struct *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;
    struct my_struct *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->hh.next)) {
        printf("user id %d: name %s\n", s->id, s->name);
    }
}

int by_name(const struct my_struct *a, const struct my_struct *b)
{
    return strcmp(a->name, b->name);
}

int by_id(const struct my_struct *a, const struct my_struct *b)
{
    return (a->id - b->id);
}

const char *getl(const char *prompt)
{
    static char buf[21];
    char *p;
    printf("%s? ", prompt); fflush(stdout);
    p = fgets(buf, sizeof(buf), stdin);
    if (p == NULL || (p = strchr(buf, '\n')) == NULL) {
        puts("Invalid input!");
        exit(EXIT_FAILURE);
    }
    *p = '\0';
    return buf;
}

int main()
{
    int id = 1;
    int running = 1;
    struct my_struct *s;
    int temp;

    while (running) {
        printf(" 1. add user\n");
        printf(" 2. add or 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");
        switch (atoi(getl("Command"))) {
            case 1:
                add_user(id++, getl("Name (20 char max)"));
                break;
            case 2:
                temp = atoi(getl("ID"));
                add_user(temp, getl("Name (20 char max)"));
                break;
            case 3:
                s = find_user(atoi(getl("ID to find")));
                printf("user: %s\n", s ? s->name : "unknown");
                break;
            case 4:
                s = find_user(atoi(getl("ID to delete")));
                if (s) {
                    delete_user(s);
                } else {
                    printf("id unknown\n");
                }
                break;
            case 5:
                delete_all();
                break;
            case 6:
                HASH_SORT(users, by_name);
                break;
            case 7:
                HASH_SORT(users, by_id);
                break;
            case 8:
                print_users();
                break;
            case 9:
                temp = HASH_COUNT(users);
                printf("there are %d users\n", temp);
                break;
            case 10:
                running = 0;
                break;
        }
    }

    delete_all();  /* free any structures */
    return 0;
}

注意事项

1. 如果在Android/gcc编译时报fall-through between switch labels，则可以用pragma语句把uthash相关的代码括起来

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
// uthash相关代码
#pragma GCC diagnostic pop

其实还可以用__attribute__ ((fallthrough)); 但是实测没有pragma这种方法好。

1. 如果编译时报padding struct 'struct UT_hash_table' with 4 bytes to align 'tail'，可以按照https://github.com/troydhanson/uthash/issues/118#issue-223582662的回答，调整uthash.h中变量的顺序

2. 如果要当HashSet用，可能也需要额外声明一个变量，不然可能会出padding的问题，报padding struct 'struct fd_struct' with 4 bytes to align 'hh'，如下：

struct fd_struct {
    int fd; // key
    int padding; // 填充用，或者是char padding[10]之类的;
    UT_hash_handle hh;
};