C 语言实现通用数据结构之通用集合(HashSet)
什么是 HashSet
HashSet 是一种常用的数据结构，其实质就是一个无序不重复的元素集合。在 C 语言中，你可以使用 HashSet 存储任何类型的数据。
HashSet 的优点在于：
- 独立性，只关心数据的存储和操作，而不必关心数据类型；
- 方便性，对于处理过程，比起普通数组无需考虑顺序问题。
实现过程
下面是一个简化的实现步骤，通俗易懂。
基本原理
HashSet 包含以下基本操作：
- 初始化 HashSet 尺寸和加载因子。
- 插入元素。
- 判断元素是否存在。
- 删除元素。
- 清空 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技术站
微信扫一扫 
支付宝扫一扫 