c实现Hash表

c实现Hash表目录 一 简介 二 hash 表结构图 三 结构定义 四 成员函数 初始化 销毁 辅助函数 辅助函数 添加 删除结点 查找 打印函数 测试 一 简介 使用 crc16 作为 hash 函数 使用拉链法解决 hash 冲突 简单的 hash 表 二 hash 表结构图 三

大家好,我是讯享网,很高兴认识大家。

目录

一、简介

二、hash表结构图

三、结构定义

四、成员函数

初始化

销毁

辅助函数

辅助函数

添加

删除结点

查找

打印函数

测试


一、简介

使用crc16作为hash函数;


讯享网

使用拉链法解决hash冲突;

简单的hash表;

二、hash表结构图

三、结构定义

1.hash函数:定义hash函数类型为接收void*类型和内存长度为参数的函数,返回整数。这里具体使用crc16作为hash函数的实现。

typedef uint16_t (*hash_func_t)(void *, int); uint16_t myhash(void *key, int len) { return crc16((const char *)key, len); } 

讯享网

2.hash结点结构:结点内自然要保留key,value。因为可以存任意类型的内存数据,所以使用void*。又因为使用的拉链法解决冲突,使用双向链表。使用双向链表的另外一个好处是方便删除。

讯享网typedef struct hash_node { void *key; void *value; struct hash_node *pre; struct hash_node *next; } hash_node_t;

     

3.hash表结构:buckets是桶的大小;hash_func 为hash函数;nodes 为桶数组,是一个指针数组。

typedef struct hash { int buckets; hash_func_t hash_func; hash_node_t nodes; } hash_t;

四、成员函数

初始化

        可以看出,hash表的桶子树是固定的。当元素越多,hash表的负载因子越高,性能就越低 :(。

讯享网hash_t *hash_init(int buckets) { if (buckets < 1) { printf("buckets must greater than 0"); return NULL; } hash_t *hash = (hash_t *)malloc(sizeof(hash_t)); hash->buckets = buckets; hash->hash_func = myhash; hash->nodes = (hash_node_t )malloc(sizeof(hash_node_t *) * buckets); return hash; }

销毁

void hash_destory(hash_t hash) { if (*hash == NULL) { return; } free((*hash)->nodes); free((*hash)); *hash = NULL; }

辅助函数

        根据key找桶,该函数为基础函数,所有地方都用得着。

讯享网//辅助函数,根据key找桶 hash_node_t key_to_bucket(const hash_t *hash, void *key, int len) { uint16_t tmp = hash->hash_func(key, len); return &(hash->nodes[tmp % hash->buckets]); }

辅助函数

        根据key找结点,该函数在hash表的添加、删除、查找等操作都会被使用。

//辅助函数,找结点 hash_node_t *key_to_node(const hash_t *hash, void *key, int key_len) { hash_node_t bucket = key_to_bucket(hash, key, key_len); hash_node_t *node = *bucket; while (node != NULL && memcmp(node->key, key, key_len) != 0) { node = node->next; } return node; }

添加

        - 首先查找key是否存在,如果存在,则覆盖value。

        - 如果key不存在,需要判断key所属桶是否为空,然后特殊处理。

讯享网 void hash_add(hash_t *hash, void *key, int key_len, void *value, int value_len) { hash_node_t *node = key_to_node(hash, key, key_len); if (node != NULL) { if (node->value != NULL) { free(node->value); } node->value = malloc(value_len); memcpy(node->value, value, value_len); return; } node = (hash_node_t *)malloc(sizeof(hash_node_t)); node->key = malloc(key_len); memcpy(node->key, key, key_len); node->value = malloc(value_len); memcpy(node->value, value, value_len); node->next = NULL; node->pre = NULL; hash_node_t bucket = key_to_bucket(hash, key, key_len); if (*bucket == NULL) { *bucket = node; } else { hash_node_t *p = *bucket; (*bucket) = node; node->next = p; p->pre = node; } }

删除结点

        - 如果结点不在hash表中,则直接返回。

        - 如果结点在hash表中,需要判断结点是不是hash表的第一个结点,然后特殊处理。

bool hash_del(hash_t *hash, void *key, int key_len) { hash_node_t *node = key_to_node(hash, key, key_len); if (node == NULL) { return false; } hash_node_t bucket = key_to_bucket(hash, key, key_len); if (*bucket == node) { *bucket = node->next; if (node->next != NULL) { node->next->pre = NULL; } free(node); } else { node->pre->next = node->next; if (node->next != NULL) { node->next->pre = node->pre; } free(node); } return true; }

查找

讯享网bool hash_exist(const hash_t *hash, void *key, int key_len) { hash_node_t *node = key_to_node(hash, key, key_len); return node == NULL; } void *hash_find(const hash_t *hash, void *key, int key_len) { hash_node_t *node = key_to_node(hash, key, key_len); return node == NULL ? NULL : node->value; }

打印函数

void hash_print(const hash_t *hash) { printf("------------hash start-------------------\n"); for (int i = 0; i < hash->buckets; i++) { printf("bucket %d:", i); hash_node_t *node = hash->nodes[i]; while (node) { printf(" %s", (char *)node->key); node = node->next; } printf("\n"); } printf("------------hash end-------------------\n"); }

测试

讯享网void test06() { hash_t *hash = hash_init(2); if (hash == NULL) { printf("hash init faied!\n"); } for (int i = 1; i <= 1000; i++) { char buf[1024] = {0}; sprintf(buf, "k%d", i); hash_add(hash, buf, strlen(buf), "v", 2); } hash_print(hash); hash_destory(&hash); }
小讯
上一篇 2025-02-28 07:17
下一篇 2025-01-27 15:01

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/132935.html