数据结构（6）哈希表原理与实现 + Valgrind 内存调试

一、从已有数据结构的局限说起

之前学过的数据存储方式各有优缺点：

核心需求： 能否像数组一样"直接定位"，但键可以是任意类型？

哈希表就是为了解决这个问题而生的。

二、哈希表的基本思想

2.1 核心概念

记录"存储位置"与"关键字"之间的对应关系：

存储位置 = hash_function(key)
即：addr = func(key)

2.2 常见哈希函数构造方法

三、哈希冲突

3.1 什么是哈希冲突

不同的 key 值产生了同样的存储位置，即 h(key1) = h(key2)。

在哈希存储中，哈希冲突是无法避免的。 既然无法避免，就需要想办法解决。

3.2 冲突解决方法

四、链地址法的实现

4.1 数据结构设计

采用链地址法后，数组中存的不是关键字数据本身，而是链表地址，所以数组类型是指针数组：

#define SIZE 10
typedef int data_t;

typedef struct node
{
data_t data; // 数据域
struct node *next; // 指针域
} node_t;

node_t *hash_table[SIZE]; // 全局指针数组，初始全为 NULL

4.2 各操作思路总览

五、完整代码实现

5.1 插入与创建

// 单个元素插入（头插法）
int hash_insert(data_t data)
{
int addr = data % SIZE;
node_t *p_new = malloc(sizeof(node_t));
if (p_new == NULL)
return -1;
p_new->data = data;
p_new->next = NULL;

if (hash_table[addr] == NULL)
{
hash_table[addr] = p_new;
}
else
{
p_new->next = hash_table[addr];
hash_table[addr] = p_new;
}
return 0;
}

// 批量创建
int hash_create(data_t *a, int len)
{
int i = 0;
for (i = 0; i < len; ++i)
hash_insert(a[i]);
return 0;
}

5.2 遍历显示

void hash_show()
{
int i = 0;
for (i = 0; i < SIZE; ++i)
{
printf("%d[%p]->", i, hash_table[i]);
if (hash_table[i] != NULL)
{
node_t *p = hash_table[i];
while (p)
{
if (p->next != NULL)
printf("%d->", p->data);
else
printf("%d|NULL", p->data);
p = p->next;
}
}
putchar('\\n');
}
}

5.3 查找

node_t *hash_find(data_t data)
{
int addr = data % SIZE;
if (hash_table[addr] == NULL)
return NULL;

node_t *p = hash_table[addr];
while (p)
{
if (p->data == data)
return p;
p = p->next;
}
return NULL;
}

5.4 修改

node_t *hash_update(data_t old, data_t new)
{
int addr = old % SIZE;
if (hash_table[addr] == NULL)
return NULL;

node_t *p = hash_table[addr];
while (p)
{
if (p->data == old)
{
p->data = new;
return p;
}
p = p->next;
}
return NULL;
}

5.5 删除（最复杂的操作）

int hash_delete_key(data_t data)
{
int addr = data % SIZE;
if (hash_table[addr] == NULL)
return -1;

node_t *p = hash_table[addr];

// 情况1：链表只有一个节点
if (p->next == NULL)
{
if (p->data == data)
{
free(p);
hash_table[addr] = NULL;
}
}
else
{
// 情况2：删除的是头节点
if (p->data == data)
{
hash_table[addr] = p->next;
free(p);
}
else
{
// 情况3：删除中间/尾部节点，找前一个节点
while (p->next && p->next->data != data)
p = p->next;
if (p->next == NULL)
return -1;

node_t *p_temp = p->next;
p->next = p_temp->next;
free(p_temp);
}
}
return 0;
}

5.6 销毁

void hash_destroy(void)
{
int i = 0;
for (i = 0; i < SIZE; ++i)
{
if (hash_table[i] != NULL)
{
node_t *p = hash_table[i];
hash_table[i] = NULL;
while (p)
{
node_t *p_temp = p;
p = p->next;
free(p_temp);
}
}
}
}

5.7 主函数

int main(int argc, const char *argv[])
{
data_t a[] = {21, 33, 43, 45, 54, 63, 67, 82, 34, 93};
int len = sizeof(a) / sizeof(a[0]);

hash_create(a, len);
hash_show();

int key = 0;
printf("Input a num:");
scanf("%d", &key);

printf("ret = %d\\n", hash_delete_key(key));
hash_destroy(); // 程序结束前销毁，防止内存泄漏
hash_show();

return 0;
}

六、用 Valgrind 检测哈希表代码的内存问题

写完数据结构代码后，如何确认没有内存泄漏或非法访问？这里介绍 Linux 下最强大的内存调试工具 —— Valgrind。

6.1 Valgrind 简介

Valgrind 是一套动态二进制插桩工具集合，最常用的模块：

入门阶段抓住：Memcheck + 正确编译参数 + 读懂报告 + 修复。

安装：

sudo apt update
sudo apt install -y valgrind

6.2 编译要求

gcc -g -O0 -fno-omit-frame-pointer -Wall -Wextra -o app main.c

6.3 最常用命令

valgrind –leak-check=full –show-leak-kinds=all –track-origins=yes ./app

6.4 读懂报告：内存泄漏分类

Valgrind 报告中的 LEAK SUMMARY 区域：

优先修：definitely lost + indirectly lost。

6.5 对哈希表代码的检测实例

假设在 main 中不调用hash_destroy()，Valgrind 报告会显示：

==23761== still reachable: 160 bytes in 10 blocks
==23761== at 0x4C31B0F: malloc (…)
==23761== by 0x108834: hash_insert (hash.c:16)
==23761== by 0x108918: hash_create (hash.c:39)
==23761== by 0x108DE5: main (hash.c:223)

解读：

• 从 main → hash_create → hash_insert → malloc 的完整调用链清晰可见；
• 10 个分配的块在进程退出时仍然可达但未释放。

修复： 在 main 末尾调用 hash_destroy()，重新检测后 still reachable 变为 0。

6.6 另一个常见问题：未初始化读 + 泄漏

#include <stdio.h>
#include <stdlib.h>

int main()
{
int *p = malloc(sizeof(int) * 10);
printf("%d\\n", p[5]); // 未初始化读
return 0; // 没 free，泄漏
}

Valgrind 会同时报告未初始化读和内存泄漏。修复方法：

• 用 calloc 或 memset 初始化后读取；
• 退出前 free(p)。

七、总结

哈希表要点

Valgrind 要点

综合学习心得