（C语言）Map数组的实现（数据结构）（链表）（指针）

源代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 键值对节点
typedef struct Node {char* key;int value;struct Node* next;
} Node;// Map结构
typedef struct {Node* buckets[100];  // 固定大小的哈希桶（简化版）int size;            // 元素数量
} Map;// 简单哈希函数（字符串转索引）
int hash(const char* key) {int hash = 0;while (*key) {hash += (*key++);}return hash % 100;  // 对应buckets大小
}// 初始化Map
void initMap(Map* map) {memset(map->buckets, 0, sizeof(map->buckets));map->size = 0;
}// 插入或更新键值对
void put(Map* map, const char* key, int value) {if (!key) return;int index = hash(key);Node* curr = map->buckets[index];// 查找是否已存在键while (curr) {if (strcmp(curr->key, key) == 0) {curr->value = value;  // 更新值return;}curr = curr->next;}// 不存在则创建新节点（头插法）Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) return;newNode->key = strdup(key);if (!newNode->key) {free(newNode);return;}newNode->value = value;newNode->next = map->buckets[index];map->buckets[index] = newNode;map->size++;
}// 根据键获取值
int get(Map* map, const char* key, int* result) {if (!key || !result) return 0;int index = hash(key);Node* curr = map->buckets[index];while (curr) {if (strcmp(curr->key, key) == 0) {*result = curr->value;return 1;  // 找到}curr = curr->next;}return 0;  // 未找到
}// 删除键值对
int removeKey(Map* map, const char* key) {if (!key) return 0;int index = hash(key);Node* curr = map->buckets[index];Node* prev = NULL;while (curr) {if (strcmp(curr->key, key) == 0) {if (prev) {prev->next = curr->next;} else {map->buckets[index] = curr->next;}free(curr->key);free(curr);map->size--;return 1;}prev = curr;curr = curr->next;}return 0;
}// 获取元素数量
int size(Map* map) {return map->size;
}// 清空Map
void clear(Map* map) {for (int i = 0; i < 100; i++) {Node* curr = map->buckets[i];while (curr) {Node* next = curr->next;free(curr->key);free(curr);curr = next;}map->buckets[i] = NULL;}map->size = 0;
}// 测试函数
int main() {Map map;initMap(&map);// 插入数据put(&map, "apple", 10);put(&map, "banana", 5);put(&map, "orange", 8);// 获取数据int val;if (get(&map, "banana", &val)) {printf("banana: %d\n", val);  // 输出：banana: 5}// 更新数据put(&map, "banana", 15);get(&map, "banana", &val);printf("updated banana: %d\n", val);  // 输出：updated banana: 15// 删除数据removeKey(&map, "orange");printf("size after remove: %d\n", size(&map));  // 输出：size after remove: 2// 清空Mapclear(&map);printf("final size: %d\n", size(&map));  // 输出：final size: 0return 0;
}

代码详解： 

这个代码实现了一个简单的 哈希表（Hash Map） 数据结构，用于存储键值对（key-value pairs）。下面将详细解释代码的每一部分及其功能：

---

1. 数据结构设计

节点结构 Node

typedef struct Node {char* key;          // 字符串键int value;          // 整数值struct Node* next;  // 指向下一个节点的指针（处理哈希冲突）
} Node;

• 作用：存储键值对的基本单元

• 关键点：

  • key 使用 strdup 动态分配内存存储字符串

  • next 指针用于解决哈希冲突（链地址法）

哈希表结构 Map

typedef struct {Node* buckets[100];  // 哈希桶数组（固定大小100）int size;            // 当前存储的元素数量
} Map;

• 作用：管理整个哈希表

• 关键点：

  • buckets 是长度为 100 的指针数组，每个桶对应一个链表

  • size 记录当前存储的键值对数量

---

2. 核心功能实现

哈希函数 hash()

int hash(const char* key) {int hash = 0;while (*key) {hash += (*key++);  // 简单累加ASCII值}return hash % 100;     // 映射到0-99的桶索引
}

• 作用：将任意字符串键映射到固定范围的索引

• 特点：

  • 简单但容易产生冲突（如 "ab" 和 "ba" 哈希值相同）

  • 使用取模运算确保结果在桶数组范围内

初始化函数 initMap()

void initMap(Map* map) {memset(map->buckets, 0, sizeof(map->buckets));map->size = 0;
}

• 作用：初始化哈希表状态

• 关键操作：

  • 将所有桶指针设为 NULL

  • 元素计数器 size 归零

插入/更新函数 put()

void put(Map* map, const char* key, int value) {// 1. 计算哈希索引int index = hash(key);// 2. 检查键是否已存在（更新值）Node* curr = map->buckets[index];while (curr) {if (strcmp(curr->key, key) == 0) {curr->value = value;return;}curr = curr->next;}// 3. 创建新节点（头插法）Node* newNode = malloc(sizeof(Node));newNode->key = strdup(key);  // 复制键字符串newNode->value = value;newNode->next = map->buckets[index];map->buckets[index] = newNode;map->size++;
}

• 特点：

  • 键存在时更新值

  • 键不存在时使用头插法添加新节点

  • 使用 strdup 深拷贝键字符串

查找函数 get()

int get(Map* map, const char* key, int* result) {int index = hash(key);Node* curr = map->buckets[index];while (curr) {if (strcmp(curr->key, key) == 0) {*result = curr->value;  // 通过指针返回结果return 1;  // 成功找到}curr = curr->next;}return 0;  // 未找到
}

• 特点：

  • 返回查找状态（1成功/0失败）

  • 通过指针参数 result 返回查找到的值

删除函数 removeKey()

int removeKey(Map* map, const char* key) {int index = hash(key);Node* curr = map->buckets[index];Node* prev = NULL;while (curr) {if (strcmp(curr->key, key) == 0) {// 从链表中删除节点if (prev) prev->next = curr->next;else map->buckets[index] = curr->next;// 释放内存free(curr->key);free(curr);map->size--;return 1;  // 删除成功}prev = curr;curr = curr->next;}return 0;  // 键不存在
}

• 关键操作：

  • 处理链表中间/头部节点的删除

  • 释放键字符串和节点本身的内存

辅助函数

int size(Map* map) { return map->size; }  // 返回元素数量void clear(Map* map) {                   // 清空整个哈希表for (int i = 0; i < 100; i++) {Node* curr = map->buckets[i];while (curr) {Node* next = curr->next;free(curr->key);free(curr);curr = next;}map->buckets[i] = NULL;}map->size = 0;
}

---

3. 测试逻辑（main函数）

int main() {Map map;initMap(&map);  // 初始化// 插入测试put(&map, "apple", 10);put(&map, "banana", 5);put(&map, "orange", 8);// 查找测试int val;get(&map, "banana", &val);  // 输出: banana: 5// 更新测试put(&map, "banana", 15);    // 更新值get(&map, "banana", &val);  // 输出: updated banana: 15// 删除测试removeKey(&map, "orange");printf("size after remove: %d\n", size(&map));  // 输出: 2// 清空测试clear(&map);printf("final size: %d\n", size(&map));  // 输出: 0return 0;
}

---

4. 代码功能总结

1. 核心数据结构：

   • 实现了一个基于链地址法的哈希表

   • 支持字符串键（key）和整数值（value）的存储

2. 支持操作：

   • put(): 插入/更新键值对

   • get(): 查找键对应的值

   • removeKey(): 删除指定键

   • size(): 获取元素数量

   • clear(): 清空整个哈希表

3. 冲突解决：

   • 使用链表解决哈希冲突（链地址法）

   • 每个桶是一个链表头节点

4. 内存管理：

   • 动态分配节点内存

   • 使用 strdup 复制键字符串

   • 删除/清空时释放所有内存

---

5. 局限性及改进建议

1. 固定桶大小：

   • 桶数组固定为100，可能导致冲突率高

   • 改进：实现动态扩容（如负载因子>0.75时扩容）

2. 简单哈希函数：

   • 当前哈希函数易产生冲突

   • 改进：使用更复杂的哈希算法（如djb2）

3. 键类型限制：

   • 仅支持字符串键

   • 改进：使用泛型支持多种键类型

4. 线程安全：

   • 非线程安全

   • 改进：添加互斥锁实现线程安全

5. 错误处理：

   • 未处理内存分配失败情况

   • 改进：添加NULL指针检查

---

6. 实际应用场景

1. 配置存储：存储程序配置参数（键值对）

2. 缓存系统：实现简单的内存缓存

3. 词频统计：统计文本中单词出现次数

4. 符号表：编译器中的变量管理

5. 路由表：网络设备中的IP路由查找

注：该代码是本人自己所写，可能不够好，不够简便，欢迎大家指出我的不足之处。如果遇见看不懂的地方，可以在评论区打出来，进行讨论，或者联系我。上述内容全是我自己理解的，如果你有别的想法，或者认为我的理解不对，欢迎指出！！！如果可以，可以点一个免费的赞支持一下吗？谢谢各位彦祖亦菲！！！！！