目录
前言：为什么要“造轮子”？
第一回合：通用链表 (Generic Linked List)
1. 设计思路：void* 的艺术
2. 核心代码实现
3. 优雅性点评
第二回合：哈希表 (Hash Table)
1. 架构选择：拉链法 vs 开放寻址法
2. 哈希函数：DJB2 算法
3. 核心代码挑战：动态扩容
4. 优雅性点评
总结：C 语言的哲学
摘要： 在高级语言满天飞的今天，为什么我们还要用 C 语言“造轮子”？因为只有亲自管理过每一字节的内存，亲自处理过每一次指针的跳转，你才算真正理解了计算机。本文将带你通过一场“造轮子大赛”，从零实现通用的链表与高效的哈希表，挑战代码设计的优雅极限。
前言：为什么要“造轮子”？
在软件工程中，我们常说“不要重复造轮子”。但在学习阶段，造轮子是掌握技术的唯一捷径。
C 语言没有 C++ STL 的便利，没有 Java 的垃圾回收，也没有 Python 的丰富库。在这里，你就是上帝，掌管着内存的生杀大权。
今天的挑战目标很明确：
通用性：不能只能存 int，要能存万物。
鲁棒性：内存管理必须无懈可击，杜绝泄漏。
优雅性：API 设计要简洁、直观，隐藏底层复杂度。
第一回合：通用链表 (Generic Linked List)
初学者的链表往往是 struct Node { int data; node* next; }。但在工业级代码（如 Linux 内核或 Redis）中，链表绝不会这么写。我们要实现一个支持任意数据类型的链表。
1. 设计思路：void* 的艺术
为了存储任意类型，我们使用 void* 指针。为了让链表更优雅，我们采用**不透明指针（Opaque Pointer）**的设计模式，将结构体的具体定义隐藏在 .c 文件中，头文件只暴露句柄。
2. 核心代码实现
头文件 (list.h):
#ifndef LIST_H
#define LIST_H
#include <stddef.h>
#include <stdbool.h>
// 不透明类型，用户不知道具体结构，只能持有指针
typedef struct List List;
// 构造与析构
List* list_create();
void list_destroy(List* list);
// 核心操作
void list_push_back(List* list, void* value);
void* list_pop_front(List* list);
size_t list_size(List* list);
// 遍历宏（C语言的魔法）
#define LIST_FOREACH(item, list) \\
for (void* item = list_first(list); item != NULL; item = list_next(list))
#endif
实现文件 (list.c) 的关键片段:
typedef struct Node {
void* value;
struct Node* next;
} Node;
struct List {
Node* head;
Node* tail;
size_t size;
};
void list_push_back(List* list, void* value) {
Node* node = malloc(sizeof(Node));
if (!node) return; // 生产环境必须处理 OOM
node->value = value;
node->next = NULL;
if (list->tail) {
list->tail->next = node;
} else {
list->head = node;
}
list->tail = node;
list->size++;
}
3. 优雅性点评
-
封装性：用户无法直接访问 list->head，必须通过 API 操作，保证了数据安全。
-
多态性：可以存储 int*、char* 甚至是 struct User*。
-
思考题：如果销毁链表，里面的 value 谁来释放？（答案：通常需要传入一个 free_func 回调函数，这才是成熟的设计）。
第二回合：哈希表 (Hash Table)
如果说链表是热身，哈希表就是真正的挑战。我们需要解决两个核心问题：哈希函数的设计与哈希冲突的解决。
1. 架构选择：拉链法 vs 开放寻址法
-
拉链法 (Chaining)：桶里存链表。优点是实现简单，缺点是缓存不友好（指针乱跳）。
-
开放寻址法 (Open Addressing)：冲突了就往后找。优点是内存连续，缓存友好。
为了挑战“高性能”与“底层优雅”，我们这次选择开放寻址法（线性探测）。
2. 哈希函数：DJB2 算法
我们需要一个分布均匀且计算够快的哈希算法。DJB2 是经典的字符串哈希算法：
unsigned long hash_djb2(unsigned char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
3. 核心代码挑战：动态扩容
最难的部分在于，当哈希表太满（负载因子 > 0.75）时，必须扩容，否则查找性能会退化为 O(n)。
typedef struct Entry {
char* key;
void* value;
bool occupied; // 标记该槽位是否被占用
bool deleted; // 标记是否被逻辑删除（墓碑机制）
} Entry;
typedef struct HashMap {
Entry* entries;
size_t capacity;
size_t count;
} HashMap;
// 扩容逻辑
static void map_resize(HashMap* map) {
size_t old_cap = map->capacity;
Entry* old_entries = map->entries;
// 容量翻倍
map->capacity *= 2;
map->entries = calloc(map->capacity, sizeof(Entry));
map->count = 0; // 重新计数
// 重新哈希 (Rehash) 所有旧数据
for (size_t i = 0; i < old_cap; i++) {
if (old_entries[i].occupied && !old_entries[i].deleted) {
map_put(map, old_entries[i].key, old_entries[i].value);
}
}
free(old_entries);
}
4. 优雅性点评
-
墓碑机制：在开放寻址法中，删除元素不能直接置空，否则会截断后续冲突元素的查找路径。我们需要一个 deleted 标记，这就是底层设计的细节之美。
-
自动扩容：用户只管 put，内部自动处理内存增长，这是优秀库应有的修养。
总结：C 语言的哲学
通过这两轮“造轮子”，我们学到了什么？
信任与责任：C 语言信任程序员，给予了无限的自由，但也要求我们对每一块 malloc 负责到底。
抽象的代价：为了通用性（void*），我们牺牲了一点点类型安全（需要强制转换）。这是底层设计中常见的权衡（Trade-off）。
极简主义：最优雅的代码往往不是炫技，而是用最简单的结构解决最复杂的问题。
挑战赛作业：
上面的代码还有优化空间。例如，哈希表如何支持非字符串的 Key？链表如何实现 O(1) 的反向遍历？
拿起你的 IDE（或者 Vim），开始你的“造轮子”之旅吧。Talk is cheap, show me the code.
如果你喜欢这种硬核的底层代码解析，欢迎在评论区留下你的 GitHub 仓库链接，让我们看看谁的轮子造得最圆！
