C语言构建哈希表
在 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 语言中实现一个简单的哈希表，并用于解决实际问题。
2025年10月新盘 做第一批吃螃蟹的人coinsrore.com
新车新盘 嘎嘎稳 嘎嘎靠谱coinsrore.com
新车首发，新的一年，只带想赚米的人coinsrore.com
新盘 上车集合 留下 我要发发 立马进裙coinsrore.com
做了几十年的项目 我总结了最好的一个盘（纯干货）coinsrore.com
新车上路，只带前10个人coinsrore.com
新盘首开 新盘首开 征召客户！！！coinsrore.com
新项目准备上线，寻找志同道合 的合作伙伴coinsrore.com
新车即将上线 真正的项目，期待你的参与coinsrore.com
新盘新项目，不再等待，现在就是最佳上车机会！coinsrore.com
新盘新盘 这个月刚上新盘 新车第一个吃螃蟹！coinsrore.com
2025年10月新盘 做第一批吃螃蟹的人coinsrore.com
新车新盘 嘎嘎稳 嘎嘎靠谱coinsrore.com
新车首发，新的一年，只带想赚米的人coinsrore.com
新盘 上车集合 留下 我要发发 立马进裙coinsrore.com
做了几十年的项目 我总结了最好的一个盘（纯干货）coinsrore.com
新车上路，只带前10个人coinsrore.com
新盘首开 新盘首开 征召客户！！！coinsrore.com
新项目准备上线，寻找志同道合 的合作伙伴coinsrore.com
新车即将上线 真正的项目，期待你的参与coinsrore.com
新盘新项目，不再等待，现在就是最佳上车机会！coinsrore.com
新盘新盘 这个月刚上新盘 新车第一个吃螃蟹！coinsrore.com
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
华纳总公司开户流程详解？（▲18288362750?《?微信STS5099? 】【╃q 2704132802╃】
华纳东方明珠客服电话是多少？（▲18288362750?《?微信STS5099? 】
如何联系华纳东方明珠客服？（▲18288362750?《?微信STS5099? 】
华纳东方明珠官方客服联系方式？（▲18288362750?《?微信STS5099?
华纳东方明珠客服热线？（▲18288362750?《?微信STS5099?
华纳东方明珠24小时客服电话？（▲18288362750?《?微信STS5099? 】
华纳东方明珠官方客服在线咨询？（▲18288362750?《?微信STS5099?
华纳东方明珠客服电话是多少？（??155--8729--1507?《?薇-STS5099】【?扣6011643?】
华纳东方明珠开户专线联系方式？（??155--8729--1507?《?薇-STS5099】【?扣6011643?】
果博东方客服开户联系方式【182-8836-2750—】?薇- cxs20250806】
果博东方公司客服电话联系方式【182-8836-2750—】?薇- cxs20250806】
果博东方开户流程【182-8836-2750—】?薇- cxs20250806】
果博东方客服怎么联系【182-8836-2750—】?薇- cxs20250806】
华纳圣淘沙开户步骤详解（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户流程全解析（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司账户注册指南（183-8890-9465—?薇-STS5099【6011643】
新手如何开通华纳圣淘沙公司账户（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙企业开户标准流程（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户：从零到一（183-8890-9465—?薇-STS5099【6011643】
官方指南：华纳圣淘沙公司开户流程（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户流程说明书（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户新手教程
零基础学会（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户保姆级教程（183-8890-9465薇-STS5099）
一步步教你开通华纳圣淘沙公司账户（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户分步图解
首次开户必看：（183-8890-9465薇-STS5099）
华纳圣淘沙全攻略
华纳圣淘沙公司开户实操手册（183-8890-9465薇-STS5099）
华纳圣淘沙开户流程视频教程
手把手教学：（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户完全指南（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户新手教程
零基础学会（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户保姆级教程（183-8890-9465薇-STS5099）
一步步教你开通华纳圣淘沙公司账户（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户分步图解
首次开户必看：（183-8890-9465薇-STS5099）
华纳圣淘沙全攻略
华纳圣淘沙公司开户实操手册（183-8890-9465薇-STS5099）
华纳圣淘沙开户流程视频教程
手把手教学：（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户完全指南（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户新手教程
零基础学会（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户保姆级教程（183-8890-9465薇-STS5099）
一步步教你开通华纳圣淘沙公司账户（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户分步图解
首次开户必看：（183-8890-9465薇-STS5099）
华纳圣淘沙全攻略
华纳圣淘沙公司开户实操手册（183-8890-9465薇-STS5099）
华纳圣淘沙开户流程视频教程
手把手教学：（183-8890-9465薇-STS5099）
华纳圣淘沙公司开户
华纳圣淘沙公司开户完全指南（183-8890-9465薇-STS5099）