在 C 语言中，构建哈希表（Hash Table）是一种常见的实现高效查找、插入和删除操作的方法。哈希表的核心思想是通过哈希函数将键（key）映射到一个索引，然后将值（value）存储在该索引对应的位置。
以下是构建哈希表的详细步骤和示例代码：
1. 哈希表的基本结构
哈希表通常由以下部分组成：
- 哈希函数：将键映射到索引。
- 数组：存储键值对。
- 冲突解决机制：处理哈希冲突（如链地址法或开放地址法）。
2. 哈希函数
哈希函数的设计直接影响哈希表的性能。一个好的哈希函数应该：
以下是一个简单的哈希函数示例（假设键是字符串）：
unsigned int hash(const char *key, int tableSize) {
unsigned int hashValue = 0;
while (*key) {
hashValue = (hashValue << 5) + *key++; // 使用移位和加法
}
return hashValue % tableSize; // 取模确保索引在数组范围内
}
3. 链地址法解决冲突
链地址法是一种常见的冲突解决机制。它的基本思想是将哈希表中每个索引位置存储为一个链表，所有哈希到同一索引的键值对都存储在该链表中。
数据结构定义：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100 // 哈希表大小
// 键值对结构
typedef struct Entry {
char *key;
int value;
struct Entry *next; // 指向下一个键值对
} Entry;
// 哈希表结构
typedef struct HashTable {
Entry *table[TABLE_SIZE]; // 存储链表的数组
} HashTable;
4. 哈希表操作
(1) 初始化哈希表
HashTable *createHashTable() {
HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
for (int i = 0; i < TABLE_SIZE; i++) {
ht->table[i] = NULL; // 初始化每个链表为空
}
return ht;
}
(2) 插入键值对
void insert(HashTable *ht, const char *key, int value) {
unsigned int index = hash(key, TABLE_SIZE);
// 创建新节点
Entry *newEntry = (Entry *)malloc(sizeof(Entry));
newEntry->key = strdup(key); // 复制键
newEntry->value = value;
newEntry->next = NULL;
// 插入到链表头部
if (ht->table[index] == NULL) {
ht->table[index] = newEntry;
} else {
newEntry->next = ht->table[index];
ht->table[index] = newEntry;
}
}
(3) 查找键值对
int search(HashTable *ht, const char *key) {
unsigned int index = hash(key, TABLE_SIZE);
Entry *current = ht->table[index];
// 遍历链表
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value; // 找到键，返回值
}
current = current->next;
}
return -1; // 未找到键
}
(4) 删除键值对
void delete(HashTable *ht, const char *key) {
unsigned int index = hash(key, TABLE_SIZE);
Entry *current = ht->table[index];
Entry *prev = NULL;
// 遍历链表
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
if (prev == NULL) {
ht->table[index] = current->next; // 删除链表头部
} else {
prev->next = current->next; // 删除链表中间或尾部
}
free(current->key);
free(current);
return;
}
prev = current;
current = current->next;
}
}
(5) 释放哈希表
void freeHashTable(HashTable *ht) {
for (int i = 0; i < TABLE_SIZE; i++) {
Entry *current = ht->table[i];
while (current != NULL) {
Entry *temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(ht);
}
5. 完整示例代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct Entry {
char *key;
int value;
struct Entry *next;
} Entry;
typedef struct HashTable {
Entry *table[TABLE_SIZE];
} HashTable;
// 哈希函数
unsigned int hash(const char *key, int tableSize) {
unsigned int hashValue = 0;
while (*key) {
hashValue = (hashValue << 5) + *key++;
}
return hashValue % tableSize;
}
// 创建哈希表
HashTable *createHashTable() {
HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
for (int i = 0; i < TABLE_SIZE; i++) {
ht->table[i] = NULL;
}
return ht;
}
// 插入键值对
void insert(HashTable *ht, const char *key, int value) {
unsigned int index = hash(key, TABLE_SIZE);
Entry *newEntry = (Entry *)malloc(sizeof(Entry));
newEntry->key = strdup(key);
newEntry->value = value;
newEntry->next = NULL;
if (ht->table[index] == NULL) {
ht->table[index] = newEntry;
} else {
newEntry->next = ht->table[index];
ht->table[index] = newEntry;
}
}
// 查找键值对
int search(HashTable *ht, const char *key) {
unsigned int index = hash(key, TABLE_SIZE);
Entry *current = ht->table[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return current->value;
}
current = current->next;
}
return -1;
}
// 删除键值对
void delete(HashTable *ht, const char *key) {
unsigned int index = hash(key, TABLE_SIZE);
Entry *current = ht->table[index];
Entry *prev = NULL;
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
if (prev == NULL) {
ht->table[index] = current->next;
} else {
prev->next = current->next;
}
free(current->key);
free(current);
return;
}
prev = current;
current = current->next;
}
}
// 释放哈希表
void freeHashTable(HashTable *ht) {
for (int i = 0; i < TABLE_SIZE; i++) {
Entry *current = ht->table[i];
while (current != NULL) {
Entry *temp = current;
current = current->next;
free(temp->key);
free(temp);
}
}
free(ht);
}
int main() {
HashTable *ht = createHashTable();
insert(ht, "apple", 10);
insert(ht, "banana", 20);
insert(ht, "orange", 30);
printf("apple: %d\n", search(ht, "apple")); // 输出 10
printf("banana: %d\n", search(ht, "banana")); // 输出 20
printf("grape: %d\n", search(ht, "grape")); // 输出 -1
delete(ht, "banana");
printf("banana after delete: %d\n", search(ht, "banana")); // 输出 -1
freeHashTable(ht);
return 0;
}
6. 总结
- 哈希表是一种高效的数据结构，适用于快速查找、插入和删除操作。
- 链地址法是解决哈希冲突的常见方法。
- 在实际应用中，可以根据需求调整哈希函数、哈希表大小和冲突解决机制。
通过以上代码，你可以在 C 语言中实现一个简单的哈希表，并用于解决实际问题。