目录

(1)uthash介绍和下载地址

(2)uthash基本用法

1.定义自己要使用的哈希表结构体

2.初始化哈希表的头指针

3.插入数据(不同key类型对应不同函数)

4.查找数据(不同key类型对应不同函数)

5.获取键值对个数

6.排序

7.遍历

8.删除

(3)不同类型key值的uthash用法

1.字符串数组作为key

2.指针作为key

3.结构体作为key

(4)注意事项

插入元素时是重复key怎么办

删除数据时注意事项


(1)uthash介绍和下载地址

uthash是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等。该套开源代码采用宏的方式实现了hash函数的相关功能,支持c语言的任意数据结构作为key值(可以是基本类型,也可以是自定义的struct),甚至可以采用多个值作为key。

uthash使用所需文件:由于该代码采用宏的方式实现,所有的实现代码都在uthash.h文件中,因此只需要在自己的代码中包含该头文件即可。

uthash头文件下载地址:https://github.com/troydhanson/uthash

(2)uthash基本用法

1.定义自己要使用的哈希表结构体

如下所示,必须是结构体。

结构体可以有任意个成员,比如这里有4个成员。

变量名字也可以随便取。结构体名字也可以随便取,比如这里为Hash。

但是要包含UT_hash_handle hh这个成员,必须要有。不用对它赋值,就像下面这样就行。

后面我们会理解到,value就是这个结构体,key可以为这个结构体中的任意一种成员。

#include "uthash.h"

#define NAME_LEN 10

typedef struct {
    int id;
    int age;
    int grade;
    char name[NAME_LEN];

    UT_hash_handle hh;
} Hash;

2.初始化哈希表的头指针

初始化自己需要使用的哈希表,像下面这样(推荐用全局变量)

Hash *hashHead = NULL;

注意必须初始化为NULL,UTHash会根据指针是否为NULL进行判断是否需要初始化。

这里的hashHead指针叫做哈希表指针,类似于链表的头指针。

hashHead => key-value结构体 => key-value结构体 => key-value结构体

3.插入数据(不同key类型对应不同函数)

假设key类型为int,用HASH_ADD_INT

    Hash *data = (Hash *)malloc(sizeof(Hash));
    data->id = 1;
    data->age = 18;
    data->grade = 100;
    strcpy(data->name, "tom");
    
    HASH_ADD_INT(hashHead, id, data);

其中第一个参数为哈希表指针,第二个参数为哈希表结构体中的某个成员名,要将哪个成员作为key,就填哪个,第三个参数是value,为哈希表结构体指针。

4.查找数据(不同key类型对应不同函数)

假设key类型为int,用HASH_FIND_INT

    Hash *findRet = NULL;
    int key = 1;
    HASH_FIND_INT(hashHead, &key, findRet);

    if (findRet != NULL) {
        printf("%s\n", findRet->name);
    }

第一个参数为哈希表指针,第二个参数为待查找key的地址,第三个参数为传出参数,即查找到的value,找不到的话为NULL。

5.获取键值对个数

用HASH_COUNT

    int count = HASH_COUNT(hashHead);
    printf("%d\n", count);

6.排序

使用HASH_SORT,实现对哈希表中的元素排序。以下是先按照成绩降序,再年龄升序,再id升序排序的例子

int CmpFunc(Hash *a, Hash *b)
{
    /* 排序比较函数:
       返回值小于0表示不交换a和b,即升序 
       返回值小于0表示交换a和b,即降序
    */
    if (a->grade != b->grade) {
        return b->grade - a->grade;
    }

    if (a->age != b->age) {
        return a->age - b->age;
    }

    return a->id - b->id;
}


HASH_SORT(hashHead, CmpFunc);

7.遍历

使用HASH_ITER,实现对哈希表中元素的遍历

    Hash *curr = NULL;
    Hash *next = NULL;
    HASH_ITER(hh, hashHead, curr, next) {
        if (curr != NULL) {
            printf("curr grade=%d\n", curr->grade);
        }
        
        if (next != NULL) {
            printf("next grade=%d\n", next->grade);
        }
        
    }

curr和next这里是传出参数。

curr是遍历到的元素,next是curr的下一个元素。一般关注curr即可。

注意当curr为最后一个键值对时,next将会为NULL。

8.删除

使用HASH_DEL,实现对哈希表中元素的删除。

注意这里需要先找到哈希表中的目标元素,然后利用HASH_DEL进行删除,注意只是从哈希表中删除,然后再利用free进行内存回收。

    Hash *value = NULL;
    int boy_id = 1;
    HASH_FIND_INT(hashHead, &boy_id, value);
    
    if (value != NULL) {
        HASH_DEL(hashHead, value);
        free(value);
    }

如果要对哈希表中的全部元素删除,可遍历结合使用HASH_DEL

    Hash *curr = NULL;
    Hash *next = NULL;
    HASH_ITER(hh, hashHead, curr, next) {
        HASH_DEL(hashHead, curr);
        free(curr);
    }

(3)不同类型key值的uthash用法

不同类型key时,插入数据和查找数据的函数将会不同,其余基本还是相同的。

1.字符串数组作为key

比如哈希结构体Hash中成员chae name[10]

    // 设计一个数据
    Hash *data = (Hash *)malloc(sizeof(Hash));
    data->id = 1;
    data->age = 18;
    data->grade = 100;
    strcpy(data->name, "tom");

    // 以name作为key进行插入
    HASH_ADD_STR(hashHead, name, data);
    
    // 查找
    Hash *findRet = NULL;
    char boy_name[] = "tom";
    HASH_FIND_STR(hashHead, boy_name, findRet);

    if (findRet != NULL) {
        printf("%s\n", findRet->name);
    }

2.指针作为key

示例代码如下,注意查找时是传入指针的地址

#include <stdio.h>  
#include <string.h>

#include "uthash.h"

#define NAME_LEN 10

typedef struct {
    void *key;
    int id;
    int age;
    int grade;
    char name[NAME_LEN];

    UT_hash_handle hh;
} Hash;

Hash *hashHead = NULL;


int main() 
{   
    // 某个值
    int *index = (int *)malloc(sizeof(int));
    *index = 99;

    // 设计一个数据
    Hash *data = (Hash *)malloc(sizeof(Hash));
    data->key = index;
    data->id = 1;
    data->age = 18;
    data->grade = 100;
    strcpy(data->name, "tom");

    // 以指针作为key进行插入
    HASH_ADD_PTR(hashHead, key, data);
    
    // 查找
    Hash *findRet = NULL;
    HASH_FIND_PTR(hashHead, &index, findRet); // 注意这里需要 &index 


    if (findRet != NULL) {
        printf("%s\n", findRet->name);
    }

    return 0;  
}

3.结构体作为key

插入用HASH_ADD,与之前相比,多了两个参数,一个句柄hh,一个结构体大小

查找用HASH_FIND,与之前相比,多了两个参数,一个句柄hh,一个结构体大小

示例代码如下

#include <stdio.h>  
#include <string.h>

#include "uthash.h"

#define NAME_LEN 10

typedef struct {
    int id;
    int age;
    int grade;
    
} KeyStruct;

typedef struct {
    KeyStruct key;
    
    char name[NAME_LEN];

    UT_hash_handle hh;
} Hash;

Hash *hashHead = NULL;


int main() 
{   
    // 设计一个数据
    Hash *data = (Hash *)malloc(sizeof(Hash));
    data->key.age = 18;
    data->key.grade = 100;
    data->key.id = 1;

    strcpy(data->name, "tom");

    // 以结构体作为key进行插入
    HASH_ADD(hh, hashHead, key, sizeof(KeyStruct), data);
    
    // 查找
    Hash *findRet = NULL;
    HASH_FIND(hh, hashHead, data, sizeof(KeyStruct), findRet);

    if (findRet != NULL) {
        printf("%s\n", findRet->name);
    }


    return 0;  
}

(4)注意事项

插入元素时是重复key怎么办

当使用 HASH_ADD_INT(或类似的 HASH_ADD 宏,但指定了整数类型作为键)向 uthash 哈希表中添加元素时,如果哈希表中已经存在一个具有相同键(key)的元素,那么新元素不会替换旧元素,而是会导致未定义行为(undefined behavior, UB)。

uthash 库没有提供直接的机制来更新已存在的键的值,它主要设计用于插入新元素和查找元素。如果你尝试使用相同的键插入一个新元素,而该键已经存在于哈希表中,uthash 不会自动合并或更新旧元素。相反,它可能会破坏哈希表的内部结构,导致数据损坏、内存泄漏或程序崩溃等问题。

如果你需要更新哈希表中已存在元素的值,你应该首先使用 HASH_FIND_INT(或相应的查找宏)来查找该元素。如果找到了,你可以直接修改该元素的值。如果没有找到,你可以使用 HASH_ADD_INT 来插入新元素。

下面是一个简单的示例,展示了如何安全地更新哈希表中已存在元素的值:

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include "uthash.h"  
  
typedef struct {  
    int id;      // 假设这是我们的键  
    int value;   // 我们要更新的值  
    UT_hash_handle hh;  
} HashElement;  
  
HashElement *hashHead = NULL;  
  
void update_or_add_element(int id, int newValue) {  
    HashElement *element;  
    HASH_FIND_INT(hashHead, &id, element);  
    if (element != NULL) {  
        // 如果元素已存在,则更新其值  
        element->value = newValue;  
    } else {  
        // 如果元素不存在,则创建并插入新元素  
        element = malloc(sizeof(HashElement));  
        if (element == NULL) {  
            fprintf(stderr, "Memory allocation failed\n");  
            exit(EXIT_FAILURE);  
        }  
        element->id = id;  
        element->value = newValue;  
        HASH_ADD_INT(hashHead, id, element);  
    }  
} 


void free_hash_table()
{
    HashElement *curr = NULL;
    HashElement *next = NULL;
    HASH_ITER(hh, hashHead, curr, next) {
        HASH_DEL(hashHead, curr);
        free(curr);
    }
}
  
int main() 
{  
    // 插入一些初始元素  
    update_or_add_element(1, 100);  
    update_or_add_element(2, 200);  
  
    // 尝试更新已存在的元素 
    // 将id为1的元素的值更新为150  
    update_or_add_element(1, 150);  
  
    // 查找并打印更新后的值  
    HashElement *element;
    int target_key = 1;  
    HASH_FIND_INT(hashHead, &target_key, element);  
    if (element != NULL) {  
        printf("Value for id 1: %d\n", element->value); // 应该输出 150  
    }  
  
    // 释放哈希表中的所有元素
    free_hash_table(); 
  
    return 0;  
}

删除数据时注意事项

如果你尝试传入一个不是哈希表中元素或键的地址来删除数据,那么结果将是未定义的。可能导致程序崩溃、数据损坏、或者无效果等。

为了避免这些问题,你应该始终确保:

  • 使用正确的键或指向哈希表中元素的指针来执行删除操作。
  • 如果你有指向哈希表中某个元素的指针,并且想要删除它,你应该直接使用该指针(确保它是指向包含 UT_hash_handle 成员的结构体的指针)和 HASH_DEL 宏。
  • 如果你只有键的值,你应该先使用查找宏(如 HASH_FIND_INT)来找到对应的元素,然后再使用 HASH_DEL 宏来删除它。

这里是一个简单的示例,展示了如何正确地删除哈希表中的元素:

#include <stdio.h>  
#include <stdlib.h>  
#include "uthash.h"  
  
typedef struct {  
    int id;  
    char name[50];  
    UT_hash_handle hh;  
} HashElement;  
  
HashElement *hashHead = NULL;  
  
void delete_element(int id) {  
    HashElement *element;  
    HASH_FIND_INT(hashHead, &id, element);  
    if (element != NULL) {  
        HASH_DEL(hashHead, element);  
        free(element); // 不要忘记释放内存  
    }  
}  

end

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部