C语言实现开放寻址哈希表冲突计数与搜索时间计算方法

现有代码核心问题 #

当前代码仅实现基础增删查改逻辑，缺失实验要求的核心能力，同时存在开放寻址法的逻辑缺陷：

• 线性探测、二次探测逻辑写死，无法快速切换对比
• 无插入、搜索过程的冲突次数统计能力
• 无操作耗时计算能力，无法做性能指标采集
• 删除逻辑直接将槽位置NULL，会打断探测链导致搜索漏元素，开放寻址法需要墓碑标记处理删除场景

第一步：基础结构改造 #

1. 常量与结构体补充 #

新增槽位状态、探测模式枚举，给哈希表结构加统计字段，替换原有的空槽判断逻辑：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h> // 用于高精度计时

#define LEN 20
// 槽位状态标记
#define EMPTY 0     // 空槽
#define VALID 1     // 存有效数据
#define TOMBSTONE 2 // 删除留下的墓碑标记
// 探测模式枚举
#define LINEAR_PROBE 0    // 线性探测
#define QUADRATIC_PROBE 1 // 二次探测

typedef struct inform {
    char* key, * name;
} INFO;

typedef struct hash_table {
    int count, size;
    INFO** array;
    int* slot_status;      // 存储每个槽位的状态
    int probe_mode;        // 当前使用的探测模式
    // 单次操作统计
    int op_collision;      // 单次插入/搜索的冲突次数
    double op_time;        // 单次操作耗时，单位毫秒
    // 全局累计统计
    long total_insert_collision;
    long total_search_collision;
    int insert_op_cnt;
    int search_op_cnt;
}HTAB;

2. 基础函数适配修改 #

初始化、释放、状态判断函数同步适配新增字段：

INFO* New_Item(char* key, char* name)
{
    INFO* result = (INFO*)malloc(sizeof(INFO));
    result->key = key;
    result->name = name;
    return result;
}

void free_item(INFO* item)
{
    if (item != NULL) free(item);
}

HTAB* NewHTAB(int size, int probe_mode)
{
    HTAB* result = (HTAB*)malloc(sizeof(HTAB));
    result->count = 0;
    result->size = size;
    result->probe_mode = probe_mode;
    result->array = (INFO**)malloc(sizeof(INFO*) * size);
    result->slot_status = (int*)malloc(sizeof(int) * size);
    memset(result->array, NULL, sizeof(INFO*) * size);
    memset(result->slot_status, EMPTY, sizeof(int) * size);
    // 统计字段初始化
    result->op_collision = 0;
    result->op_time = 0;
    result->total_insert_collision = 0;
    result->total_search_collision = 0;
    result->insert_op_cnt = 0;
    result->search_op_cnt = 0;
    return result;
}

void free_hash_table(HTAB* table)
{
    if (table != NULL) {
        for (int i = 0; i < table->size; i++) {
            if (table->slot_status[i] == VALID) free_item(table->array[i]);
        }
        free(table->array);
        free(table->slot_status);
        free(table);
    }
}

int ht_hasItem(HTAB* table, int idx)
{
    return table->slot_status[idx] == VALID;
}

int ht_IsFull(HTAB* table)
{
    return table->count == table->size;
}

int Hash_Code(int key, int size)
{
    return key % size;
}

3. 统一探测逻辑封装 #

把探测逻辑抽成独立函数，同时支持两种探测模式、冲突次数统计、墓碑复用：

冲突次数统计规则：初始哈希位置如果被占用（有效元素/墓碑），每探测一次下一个位置计1次冲突。

int get_probe_idx(HTAB* table, int init_idx, const char* target_key, int* collision_cnt, int is_insert)
{
    int h = 1;
    int idx = init_idx;
    int collide = 0;
    int first_tombstone = -1; // 记录遇到的第一个墓碑位置，插入时可直接复用
    while (1) {
        int status = table->slot_status[idx];
        if (status == EMPTY) {
            *collision_cnt = collide;
            if (is_insert) return first_tombstone != -1 ? first_tombstone : idx;
            else return -1;
        }
        if (status == TOMBSTONE) {
            collide++;
            if (first_tombstone == -1) first_tombstone = idx;
            // 计算下一个探测位置
            if (table->probe_mode == LINEAR_PROBE) idx = (idx + 1) % table->size;
            else {
                idx = (init_idx + h*h) % table->size;
                h++;
            }
            continue;
        }
        // 槽位为有效元素，搜索模式下key匹配直接返回
        if (!is_insert && strcmp(table->array[idx]->key, target_key) == 0) {
            *collision_cnt = collide;
            return idx;
        }
        collide++;
        if (table->probe_mode == LINEAR_PROBE) idx = (idx + 1) % table->size;
        else {
            idx = (init_idx + h*h) % table->size;
            h++;
        }
        // 防止二次探测死循环，探测轮次超过表长直接返回
        if (h > table->size) {
            *collision_cnt = collide;
            return -1;
        }
    }
}

4. 增删查函数改造 #

插入、搜索函数加入计时、冲突统计逻辑，删除函数改为墓碑标记：

int Insert(HTAB* table, char* keycpy, char* namecpy)
{
    // 初始化单次操作统计与计时
    table->op_collision = 0;
    LARGE_INTEGER t1, t2, tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);

    if (ht_IsFull(table)) {
        printf("Hash table is FULL!!!");
        QueryPerformanceCounter(&t2);
        table->op_time = (t2.QuadPart - t1.QuadPart)*1000.0 / tc.QuadPart;
        return -1;
    }
    char* key = _strdup(keycpy);
    char* name = _strdup(namecpy);
    INFO* item = New_Item(key, name);

    int init_idx = Hash_Code(atoi(key), table->size);
    int collide = 0;
    int idx = get_probe_idx(table, init_idx, key, &collide, 1);
    if (idx == -1) {
        free(key); free(name); free(item);
        QueryPerformanceCounter(&t2);
        table->op_time = (t2.QuadPart - t1.QuadPart)*1000.0 / tc.QuadPart;
        return -1;
    }
    // 写入槽位
    table->array[idx] = item;
    table->slot_status[idx] = VALID;
    table->count++;
    // 更新累计统计
    table->op_collision = collide;
    table->total_insert_collision += collide;
    table->insert_op_cnt++;

    QueryPerformanceCounter(&t2);
    table->op_time = (t2.QuadPart - t1.QuadPart)*1000.0 / tc.QuadPart;
    return 0;
}

int Search(HTAB* table, char* key)
{
    table->op_collision = 0;
    LARGE_INTEGER t1, t2, tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&t1);

    int init_idx = Hash_Code(atoi(key), table->size);
    int collide = 0;
    int idx = get_probe_idx(table, init_idx, key, &collide, 0);
    // 更新累计统计
    table->op_collision = collide;
    table->total_search_collision += collide;
    table->search_op_cnt++;

    QueryPerformanceCounter(&t2);
    table->op_time = (t2.QuadPart - t1.QuadPart)*1000.0 / tc.QuadPart;
    return idx;
}

INFO* Remove(HTAB* table, char* key)
{
    INFO* result = NULL;
    int idx = Search(table, key);
    if (idx != -1) {
        result = table->array[idx];
        table->slot_status[idx] = TOMBSTONE; // 标记墓碑，不直接置空
        table->array[idx] = NULL;
        table->count--;
    }
    return result;
}

// 原有Display、main函数逻辑可保留，只需要把NewHTAB调用改成传入探测模式参数即可

第二步：不同装载因子性能测试实现 #

装载因子计算公式：load_factor = 表中已存元素数量 / 哈希表总长度，测试流程如下：

• 固定哈希表长度（建议选质数，减少二次探测的死循环概率，比如选1009、10007这类质数）
• 分别初始化线性探测、二次探测两个哈希表实例
• 批量生成符合要求的≥10位数字键，逐个插入
• 每插入一批元素，计算当前装载因子，记录累计插入冲突数、平均单次插入冲突数
• 到预设装载因子节点（比如0.1、0.2…直到0.9）时，随机抽取一批已存在、不存在的键做搜索测试，统计平均搜索冲突次数、平均搜索耗时
• 最终对比两种探测方式在不同装载因子下的指标差异即可

核心指标计算方式 #

• 平均插入冲突数 = 累计插入冲突次数 / 总插入操作次数
• 平均搜索冲突数 = 累计搜索冲突次数 / 总搜索操作次数
• 平均搜索耗时 = 所有搜索操作总耗时 / 总搜索操作次数

注意事项 #

• 二次探测在表长为合数、装载因子过高时，可能出现无法探测到空槽的问题，测试时尽量选择质数作为表长
• 测试搜索性能时建议分开统计「搜索命中」「搜索未命中」两类场景的指标，两者冲突次数差异较大
• 若不需要微秒级计时精度，也可替换为标准库clock()函数做耗时统计

内容的提问来源于stack exchange，提问作者Sollpix