C语言哈希表实现通讯录：如何避免重复调用checkDuplicate查重函数

你当前代码出现两次checkDuplicate()调用的核心原因，是把「初始索引校验」「线性探测找空位」「重复值判断」三个逻辑拆成了独立步骤，实际上线性探测哈希表的插入规则本身就要求 从哈希计算得到的初始索引开始，逐位向后遍历直到遇到空槽——如果待插入的手机号已经存在，必然在这条探测路径上，完全不需要拆分多次校验，只要把查重逻辑嵌入探测遍历的过程，走一遍流程就能同时完成重复拦截和空位查找。

具体改造点 #

• 原代码的linearRehash()遍历是从初始索引的下一位开始的，漏掉了初始索引位置的校验，才需要在外层单独补初始位的查重、重哈希返回后的二次查重
• 把查重逻辑统一放到探测遍历循环里，从初始索引开始，对每一个遍历到的槽位依次做重复判断、空槽判断，遍历全程仅做一次字符串比对，没有冗余调用
• 用返回值区分三种探测结果：找到空插入位、找到重复号码、哈希表已满

优化后实现代码 #

// 探测函数返回值约定
#define DUPLICATE_NUM -1
#define TABLE_FULL -2

int probeInsertPos(int initIndex, int tableSize) {
    int current = initIndex;
    // 最多遍历整个表的所有槽位，避免死循环
    for (int i = 0; i < tableSize; i++) {
        // 先校验当前槽位是否是重复号码
        if (!strcmp(table1.listContact[current].phoneNum, temp.phoneNum)) {
            return DUPLICATE_NUM;
        }
        // 再校验当前槽位是否为空（"foo"是原代码定义的空槽标记）
        if (!strcmp(table1.listContact[current].phoneNum, "foo")) {
            return current; // 返回可插入的空位索引
        }
        // 不满足条件则线性探测下一个位置
        current = (current + 1) % tableSize;
    }
    return TABLE_FULL;
}

void inputData(){
    printf("Enter contact name  : "); 
    gets(temp.name);
    fflush(stdin);
    printf("Enter contact email : "); 
    gets(temp.email);
    fflush(stdin);
    printf("Enter contact phone number : "); 
    gets(temp.phoneNum);
    fflush(stdin);

    int tableSize = sizeof(table1.listContact)/sizeof(table1.listContact[0]);
    int initIndex = hash(temp.phoneNum, tableSize);
    int probeRes = probeInsertPos(initIndex, tableSize);

    if (probeRes == DUPLICATE_NUM) {
        puts("Number is used");
        return;
    }
    if (probeRes == TABLE_FULL) {
        puts("Memory Full");
        return;
    }
    // probeRes为合法空位索引，直接写入联系人数据
    strcpy(table1.listContact[probeRes].name, temp.name);
    strcpy(table1.listContact[probeRes].email, temp.email);
    strcpy(table1.listContact[probeRes].phoneNum, temp.phoneNum);
}

额外注意点 #

• 改造后完全删除了冗余的checkDuplicate()单独调用，所有查重逻辑都在探测遍历过程中完成，每个槽位仅比对一次，没有重复计算
• 原代码用特殊字符串"foo"作为空槽标记存在逻辑漏洞，如果用户真的输入foo作为手机号会触发异常，建议给联系人结构体增加独立的int is_empty状态位标记槽位是否被占用，可靠性更高
• 原代码使用的gets()函数存在缓冲区溢出安全风险，建议替换为fgets()实现输入读取

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