21、哈希表的调试与测试：单元测试框架、边界条件测试、性能基准测试、内存泄漏检测

写哈希表代码，最怕什么？

不是写不出来，而是写出来之后，一跑就崩，一测就挂。我见过太多人，哈希表逻辑看着没问题，结果插入几个元素就段错误，或者内存泄漏到服务器撑不住。说白了，哈希表这种数据结构，调试和测试比实现本身更考验功底。

今天我就把压箱底的测试方法论拿出来，从单元测试到内存泄漏检测，一条龙讲清楚。

21.1 单元测试框架：给哈希表上保险

我个人习惯，写任何数据结构之前，先把测试框架搭好。C语言里没有官方的单元测试库，但我们可以自己写一个轻量级的。

// mini_test.h
#ifndef MINI_TEST_H
#define MINI_TEST_H

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

static int test_passed = 0;
static int test_failed = 0;

#define ASSERT_EQ(actual, expected, msg) \
    do { \
        if ((actual) != (expected)) { \
            fprintf(stderr, "[FAIL] %s:%d - %s (expected=%ld, actual=%ld)\n", \
                    __FILE__, __LINE__, msg, (long)(expected), (long)(actual)); \
            test_failed++; \
        } else { \
            test_passed++; \
        } \
    } while(0)

#define ASSERT_NE(actual, unexpected, msg) \
    do { \
        if ((actual) == (unexpected)) { \
            fprintf(stderr, "[FAIL] %s:%d - %s (unexpected=%ld)\n", \
                    __FILE__, __LINE__, msg, (long)(unexpected)); \
            test_failed++; \
        } else { \
            test_passed++; \
        } \
    } while(0)

#define TEST_REPORT() \
    printf("\n=== Test Report ===\n"); \
    printf("Passed: %d, Failed: %d\n", test_passed, test_failed); \
    printf("===================\n")

#endif

这个框架虽然简陋，但够用。我在项目中用过更复杂的CUnit，但说实话，对于哈希表这种基础结构，轻量级框架反而更灵活。

21.2 边界条件测试：魔鬼藏在细节里

哈希表的边界条件，我踩过的坑比写过的代码还多。你想想看，空表、满表、只有一个元素、键冲突……每个场景都可能翻车。

必须覆盖的边界条件清单：

• 空表操作：查找、删除、遍历空哈希表
• 单元素表：插入一个元素后查找、删除
• 满表（负载因子=1）：插入到不能再插入
• 键冲突：多个键映射到同一个桶
• 重复键：插入已存在的键（覆盖还是拒绝？）
• 删除不存在的键：返回什么？
• 大规模插入后删除：内存碎片问题

我曾经在一个嵌入式项目中，哈希表在删除最后一个元素后，头指针没置NULL，导致后续查找直接访问野指针。嗯，那次排查了整整一个下午。

// 边界条件测试示例
void test_boundary_conditions() {
    HashTable* ht = ht_create(4);  // 小容量，方便测试
    
    // 1. 空表查找
    ASSERT_EQ(ht_lookup(ht, "key1"), NULL, "查找空表应返回NULL");
    
    // 2. 插入一个元素
    ht_insert(ht, "key1", "value1");
    ASSERT_NE(ht_lookup(ht, "key1"), NULL, "插入后应能找到");
    
    // 3. 删除唯一元素
    ht_delete(ht, "key1");
    ASSERT_EQ(ht_lookup(ht, "key1"), NULL, "删除后应找不到");
    
    // 4. 再次删除已删除的键
    int ret = ht_delete(ht, "key1");
    ASSERT_EQ(ret, -1, "删除不存在的键应返回-1");
    
    // 5. 插入到满表
    ht_insert(ht, "a", "1");
    ht_insert(ht, "b", "2");
    ht_insert(ht, "c", "3");
    ht_insert(ht, "d", "4");
    int result = ht_insert(ht, "e", "5");
    ASSERT_EQ(result, -1, "满表插入应失败");
    
    ht_destroy(ht);
}

21.3 性能基准测试：别让哈希表成为瓶颈

哈希表写好了，能跑，但快不快？我见过一个哈希表，插入100万个元素花了30秒——后来发现是扩容策略有问题，每次扩容只增加一个桶。

性能基准测试要关注三个指标：

指标	说明	正常范围
插入吞吐量	每秒能插入多少元素	百万级/秒（视数据大小）
查找延迟	单次查找平均耗时	< 1微秒
扩容开销	触发扩容时的卡顿时间	< 10毫秒

// 性能基准测试框架
#include <time.h>

double benchmark_insert(int count) {
    HashTable* ht = ht_create(1024);
    clock_t start = clock();
    
    for (int i = 0; i < count; i++) {
        char key[32];
        snprintf(key, sizeof(key), "key_%d", i);
        ht_insert(ht, key, "value");
    }
    
    clock_t end = clock();
    double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
    printf("插入 %d 个元素: %.3f 秒 (%.0f 个/秒)\n", 
           count, elapsed, count / elapsed);
    
    ht_destroy(ht);
    return elapsed;
}

void run_benchmarks() {
    printf("=== 性能基准测试 ===\n");
    benchmark_insert(10000);
    benchmark_insert(100000);
    benchmark_insert(1000000);
}

21.4 内存泄漏检测：看不见的杀手

哈希表涉及大量动态内存分配——节点、桶数组、键值对拷贝。稍有不慎，内存泄漏就找上门了。我当年有个项目，哈希表每插入一次就泄漏几个字节，跑了三天服务器内存爆了。

检测方法有三种：

1. Valgrind：Linux下最常用的工具，直接跑 valgrind --leak-check=full ./your_program
2. AddressSanitizer：编译时加 -fsanitize=address，运行时自动检测
3. 手动计数：在代码里维护分配/释放计数器

我个人推荐第三种作为日常调试手段，因为Valgrind跑起来太慢了，大项目等不起。

// 手动内存泄漏检测
static int alloc_count = 0;
static int free_count = 0;

void* debug_malloc(size_t size) {
    alloc_count++;
    return malloc(size);
}

void debug_free(void* ptr) {
    if (ptr) {
        free_count++;
        free(ptr);
    }
}

void check_memory_leak() {
    if (alloc_count != free_count) {
        fprintf(stderr, "[LEAK] 分配 %d 次，释放 %d 次，泄漏 %d 次\n",
                alloc_count, free_count, alloc_count - free_count);
    } else {
        printf("[OK] 无内存泄漏 (分配/释放: %d)\n", alloc_count);
    }
}

21.5 知识体系总览

下面这张图，把哈希表调试与测试的四个维度串起来了。你可以把它当作检查清单，每次写完哈希表，对着这张图跑一遍，基本就稳了。

这四个维度，缺一不可。单元测试保证功能正确，边界条件测试堵住极端情况，性能测试确保效率，内存泄漏检测守住资源底线。我每次发布哈希表代码前，都会把这四步走一遍，少一步都不放心。