C语言中的哈希（uthash）说明(demo示例)

超、凢脫俗 2023-10-04 23:08 15阅读 0赞

## **1. C语言中的哈希** ##

由于C语言本身不存在哈希，但是当需要使用哈希表的时候自己构建哈希会异常复杂。因此，我们可以调用开源的第三方头文件uthash，这只是一个头文件：uthash.h。我们需要做的就是将头文件复制到您的项目中，然后：\#include “uthash.h”。由于uthash仅是头文件，因此没有可链接的库代码。

uthash还包括三个额外的头文件，主要提供链表，动态数组和字符串。utlist.h为C结构提供了链接列表宏。utarray.h使用宏实现动态数组。utstring.h实现基本的动态字符串。

使用uthash添加，查找和删除通常是常数时间的操作，此哈希的目标是简约高效。它大约有1000行C。它会自动内联，因为它是作为宏实现的。

github下载链接： [GitHub - troydhanson/uthash: C macros for hash tables and more][GitHub - troydhanson_uthash_ C macros for hash tables and more]

src文件夹下的头文件

![5c0d4590fd5244caa218ac28e53cd44c.png][]

### 一个测试示例，检查是否可以使用uthash： ###

（注意：

1.*\#include "src/uthash.h"*填写实际的uthash.h路径

2.修改编译器配置：参照链接中方法1进行操作： [在VS2010以及更新版本的VS系列编译器中使用C语言不安全库函数时提示C4996（warning或error）的解决方法\_错误c4996-CSDN博客][VS2010_VS_C_C4996_warning_error_c4996-CSDN] ）:

#include <stdio.h>   /* printf */
    #include <stdlib.h>  /* atoi, malloc */
    #include <string.h>  /* strcpy */
    #include "src/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;
    }

## **2. 它能做什么？** ##

uthash支持对哈希表中的项目进行以下操作：

1.添加/替换

2.找到

3.删除

4.计数

5.迭代

6.排序

## **3. 详细说明测试代码的含义(简述uthash的使用)** ##

### 3.1 定义结构体 ###

这里我们将id作为一个索引值，也就是键值，将name作为value。

struct my_struct {
            int id;                    /* key */
            char name[21];
            UT_hash_handle hh;         /* makes this structure hashable */
        };
        /*声明哈希为NULL指针*/
        struct my_struct* users = NULL;    /* important! initialize to NULL */

注意：一定要包含UT\_hash\_handlehh;hh不需要初始化。它可以命名为任何名称，但是我们一般都命名为hh**。**uthash库提供的哈希表操作可实现类似于双向链表的功能，可以通过结构成员体hh的hh.prev和hh.next去获取当前结点的前一个结点或者后一个结点

### 3.2 添加 ###

HASH\_ADD\_INT表示添加的键值为int类型

HASH\_ADD\_STR表示添加的键值为字符串类型

HASH\_ADD\_PTR表示添加的键值为指针类型

HASH\_ADD表示添加的键值可以是任意类型

void add_user(int user_id, const char* name)
        {
            struct my_struct* s;
            /*重复性检查，当把两个相同key值的结构体添加到哈希表中时会报错*/
            HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
            /*只有在哈希中不存在ID的情况下，我们才创建该项目并将其添加。否则，我们只修改已经存在的结构。*/
            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\_ADD\_INT函数中，第一个参数users是哈希表，第二个参数id是键字段的名称。最后一个参数s是指向要添加的结构的指针。

### 3.3 查找 ###

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是输出变量。当可以在哈希表中找到相应键值时，s返回给定键的结构，当找不到时s返回NULL。

### 3.4 替换 ###

HASH\_REPLACE宏等效于HASH\_ADD宏，HASH\_REPLACE会尝试查找和删除项目外。如果找到并删除了一个项目，它还将返回该项目的指针作为输出参数。

示例程序中没有相关代码。

### 3.5 删除 ###

要从哈希表中删除结构，必须具有指向它的指针。（如果只有键，请先执行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是指向我们要从哈希中删除的结构的指针。

删除结构只是将其从哈希表中删除，并非free。何时释放结构的选择完全取决于自己；uthash永远不会释放您的结构

### 3.6 循环删除 ###

HASH\_ITER是一个宏定义，程序执行时被替换为一个循环。

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

### 3.7 删除哈希表所有元素 ###

如果您只想删除所有项目，但不释放它们或进行每个元素的清理，则可以通过一次操作更有效地做到这一点：

HASH_CLEAR(hh,users);

之后，列表头（此处为users）将设置为NULL。

### 3.8 计算哈希表元素个数 ###

temp = HASH_COUNT(users);
        printf("there are %d users\n", temp);
        break;

当users为NULL时，HASH\_COUNT会返回0.

### 3.9 遍历哈希表中的所有项目 ###

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

还有一个hh.prev指针，可用于从任何已知项开始向后迭代哈希。

由于hh.prev和hh.next字段的缘故，可以在哈希中向前和向后迭代。可以通过重复跟随这些指针来访问哈希中的所有项目，因此哈希也是**双链表**。

### 3.10 排序哈希表 ###

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)

\*/

by\_name和by\_id的两个比较函数示例。

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

两个使用比较函数的排序函数示例。

HASH_SORT(users, by_name);
        HASH_SORT(users, by_id);

### 3.11 测试示例简单示例截图 ###

加入key和valve的输入和输出

![a94b04c48dfd4aa7b0260531b8dafadc.png][]

## 4. 键值的各种类型举例 ##

### **4.1 整型键值** ###

当键值为整型时，可以使用HASH\_ADD\_INT和HASH\_FIND\_INT。（对于所有类型的键，其他操作（例如HASH\_DELETE和）HASH\_SORT都是相同的）。

### **4.2 字符串键值** ###

当键值为字符串时，具体要使用那个函数取决于结构体中的键值为字符串数组还是字符串指针。 这一点很重要。当结构体中的键值为字符串数组时，使用HASH\_ADD\_STR(STR就是字符串string缩写)。键值为字符串指针时使用HASH\_ADD\_KEYPTR(PTR就是指针pointer缩写)。接下来给出两个例子参考。

#### **当结构体中的键值为字符串数组时** ####

#include <string.h>  /* strcpy */
    #include <stdlib.h>  /* malloc */
    #include <stdio.h>   /* printf */
    #include "src/uthash.h"
    
    struct my_struct {
        char name[10];             /* key (string is WITHIN the structure) */
        int id;
        UT_hash_handle hh;         /* makes this structure hashable */
    };
    
    
    int main(int argc, char* argv[]) {
        const char* names[] = { "joe", "bob", "betty", NULL };
        struct my_struct* s, * tmp, * users = NULL;
    
        for (int i = 0; names[i]; ++i) {
            s = (struct my_struct*)malloc(sizeof * s);
            strcpy(s->name, names[i]);
            s->id = i;
            HASH_ADD_STR(users, name, s);
        }
    
        HASH_FIND_STR(users, "betty", s);
        if (s) printf("betty's id is %d\n", s->id);
    
        /* free the hash table contents */
        HASH_ITER(hh, users, s, tmp) {
            HASH_DEL(users, s);
            free(s);
        }
        return 0;
    }

#### **当结构体中的键值为字符串指针时** ####

#include <string.h>  /* strcpy */
    #include <stdlib.h>  /* malloc */
    #include <stdio.h>   /* printf */
    #include "src/uthash.h"
    
    struct my_struct {
        const char* name;          /* key */
        int id;
        UT_hash_handle hh;         /* makes this structure hashable */
    };
    
    
    int main(int argc, char* argv[]) {
        const char* names[] = { "joe", "bob", "betty", NULL };
        struct my_struct* s, * tmp, * users = NULL;
    
        for (int i = 0; names[i]; ++i) {
            s = (struct my_struct*)malloc(sizeof * s);
            s->name = names[i];
            s->id = i;
            HASH_ADD_KEYPTR(hh, users, s->name, strlen(s->name), s);
        }
    
        HASH_FIND_STR(users, "betty", s);
        if (s) printf("betty's id is %d\n", s->id);
    
        /* free the hash table contents */
        HASH_ITER(hh, users, s, tmp) {
            HASH_DEL(users, s);
            free(s);
        }
        return 0;
    }

### **4.3 指针键值** ###

#include <stdio.h>
    #include <stdlib.h>
    #include "src/uthash.h"
    
    typedef struct {
        void* key;
        int i;
        UT_hash_handle hh;
    } el_t;
    
    el_t* hash = NULL;
    char* someaddr = NULL;
    
    int main() {
        el_t* d;
        el_t* e = (el_t*)malloc(sizeof * e);
        if (!e) return -1;
        e->key = (void*)someaddr;
        e->i = 1;
        HASH_ADD_PTR(hash, key, e);
        HASH_FIND_PTR(hash, &someaddr, d);
        if (d) printf("found\n");
    
        /* release memory */
        HASH_DEL(hash, e);
        free(e);
        return 0;
    }

### **4.4 结构体键值** ###

在将项目添加到哈希或查找项目之前，必须将结构体键值中的元素清零。

#include <stdlib.h>
    #include <stdio.h>
    #include "src/uthash.h"
    
    typedef struct {
        char a;
        int b;
    } record_key_t;
    
    typedef struct {
        record_key_t key;
        /* ... other data ... */
        UT_hash_handle hh;
    } record_t;
    
    int main(int argc, char* argv[]) {
        record_t l, * p, * r, * tmp, * records = NULL;
    
        r = (record_t*)malloc(sizeof * r);
        /*结构体键值清零*/
        memset(r, 0, sizeof * r);
        r->key.a = 'a';
        r->key.b = 1;
        HASH_ADD(hh, records, key, sizeof(record_key_t), r);
    
        memset(&l, 0, sizeof(record_t));
        l.key.a = 'a';
        l.key.b = 1;
        HASH_FIND(hh, records, &l.key, sizeof(record_key_t), p);
    
        if (p) printf("found %c %d\n", p->key.a, p->key.b);
    
        HASH_ITER(hh, records, p, tmp) {
            HASH_DEL(records, p);
            free(p);
        }
        return 0;
    }

## 5.常用宏参考 ##

### **4.1 类型宏** ###

HASH\_ADD\_INT(head,keyfield\_name, item\_ptr)

HASH\_REPLACE\_INT(head,keyfiled\_name, item\_ptr,replaced\_item\_ptr)

HASH\_FIND\_INT(head,key\_ptr, item\_ptr)

HASH\_ADD\_STR(head,keyfield\_name, item\_ptr)

HASH\_REPLACE\_STR(head,keyfield\_name,item\_ptr, replaced\_item\_ptr)

HASH\_FIND\_STR(head,key\_ptr, item\_ptr)

HASH\_ADD\_PTR(head,keyfield\_name, item\_ptr)

HASH\_REPLACE\_PTR(head,keyfield\_name, item\_ptr, replaced\_item\_ptr)

HASH\_FIND\_PTR(head,key\_ptr, item\_ptr)

HASH\_DEL(head,item\_ptr)

HASH\_SORT(head,cmp)

HASH\_COUNT(head)

### **4.2 通用宏** ###

HASH\_ADD(hh\_name,head, keyfield\_name, key\_len, item\_ptr)

HASH\_ADD\_BYHASHVALUE(hh\_name,head, keyfield\_name, key\_len, hashv, item\_ptr)

HASH\_ADD\_KEYPTR(hh\_name,head, key\_ptr, key\_len, item\_ptr)

HASH\_ADD\_KEYPTR\_BYHASHVALUE(hh\_name,head, key\_ptr, key\_len, hashv, item\_ptr)

HASH\_ADD\_INORDER(hh\_name,head, keyfield\_name, key\_len, item\_ptr, cmp)

HASH\_ADD\_BYHASHVALUE\_INORDER(hh\_name,head, keyfield\_name, key\_len, hashv, item\_ptr, cmp)

HASH\_ADD\_KEYPTR\_INORDER(hh\_name,head, key\_ptr, key\_len, item\_ptr, cmp)

HASH\_ADD\_KEYPTR\_BYHASHVALUE\_INORDER(hh\_name,head, key\_ptr, key\_len, hashv, item\_ptr, cmp)

HASH\_REPLACE(hh\_name,head, keyfield\_name, key\_len, item\_ptr, replaced\_item\_ptr)

HASH\_REPLACE\_BYHASHVALUE(hh\_name,head, keyfield\_name, key\_len, hashv, item\_ptr, replaced\_item\_ptr)

HASH\_REPLACE\_INORDER(hh\_name,head, keyfield\_name, key\_len, item\_ptr, replaced\_item\_ptr, cmp)

HASH\_REPLACE\_BYHASHVALUE\_INORDER(hh\_name,head, keyfield\_name, key\_len, hashv, item\_ptr, replaced\_item\_ptr, cmp)

HASH\_FIND(hh\_name,head, key\_ptr, key\_len, item\_ptr)

HASH\_FIND\_BYHASHVALUE(hh\_name,head, key\_ptr, key\_len, hashv, item\_ptr)

HASH\_DELETE(hh\_name,head, item\_ptr)

HASH\_VALUE(key\_ptr,key\_len, hashv)

HASH\_SRT(hh\_name,head, cmp)

HASH\_CNT(hh\_name,head)

HASH\_CLEAR(hh\_name,head)

HASH\_SELECT(dst\_hh\_name,dst\_head, src\_hh\_name, src\_head, condition)

HASH\_ITER(hh\_name,head, item\_ptr, tmp\_item\_ptr)

HASH\_OVERHEAD(hh\_name,head)

### **4.3 参数说明** ###

**hh\_name**：UT\_hash\_handle结构中字段的名称。俗称 hh。

**head**：结构指针变量，用作哈希的“头”。如此命名是因为它最初指向添加到哈希中的第一项。

**keyfield\_name**：结构中键字段的名称。（对于多字段键，这是键的第一个字段）。如果您不熟悉宏，则将字段名称作为参数传递似乎很奇怪。请参阅注释。

**key\_len**：键字段的长度（以字节为单位）。例如，对于整数键，它是sizeof(int)，而对于字符串键，它是strlen(key)。

**key\_ptr**：对于HASH\_FIND，这是指向要在哈希中查找的键的指针(由于它是指针，因此您不能在此处直接传递文字值)。对于 HASH\_ADD\_KEYPTR，这是要添加的项的键的地址。

**hashv**：提供的键的哈希值。这是BYHASHVALUE宏的输入参数，是的输出参数HASH\_VALUE。如果您要重复查找相同的键，则重用缓存的哈希值可以优化性能。

** item\_ptr**：指向要添加，删除，替换或查找的结构的指针，或迭代期间的当前指针。这是一个输入参数HASH\_ADD， HASH\_DELETE和HASH\_REPLACE宏，和用于输出参数HASH\_FIND 和HASH\_ITER。（当HASH\_ITER用于迭代时，tmp\_item\_ptr 是与item\_ptr内部使用的类型相同的另一个变量）。

**replace\_item\_ptr**：用于HASH\_REPLACE宏。这是一个输出参数，设置为指向替换的项目（如果没有替换的项目，则设置为NULL）。

**cmp**：指向比较函数的指针，该函数接受两个参数（指向要比较的项目的指针），并返回一个int值，该值指定第一个项目应在第二个项目之前，等于还是之后排序（如strcmp）。

**condition**：接受单个参数的函数或宏（指向结构的空指针，需要将其强制转换为适当的结构类型）。如果应“选择”结构以将其添加到目标哈希中，则函数或宏的值应为非零值。

[GitHub - troydhanson_uthash_ C macros for hash tables and more]: https://github.com/troydhanson/uthash
[5c0d4590fd5244caa218ac28e53cd44c.png]: https://img-blog.csdnimg.cn/img_convert/5c0d4590fd5244caa218ac28e53cd44c.png
[VS2010_VS_C_C4996_warning_error_c4996-CSDN]: https://blog.csdn.net/xijinno1/article/details/129414996
[a94b04c48dfd4aa7b0260531b8dafadc.png]: https://img-blog.csdnimg.cn/img_convert/a94b04c48dfd4aa7b0260531b8dafadc.png