什么是哈希表？如何在C语言中实现一个哈希表？
哈希表概述
哈希表，也被称为散列表，是一种基于哈希函数组织数据，以支持快速插入和搜索的数据结构。它通过计算键值（Key）的哈希值，来确定数据在表中的存储位置，从而实现高效的数据访问。哈希表的核心优势在于其平均情况下的时间复杂度为O(1)，这使得它在处理大数据集时具有出色的性能。
哈希表的基本构成
- 哈希函数：用于将键值转换为哈希值，该值通常用作数组中的索引。
- 哈希表（数组）：用于存储键值对。
- 解决冲突的方法：由于哈希函数可能产生相同的哈希值（即冲突），因此需要采用相应策略来处理，如链地址法（拉链法）或开放地址法。
在C语言中实现哈希表
以下是一个简单的哈希表实现示例，采用链地址法来处理冲突：
c复制代码
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
// 定义哈希表项 | |
typedef struct HashNode {
| |
char* key; | |
int value; | |
struct HashNode* next; | |
} HashNode; | |
// 定义哈希表 | |
typedef struct HashTable {
| |
HashNode** table; | |
int size; | |
} HashTable; | |
// 简单的哈希函数，用于生成哈希值 | |
unsigned int hash(char* str, int size) {
| |
unsigned int hash = 0; | |
while (*str) {
| |
hash = (hash << 5) + *str++; | |
} | |
return hash % size; | |
} | |
// 创建哈希表 | |
HashTable* createTable(int size) {
| |
HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable)); | |
hashTable->size = size; | |
hashTable->table = (HashNode**)calloc(size, sizeof(HashNode*)); | |
return hashTable; | |
} | |
// 插入键值对到哈希表中 | |
void insert(HashTable* hashTable, char* key, int value) {
| |
unsigned int index = hash(key, hashTable->size); | |
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode)); | |
newNode->key = strdup(key); | |
newNode->value = value; | |
newNode->next = hashTable->table[index]; | |
hashTable->table[index] = newNode; | |
} | |
// 搜索哈希表中的键 | |
int search(HashTable* hashTable, char* key) {
| |
unsigned int index = hash(key, hashTable->size); | |
HashNode* currentNode = hashTable->table[index]; | |
while (currentNode) {
| |
if (strcmp(currentNode->key, key) == 0) {
| |
return currentNode->value; | |
} | |
currentNode = currentNode->next; | |
} | |
return -1; // 未找到键时返回-1 | |
} | |
// 释放哈希表占用的内存 | |
void freeTable(HashTable* hashTable) {
| |
for (int i = 0; i < hashTable->size; i++) {
| |
HashNode* currentNode = hashTable->table[i]; | |
while (currentNode) {
| |
HashNode* temp = currentNode; | |
currentNode = currentNode->next; | |
free(temp->key); | |
free(temp); | |
} | |
} | |
free(hashTable->table); | |
free(hashTable); | |
} | |
// 主函数示例 | |
int main() {
| |
HashTable* hashTable = createTable(10); | |
insert(hashTable, "apple", 5); | |
insert(hashTable, "banana", 3); | |
insert(hashTable, "orange", 7); | |
printf("apple的值: %d\n", search(hashTable, "apple")); | |
printf("banana的值: %d\n", search(hashTable, "banana")); | |
printf("grape的值: %d\n", search(hashTable, "grape")); // 未找到键时输出-1 | |
freeTable(hashTable); | |
return 0; | |
} |
注意事项
- 哈希函数的选择：上述示例中的哈希函数相对简单，可能不适用于所有场景。在实际应用中，你可能需要选择或设计更合适的哈希函数，以减少冲突并提高性能。
- 动态调整哈希表大小：当哈希表中的元素数量过多，导致冲突频繁时，你可能需要动态调整哈希表的大小，并重新哈希所有元素。这通常涉及创建一个新的哈希表，并将旧表中的元素迁移到新表中。
- 线程安全：上述示例中的哈希表实现不是线程安全的。如果你需要在多线程环境中使用哈希表，你需要添加适当的锁机制来确保线程安全。