1. Python技术站首页
  2. C

C语言实现通用数据结构之通用集合(HashSet)

• C

C 语言实现通用数据结构之通用集合(HashSet)

什么是 HashSet

HashSet 是一种常用的数据结构，其实质就是一个无序不重复的元素集合。在 C 语言中，你可以使用 HashSet 存储任何类型的数据。

HashSet 的优点在于：

  1. 独立性，只关心数据的存储和操作，而不必关心数据类型；
  2. 方便性，对于处理过程，比起普通数组无需考虑顺序问题。

实现过程

下面是一个简化的实现步骤，通俗易懂。

基本原理

HashSet 包含以下基本操作：

  1. 初始化 HashSet 尺寸和加载因子。
  2. 插入元素。
  3. 判断元素是否存在。
  4. 删除元素。
  5. 清空 HashSet。

尽管 HashSet 的实现方法因平台而异，但如同任何数据结构一样，有许多共性。通过以下的操作，你可以大致了解 HashSet 的实现。

/** 元素类型 */
typedef struct HashSetType_s {
    uint32_t hash;   // 哈希值
    void *value;     // 元素值
} HashSetType;

/** 哈希表 */
typedef struct HashSet_s {
    uint32_t size;    // 哈希表大小
    float load_factor;// 哈希表负载因子

    uint32_t count;   // 哈希表元素总数
    HashSetType *map; // 元素映射表，数组

    /** 函数指针 **/
    uint32_t (*hash_func)(const void *value);         // 元素哈希函数
    int (*keycmp_func)(const void *a, const void *b);// 元素比较函数
    void (*destroy_func)(void *value);               // 元素销毁函数
} HashSet;

/** 创建 HashSet 对象 **/
HashSet *HashSet_create(int size, float load_factor,
                        uint32_t (*hash_func)(const void *value),
                        int (*keycmp_func)(const void *a, const void *b),
                        void (*destroy_func)(void *value));

/** 销毁 HashSet 对象 **/
void HashSet_destroy(HashSet **set);

/** 插入元素 **/
int HashSet_insert(HashSet *set, const void *value);

/** 查询元素是否存在 **/
int HashSet_exists(HashSet *set, const void *value);

/** 删除元素 **/
int HashSet_remove(HashSet *set, const void *value);

/** 元素数量 **/
uint32_t HashSet_count(HashSet *set);

/** 清空 HashSet **/
void HashSet_clear(HashSet *set);

插入元素

HashSet 的插入元素操作十分简单明了。只需要通过哈希函数求出元素的哈希值，并将元素存储在哈希表中即可。

int HashSet_insert(HashSet *set, const void *value) {
    if (value == NULL) return -1;

    if (set->count >= (uint32_t) (set->size * set->load_factor)) {
        // 哈希表负载因子过大，需要扩容。
        int new_size = 2 * set->size;
        HashSetType *new_map = (HashSetType *)calloc(new_size, sizeof(HashSetType));
        if (new_map == NULL) return -1;

        for (uint32_t i = 0; i < set->size; i++) {
            HashSetType *old_elem = &set->map[i];
            if (old_elem->value == NULL) continue;
            /** 计算哈希值 **/
            uint32_t idx = old_elem->hash % new_size;
            HashSetType *new_elem = &new_map[idx];

            new_elem->hash = old_elem->hash;
            new_elem->value = old_elem->value;
        }

        set->size = new_size;
        free(set->map);
        set->map = new_map;
    }

    HashSetType elem = {0};
    elem.hash = set->hash_func(value);
    elem.value = (void *)value;

    uint32_t idx = elem.hash % set->size;
    HashSetType *old_elem = &set->map[idx];
    if (old_elem->value != NULL) {
        // 如果元素已经存在，那么不再重复插入。
        if (set->keycmp_func(old_elem->value, value) == 0) return -1;
        // 如果被新元素 hash 到了原槽上，那么发生冲突或碰撞，采用线性探测法解决。
        uint32_t i = 1;
        while (1) {
            idx = (elem.hash + i) % set->size;
            old_elem = &set->map[idx];
            if (old_elem->value != NULL) {
                if (set->keycmp_func(old_elem->value, value) == 0) return -1;
            } else {
                break;
            }
            i++;
        }
    }

    *old_elem = elem;
    set->count++;
    return 0;
}

判断元素是否存在

HashSet 的元素查找操作通过哈希函数依次寻找元素所在的桶，即哈希值为 key 的元素所在的位置——桶，如果该桶是空桶，说明查找失败，则返回 FALSE。如果该桶不是空桶，则说明有哈希冲突的元素存放于该位置，此时，我们需要采用线性探测法的无序表解决来寻找被查找元素所在的位置，如果最终没有找到，说明查找失败，则返回 FALSE。

int HashSet_exists(HashSet *set, const void *value) {
    if (value == NULL) return 0;

    uint32_t hash = set->hash_func(value);
    uint32_t idx = hash % set->size;

    HashSetType *elem = &set->map[idx];
    if (elem->value == NULL) return 0;
    if (set->keycmp_func(elem->value, value) == 0) return 1;

    uint32_t i = 1;
    while (1) {
        idx = (hash + i) % set->size;
        elem = &set->map[idx];
        if (elem->value == NULL) return 0;
        if (set->keycmp_func(elem->value, value) == 0) return 1;
        i++;
    }
}

删除元素

HashSet 的元素删除操作十分简单。只需要通过哈希函数在哈希 map 中找到对应位置的元素，然后把该元素从 map 中删除即可。

int HashSet_remove(HashSet *set, const void *value) {
    if (value == NULL) return -1;

    uint32_t hash = set->hash_func(value);
    uint32_t idx = hash % set->size;

    HashSetType *elem = &set->map[idx];
    if (elem->value == NULL) return -1;
    if (set->keycmp_func(elem->value, value) == 0) {
        set->destroy_func(elem->value);
        elem->value = NULL;
        set->count--;
        return 0;
    }

    uint32_t i = 1;
    while (1) {
        idx = (hash + i) % set->size;
        elem = &set->map[idx];
        if (elem->value == NULL) return -1;
        if (set->keycmp_func(elem->value, value) == 0) {
            set->destroy_func(elem->value);
            elem->value = NULL;
            set->count--;
            return 0;
        }
        i++;
    }
    return 0;
}

示例说明

示例 1：使用 int类型实现 HashSet

假设需要声明一个 HashSet 类型的 set 变量，存储整型数据，读者可以采用如下方式进行初始化：

#include "HashSet.h"

uint32_t int_hash(const void *key) {
   return *((uint32_t *) key);
}

int int_keycmp(const void *a, const void *b) {
    return *(uint32_t *)a - *(uint32_t *)b;
}

void int_destroy(void *value) {
    free(value);
}

// 初始化 set 集合
static HashSet *set;
uint32_t hash_set_size = 3;
float hash_set_load_factor = 0.7;

int main() {
    set = HashSet_create(hash_set_size, hash_set_load_factor,
                          int_hash, int_keycmp, int_destroy);

    uint32_t *elem;
    elem = (uint32_t *)malloc(sizeof(uint32_t));
    *elem = 3;
    HashSet_insert(set, elem);

    if (HashSet_exists(set, &elem)) {
        printf("Element exists.\n");
    } else {
        printf("Element does not exist.\n");
    };
    HashSet_destroy(&set);
    return 0;

示例 2：使用 struct类型实现 HashSet

接下来我们以结构体类型为例，实现一个完整的 demo。

// 数组大小，元素数量
#define SET_SIZE    100
#define VALUE_NUM   20

typedef struct {
    int a;
    float b;
} value_t;

// Hash Function
uint32_t value_hash(const void *key) {
    int a = ((value_t *) key)->a;
    return a * a;
}

// Compare Function
int value_cmp(const void *a, const void *b) {
    value_t *data_a = (value_t *)a;
    value_t *data_b = (value_t *)b;
    return (data_a->a != data_b->a || data_a->b != data_b->b);
}

// Destroy Function
void value_freed(void *key) { free(key); }

static HashSet *set;

int main() {
    set = HashSet_create(SET_SIZE, 0.7, value_hash, value_cmp, value_freed);

    value_t *arr[VALUE_NUM];
    for (size_t i = 0; i < VALUE_NUM; i++) {
        arr[i] = (value_t *) malloc(sizeof(value_t));
        arr[i]->a = (int) rand() % 10;
        arr[i]->b = (float) rand() / RAND_MAX;
        HashSet_insert(set, arr[i]);
    }

    // 若元素存在，就删除它
    for (size_t i = 0; i < VALUE_NUM; i++) {
        if (HashSet_exists(set, arr[i])) {
            HashSet_remove(set, arr[i]);
        }
    }
    HashSet_destroy(&set);
    return 0;
}

总结

HashSet 是一个十分简单的数据结构，通过使用哈希表实现，可以非常方便地存储完整元素，不论元素的数据类型如何，都可以使用 HashSet 进行存储。本文通过一个简单的通用 HashSet，用 C 语言的方式实现了哈希表的常见操作，使读者能够大致了解 HashSet 的实现过程。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言实现通用数据结构之通用集合(HashSet) - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • vscode调用c项目后怎么引用dll?

    在VSCode中调用C语言项目，如果需要使用动态链接库（DLL）的话，一般需要进行以下步骤： 创建动态链接库 先编写动态链接库的代码并生成DLL文件。例如，编写一个示例代码，将其保存为 “hello.c”，编译并生成DLL文件 “hello.dll”。示例代码如下： #include <stdio.h> #include <stdlib.h…

    C 2023年5月23日
    00

  • 使用VScode搭建ROS开发环境的教程详解

    使用VScode搭建ROS开发环境的教程详解 为了在 VScode 中开发 ROS 项目，我们需要以下常用插件： C/C++ 扩展插件 ROS 扩展插件 ROS msg 扩展插件 下面是一个详细的步骤列表，介绍如何准备环境、配置 VScode 以及开发在 ROS 中。 环境准备 为了完成本教程，你需要：1. 一台安装有 Ubuntu 的电脑。2. 你需要在电…

    C 2023年5月23日
    00

  • C语言利用模板实现简单的栈类

    C语言利用模板实现简单的栈类 概述 本文介绍如何利用C语言中的模板来实现一个简单的栈类，使用者可以通过该类方便地进行基本的栈操作，比如入栈、出栈、查看栈顶元素等。 设计思路 栈是一种后进先出的数据结构，本文中我们采用单向链表的形式来实现栈，每个节点存储一个数据元素，同时每个节点还有个指向下一个节点的指针。栈的主要操作为入栈、出栈、查看栈顶元素，我们在代码中实…

    C 2023年5月23日
    00

  • C++实现小型图书管理系统

    C++实现小型图书管理系统攻略 1. 系统设计 图书管理系统主要包含以下功能：- 添加书籍- 删除书籍- 查询书籍信息- 修改书籍信息- 显示所有书籍 因此，我们可以设计一个Book类来表示一本书籍，其中包含以下属性：- 书名- 作者- 出版社- ISBN编号- 价格 下面是Book类的定义： class Book { public: string name…

    C 2023年5月23日
    00

  • C++中如何实现回调的方法示例

    C++中实现回调的方法有多种，下面介绍两种常见的实现方式。 方式一：函数指针 通过函数指针实现回调，需要定义一个函数指针类型，将回调函数与函数指针进行绑定，然后在合适的时机调用函数指针即可。 示例1 定义一个函数指针类型，函数原型为： typedef void (*MyCallbackFunc) (int arg1, int arg2); 其中，第一个参数表…

    C 2023年5月23日
    00

  • 浅析Android整合OKHttp与Gson实例

    一、介绍OKHttp和Gson OKHttp是一个开源的Java HTTP客户端，它与Android平台完美配合。OKHttp可以处理HTTP请求和响应的拦截以及消息中的数据转换。Gson是一个Java库，用于将Java对象转换为JSON字符串并从JSON字符串构造Java对象。 二、整合步骤 在Android项目的build.gradle文件中添加OKHt…

    C 2023年5月23日
    00

  • 分享Access数据库操作小技巧

    分享Access数据库操作小技巧 在Access数据库操作中，有一些小技巧能够提高你的效率。以下是一些常用的小技巧，这里将一一进行讲解。 使用SQL查询进行批量修改 当需要对数据库中大量的数据进行修改时，手动一个一个修改无疑是非常繁琐的。此时，我们可以使用SQL查询来进行批量修改。 比如说，我们有一个学生表格，其中有个性别字段需要修改。我们可以通过以下的SQ…

    C 2023年5月23日
    00

  • C++中的string类（C++字符串）入门完全攻略

    下面是C++中的string类（C++字符串）入门完全攻略的详细讲解： 1. 什么是string类？ string类是C++标准库提供的用于处理字符串的类，它提供了许多方便的方法来操作字符串，比如字符串的拼接、查找、替换等等，使得C++中的字符串处理变得更加轻松和高效。 2. string类的基本用法 （1）字符串的定义和初始化 在使用string类之前，可…

    C 2023年5月22日
    00
合作推广
合作推广
分享本页
返回顶部