C语言uthash的用法

文章目录

• 1 定义一个哈希表
• • 键
  • 值
  • UT_hash_handle
• 2 哈希 *** 作
• • 声明
  • 添加
  • 查找
  • 删除
  • 获取哈希表中元素个数
  • 迭代
  • 排序
• 3 案例
• 键的使用

官网解释：https://troydhanson.github.io/uthash/userguide.html
在使用之前，我们必须包含uthash.h的头文件，你需要将该头文件加入到你的项目中

#include "uthash.h"

1 定义一个哈希表

我们直到，在哈希表中，最重要的就是键和值，在 utash 中，哈希表由结构体组成。 每个结构体代表一个键值关联。 一个或多个结构体里的域构成键， 该结构指针就是值。

我们定义一个my_struct 结构体，用id的值作为键值，my_struct 的实例指针作为值

#include "uthash.h"

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

键

键的数据类型或名称没有限制，可以具有任何名称和数据类型。但是再把值添加到哈希表之前，必须保证键没有被使用，保证键的唯一性。可以使用HASH_FIND检查哈希表是否已存在该键。

值

值就是结构体实例的指针

UT_hash_handle

UT_hash_handle 字段必须要存在于你定义的结构体中，它不需要初始化，可以命名任何东西，比如hh，UT_hash_handle 用来标记该结构体是哈希表。

2 哈希 *** 作 声明

我们必须将声明的哈希表结构体初始化为NULL指针

struct my_struct *users = NULL;    /* important! initialize to NULL */

添加

按照合适非方法分配和初始化结构体，初始化必须保证键是唯一值，然后调用HASH_ADD添加到哈希表中，这里我们使用便利宏 HASH_ADD_INT，它为 int 类型的键提供了简化的用法。

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

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

HASH_ADD_INT 的第一个参数是哈希表，第二个参数是键的名称。，在这里，这是 id。 最后一个参数是指向要添加的结构指针。

将结构添加到哈希表后，不要更改其键的值。 我们要从哈希中删除该项目，更改键值，然后重新添加它。

在上面的示例中，我们没有检查 user_id 是否已经是哈希中某个现有项目的键值。 如果你的程序有可能生成重复键，则必须在将键添加到散哈希表之前显式检查唯一性。 如果键已经在散列中，可以简单地修改散列中的现有结构，而不是添加项。 将具有相同键的两个项目添加到哈希表是错误的。

让我们重写 add_user 函数来检查 id 是否在哈希中。 只有当 id 不存在于散列中时，我们才创建项目并添加它。 否则我们只是修改已经存在的结构。

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);
}

查找

要在哈希中查找结构体，你需要它的键。 然后调用 HASH_FIND。 （这里我们使用便利宏 HASH_FIND_INT 来处理 int 类型的键）。

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

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

这里，哈希表是users，&user_id 指向键（本例中为整数）。 最后，s 是 HASH_FIND_INT 的输出变量。 最终结果是 s 指向具有给定键的结构，或者如果在散列中找不到键，则为 NULL。

删除

要从哈希中删除结构体，你必须有一个指向它的指针。 （如果你只有键，首先做一个 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 是指向我们要从哈希中删除的结构的指针。

删除所有元素：HASH_ITER 宏是一个删除安全的迭代构造，它扩展为一个简单的 for 循环。

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_COUNT 获取哈希表中的结构体数：

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

迭代

你可以通过从头开始并跟随 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.next 指针时，以“插入顺序”访问散列中的项目。 你可以使用 HASH_SORT 将项目排序为新顺序。

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)
   */
}

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);
}

void sort_by_name() {
    HASH_SORT(users, by_name);
}

void sort_by_id() {
    HASH_SORT(users, by_id);
}

3 案例

#include    /* printf */
#include   /* atoi, malloc */
#include   /* 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 = ';'return
    ; buf}
int

main ()int
{
    = id 1 ;int
    = running 1 ;struct
    my_struct * ;sint
    ; tempwhile

    ( )runningprintf {
        (" 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
                (,tempgetl ("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
                ( )sdelete_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 ;}
如果是字符串当键，有两种，一种是char * ，使用XXX_XXX_KETPTR，两一种是char [] ,比如char name[10]，使用XXX_XXX_STR

键的使用

1. 如果指针自己是键，使用XXX_XXX_PTR，如果指针指向的是键，比如char *，char *name = “aaa”，aaa作为键，则使用XXX_XXX_KEYPTR
2. 如果是整数，使用XXX_XXX_INT
3. 键可是是任何数据类型，任何数据类型可以使用通用宏HASH_ADD和HASH_FIND