C语言哈希表

ops/2024/10/18 5:42:22/

哈希表（Hash Table）是一种高效的数据结构，用于实现快速的数据查找、插入和删除操作。哈希表通过将关键字（Key）映射到表中的位置（索引），实现近似常数时间的操作效率。哈希表在许多应用中广泛使用，如数据库索引、缓存系统、编译器符号表等。本文将详细介绍如何使用C语言实现哈希表，包括基本概念、哈希函数、冲突处理方法、基本操作、示例代码及其优缺点。

哈希表的基本概念

定义

哈希表是一种通过哈希函数将关键字映射到数组索引的数据结构。每个元素（键值对）由一个键（Key）和一个值（Value）组成。理想情况下，哈希函数能将不同的键均匀地分布到哈希表的各个位置，从而实现高效的数据操作。

哈希函数

哈希函数是哈希表的核心，用于将键转换为数组索引。一个好的哈希函数应具备以下特性：

  • 确定性：相同的键每次映射的索引应相同。

  • 均匀性：键应均匀分布到哈希表的各个位置，尽量减少冲突。

  • 高效性：计算哈希值的时间复杂度应尽可能低。

常见的哈希函数包括除留余数法、乘法散列法、字符串哈希函数等。

冲突处理

由于哈希函数将有限的索引映射到可能无限的键集合，冲突是不可避免的。常见的冲突处理方法包括：

  1. 链地址法（Separate Chaining）：每个哈希表的索引对应一个链表，当多个键映射到同一索引时，将它们存储在该索引的链表中。

  2. 开放地址法（Open Addressing）：当发生冲突时，通过探测方法（如线性探测、二次探测、双重哈希等）寻找下一个可用的位置存储键值对。

本教程将采用链地址法来实现哈希表，因为其实现相对简单且适用于动态数据集。

应用场景

  1. 数据库索引：快速查找记录。

  2. 缓存系统：实现高效的缓存查找。

  3. 编译器符号表：存储变量和函数的信息。

  4. 密码学：用于数据加密和哈希验证。

  5. 字典和集合的实现。

哈希表的基本结构

在C语言中，哈希表通常由一个数组和一组链表（用于链地址法）组成。每个数组元素称为桶（Bucket），每个桶存储一个或多个键值对。

哈希表节点的结构体定义

首先，定义哈希表节点（键值对）的结构体：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义键值对的结构体
typedef struct HashNode {char* key;               // 键int value;               // 值struct HashNode* next;   // 指向下一个节点的指针（用于链地址法）
} HashNode;

哈希表的结构体定义

接下来，定义哈希表的结构体：

// 定义哈希表的结构体
typedef struct HashTable {int size;        // 哈希表的大小（桶的数量）HashNode** table; // 指向哈希表数组的指针
} HashTable;

哈希函数的实现

为了将键（字符串）映射到哈希表的索引，我们需要设计一个有效的哈希函数。以下是一个简单的哈希函数示例，采用了djbx33a算法（又称为djb2哈希函数），它对字符串具有较好的分布性：

// djb2哈希函数
unsigned int hashFunction(char* key, int size) {unsigned long hash = 5381;int c;while ((c = *key++))hash = ((hash << 5) + hash) + c; // hash * 33 + creturn hash % size;
}

哈希表的基本操作

1. 创建哈希表

创建一个指定大小的哈希表，并初始化所有桶为空：

// 创建并初始化哈希表
HashTable* createHashTable(int size) {HashTable* hashtable = (HashTable*)malloc(sizeof(HashTable));if (!hashtable) {printf("内存分配失败\n");exit(1);}hashtable->size = size;hashtable->table = (HashNode**)malloc(sizeof(HashNode*) * size);if (!hashtable->table) {printf("内存分配失败\n");exit(1);}for (int i = 0; i < size; i++)hashtable->table[i] = NULL;return hashtable;
}

2. 创建新节点

创建一个新的哈希表节点：

// 创建一个新的哈希表节点
HashNode* createHashNode(char* key, int value) {HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->key = strdup(key); // 复制键字符串newNode->value = value;newNode->next = NULL;return newNode;
}

3. 插入键值对（Insert）

将一个键值对插入到哈希表中。如果键已存在，则更新其值：

// 插入键值对到哈希表
void insert(HashTable* hashtable, char* key, int value) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];// 检查键是否已存在while (current) {if (strcmp(current->key, key) == 0) {current->value = value; // 更新值return;}current = current->next;}// 如果键不存在，则创建新节点并插入链表头部HashNode* newNode = createHashNode(key, value);newNode->next = hashtable->table[index];hashtable->table[index] = newNode;
}

4. 查找键值对（Search）

根据键查找对应的值：

// 查找键对应的值，若找到则返回值，否则返回-1
int search(HashTable* hashtable, char* key) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];while (current) {if (strcmp(current->key, key) == 0)return current->value;current = current->next;}return -1; // 表示未找到
}

5. 删除键值对（Delete）

根据键删除对应的键值对：

// 根据键删除键值对
void deleteKey(HashTable* hashtable, char* key) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];HashNode* prev = NULL;while (current) {if (strcmp(current->key, key) == 0) {if (prev)prev->next = current->next;elsehashtable->table[index] = current->next;free(current->key);free(current);return;}prev = current;current = current->next;}printf("键 '%s' 未找到，无法删除。\n", key);
}

6. 打印哈希表

遍历并打印哈希表中的所有键值对：

// 打印哈希表
void printHashTable(HashTable* hashtable) {for (int i = 0; i < hashtable->size; i++) {HashNode* current = hashtable->table[i];printf("桶 %d:", i);while (current) {printf(" -> [键: %s, 值: %d]", current->key, current->value);current = current->next;}printf("\n");}
}

7. 销毁哈希表

释放哈希表占用的内存：

// 销毁哈希表，释放内存
void destroyHashTable(HashTable* hashtable) {for (int i = 0; i < hashtable->size; i++) {HashNode* current = hashtable->table[i];while (current) {HashNode* temp = current;current = current->next;free(temp->key);free(temp);}}free(hashtable->table);free(hashtable);
}

哈希表的示例代码

以下是一个完整的哈希表实现示例程序，展示了如何插入、查找、删除和打印哈希表中的键值对：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义键值对的结构体
typedef struct HashNode {char* key;int value;struct HashNode* next;
} HashNode;// 定义哈希表的结构体
typedef struct HashTable {int size;HashNode** table;
} HashTable;// djb2哈希函数
unsigned int hashFunction(char* key, int size) {unsigned long hash = 5381;int c;while ((c = *key++))hash = ((hash << 5) + hash) + c; // hash * 33 + creturn hash % size;
}// 创建并初始化哈希表
HashTable* createHashTable(int size) {HashTable* hashtable = (HashTable*)malloc(sizeof(HashTable));if (!hashtable) {printf("内存分配失败\n");exit(1);}hashtable->size = size;hashtable->table = (HashNode**)malloc(sizeof(HashNode*) * size);if (!hashtable->table) {printf("内存分配失败\n");exit(1);}for (int i = 0; i < size; i++)hashtable->table[i] = NULL;return hashtable;
}// 创建一个新的哈希表节点
HashNode* createHashNode(char* key, int value) {HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->key = strdup(key);newNode->value = value;newNode->next = NULL;return newNode;
}// 插入键值对到哈希表
void insert(HashTable* hashtable, char* key, int value) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];// 检查键是否已存在while (current) {if (strcmp(current->key, key) == 0) {current->value = value; // 更新值return;}current = current->next;}// 如果键不存在，则创建新节点并插入链表头部HashNode* newNode = createHashNode(key, value);newNode->next = hashtable->table[index];hashtable->table[index] = newNode;
}// 查找键对应的值，若找到则返回值，否则返回-1
int search(HashTable* hashtable, char* key) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];while (current) {if (strcmp(current->key, key) == 0)return current->value;current = current->next;}return -1; // 表示未找到
}// 根据键删除键值对
void deleteKey(HashTable* hashtable, char* key) {unsigned int index = hashFunction(key, hashtable->size);HashNode* current = hashtable->table[index];HashNode* prev = NULL;while (current) {if (strcmp(current->key, key) == 0) {if (prev)prev->next = current->next;elsehashtable->table[index] = current->next;free(current->key);free(current);return;}prev = current;current = current->next;}printf("键 '%s' 未找到，无法删除。\n", key);
}// 打印哈希表
void printHashTable(HashTable* hashtable) {for (int i = 0; i < hashtable->size; i++) {HashNode* current = hashtable->table[i];printf("桶 %d:", i);while (current) {printf(" -> [键: %s, 值: %d]", current->key, current->value);current = current->next;}printf("\n");}
}// 销毁哈希表，释放内存
void destroyHashTable(HashTable* hashtable) {for (int i = 0; i < hashtable->size; i++) {HashNode* current = hashtable->table[i];while (current) {HashNode* temp = current;current = current->next;free(temp->key);free(temp);}}free(hashtable->table);free(hashtable);
}int main() {// 创建一个大小为10的哈希表HashTable* hashtable = createHashTable(10);// 插入键值对insert(hashtable, "apple", 100);insert(hashtable, "banana", 200);insert(hashtable, "orange", 300);insert(hashtable, "grape", 400);insert(hashtable, "melon", 500);// 打印哈希表printf("初始哈希表:\n");printHashTable(hashtable);// 查找键char* keyToFind = "banana";int value = search(hashtable, keyToFind);if (value != -1)printf("键 '%s' 的值是 %d\n", keyToFind, value);elseprintf("键 '%s' 未找到\n", keyToFind);// 删除键char* keyToDelete = "orange";deleteKey(hashtable, keyToDelete);printf("删除键 '%s' 后的哈希表:\n", keyToDelete);printHashTable(hashtable);// 更新键insert(hashtable, "apple", 150);printf("更新键 'apple' 后的哈希表:\n");printHashTable(hashtable);// 销毁哈希表destroyHashTable(hashtable);return 0;
}

示例输出

初始哈希表:
桶 0:
桶 1: -> [键: apple, 值: 100]
桶 2:
桶 3:
桶 4:
桶 5: -> [键: banana, 值: 200]
桶 6: -> [键: orange, 值: 300]
桶 7: -> [键: grape, 值: 400]
桶 8:
桶 9: -> [键: melon, 值: 500]键 'banana' 的值是 200
删除键 'orange' 后的哈希表:
桶 0:
桶 1: -> [键: apple, 值: 100]
桶 2:
桶 3:
桶 4:
桶 5: -> [键: banana, 值: 200]
桶 6:
桶 7: -> [键: grape, 值: 400]
桶 8:
桶 9: -> [键: melon, 值: 500]更新键 'apple' 后的哈希表:
桶 0:
桶 1: -> [键: apple, 值: 150]
桶 2:
桶 3:
桶 4:
桶 5: -> [键: banana, 值: 200]
桶 6:
桶 7: -> [键: grape, 值: 400]
桶 8:
桶 9: -> [键: melon, 值: 500]

哈希表的优缺点

优点

  1. 高效的查找、插入和删除：哈希表的平均时间复杂度为O(1)，适用于需要频繁操作的数据集。

  2. 灵活的键类型：支持多种键类型（如字符串、整数等），通过适当的哈希函数实现。

  3. 动态扩展：哈希表的大小可以根据需要动态调整，以适应不同的数据规模。

缺点

  1. 冲突处理开销：虽然大多数情况下操作效率高，但在冲突频繁的情况下，性能可能下降。

  2. 哈希函数设计：需要设计高效且均匀的哈希函数，避免冲突过多。

  3. 空间浪费：为了减少冲突，哈希表通常需要预留一定的空桶，可能导致空间浪费。

  4. 不支持有序操作：哈希表不维护键的顺序，不适合需要有序数据的场景。

哈希表的应用场景

  1. 数据库索引：用于快速定位记录。

  2. 编译器符号表：存储变量、函数等符号的信息。

  3. 缓存系统：实现快速的数据缓存，如内存缓存、网页缓存。

  4. 唯一性检测：用于检查数据集合中的重复元素。

  5. 字典和集合的实现：实现高效的键值对存储和查询。

哈希表的优化

动态扩展

随着数据量的增加，哈希表的负载因子（Load Factor，即元素数量与哈希表大小的比值）可能增大，导致冲突增加。为了保持高效性，通常需要在负载因子达到某一阈值时，扩展哈希表的大小，并重新哈希所有元素。

使用更好的哈希函数

选择适合具体键类型的哈希函数，可以显著减少冲突，提高哈希表的性能。例如，对于字符串键，可以使用更复杂的哈希函数如MurmurHash、SipHash等。

冲突处理策略的选择

根据具体应用场景，选择适合的冲突处理策略。例如，链地址法适用于动态数据集，而开放地址法在内存使用上更为紧凑。


http://www.ppmy.cn/ops/126399.html

相关文章

Oracle用户以及初学的经验

Oracle用户以及初学的经验

背景&#xff1a;目前略&#xff0c;后续补上 //创建用户 CREATE USER tpmeaccount IDENTIFIED BY 12345678; //授权权限 GRANT CONNECT, RESOURCE TO tpmeaccount;//登录&#xff0c; 以sysdba这个角色登录 &#xff0c; sys是用户名 /后面是密码 sqlplus sys/123456 as sysd…
阅读更多...
【进阶OpenCV】 （18）-- Dlib库 --人脸关键点定位

【进阶OpenCV】 （18）-- Dlib库 --人脸关键点定位

文章目录 人脸关键点定位一、作用二、原理三、代码实现1. 构造人脸检测器2. 载入模型&#xff08;加载预测器&#xff09;3. 获取关键点4. 显示图像5. 完整代码 总结 人脸关键点定位 在dlib库中&#xff0c;有shape_predictor_68_face_landmarks.dat预测器&#xff0c;这是一个…
阅读更多...
重构长方法之以方法对象取代方法

重构长方法之以方法对象取代方法

以方法对象取代方法 是重构长方法的一种技术&#xff0c;适用于那些过长、逻辑复杂且难以拆解的单一方法。此方法通过引入一个新的类&#xff0c;将原本庞杂的方法转化为一个对象方法&#xff0c;这样可以更容易将方法中的不同步骤拆解为多个私有方法&#xff0c;使代码结构清晰…
阅读更多...
python实现屏幕录制，录音录制工具

python实现屏幕录制，录音录制工具

python实现屏幕录制&#xff0c;录音录制工具 一&#xff0c;介绍 Python 实现的屏幕录制和录音录制工具是一个便捷的应用程序&#xff0c;旨在帮助用户同时捕捉计算机屏幕上的活动以及与之相关的音频输出。这个工具尤其针对教育工作者、内容创作者、技术支持人员以及任何需要…
阅读更多...
数据库的相关概念

数据库的相关概念

先看与数据库有关的几个名词&#xff1a; DB&#xff1a;database&#xff0c;数据库&#xff0c;里边保存了有组织的规范的数据。 DBMS&#xff1a;database management system &#xff0c; 数据库管理系统&#xff0c;简称数据库软件&#xff0c;数据库产品&#xff0c;数…
阅读更多...
Python操作MySQL数据库：基础教程与示例代码

Python操作MySQL数据库：基础教程与示例代码

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storm…
阅读更多...
【数据分享】全国资源和环境-环境污染治理投资（1998-2021年）

【数据分享】全国资源和环境-环境污染治理投资（1998-2021年）

数据介绍 一级标题指标名称单位指标解释资源和环境环境污染治理投资总额亿元环境污染治理投资指在污染源治理和城市环境基础设施建设的资金投入中&#xff0c;用于形成固定资产的资金&#xff0c;其中污染源治理投资包括工业污染源治理投资和“三同时”项目环保投资两部分。环…
阅读更多...
解决高版本使用Gson报错Caused by: java.lang.NoClassDefFoundError: java/sql/Time

解决高版本使用Gson报错Caused by: java.lang.NoClassDefFoundError: java/sql/Time

开发项目使用jdk21&#xff0c;版本较高&#xff0c;需要用模块化引入。在使用gson转换json数据时&#xff0c;报错 Caused by: java.lang.NoClassDefFoundError: java/sql/Time at gson2.8.5/com.google.gson.Gson.<init>(Gson.java:265) at gson2.8.5/com.google.gson…
阅读更多...
最新文章

Copyright @ 2022~2023