哈希表概述
哈希表，也被称为散列表，是一种基于哈希函数组织数据，以支持快速插入和搜索的数据结构。它通过计算键值（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; |
|
} |
注意事项
- 哈希函数的选择：上述示例中的哈希函数相对简单，可能不适用于所有场景。在实际应用中，你可能需要选择或设计更合适的哈希函数，以减少冲突并提高性能。
- 动态调整哈希表大小：当哈希表中的元素数量过多，导致冲突频繁时，你可能需要动态调整哈希表的大小，并重新哈希所有元素。这通常涉及创建一个新的哈希表，并将旧表中的元素迁移到新表中。
- 线程安全：上述示例中的哈希表实现不是线程安全的。如果你需要在多线程环境中使用哈希表，你需要添加适当的锁机制来确保线程安全。