Coalesced Hashing的HashInsert与HashFind函数问题求助

• 检查冲突链的维护逻辑：Coalesced Hashing要求冲突节点挂在主桶的链尾而非头部，若插入时错误地将新节点插在链首，会导致查找时遍历顺序错误——样例可能刚好是顺序插入场景，但隐藏测试大概率包含逆序或乱序插入的用例。
• 验证空槽标记规则：确保插入时正确标记已使用的槽位，查找时严格跳过未使用的槽。若空槽判断逻辑存在漏洞（比如用0作为空标记但允许键值为0），隐藏测试中出现键值为0的元素会直接导致查找失败或插入异常。
• 核对哈希函数的边界处理：哈希计算时取模操作必须匹配哈希表的实际长度，比如数组长度为TABLE_SIZE时，需用hash(key) % TABLE_SIZE而非hash(key) % (TABLE_SIZE-1)。样例可能未触发边界场景，但隐藏测试必然包含哈希值刚好等于数组长度的情况。
• 确认链尾的终止标记：Coalesced Hashing中链尾的next指针应设为无效值（比如-1或等于TABLE_SIZE的数值），若错误地用0作为链尾标记，当槽位0被占用时会导致冲突链提前终止，后续节点无法被遍历到。
• 检查查找遍历的终止条件：查找时必须遍历到链尾才停止，而非中途遇到空槽就直接退出。即使作业不要求支持删除，插入时的链维护错误也可能导致冲突链中间出现无效节点，隐藏测试会专门覆盖这类场景。
• 测试重复键的处理逻辑：若作业要求不允许重复键值，需确认HashInsert()在插入前会先执行查找操作，若键已存在则返回错误。样例通常不会包含重复键，但隐藏测试必然会覆盖这个场景。

参考逻辑片段 #

以下是符合Coalesced Hashing规范的插入、查找函数伪代码（供你对比排查）：

// 哈希表结构定义（示例）
typedef struct {
    int key;
    int used;
    int next;
} HashEntry;

#define TABLE_SIZE 100
HashEntry table[TABLE_SIZE];

// 哈希函数示例（可替换为作业要求的实现）
int hash(int key) {
    return key % TABLE_SIZE;
}

// 插入函数逻辑
int HashInsert(int key) {
    int idx = hash(key);
    // 主桶为空，直接插入
    if (!table[idx].used) {
        table[idx].key = key;
        table[idx].used = 1;
        table[idx].next = -1;
        return 1;
    }
    // 遍历到冲突链的尾部
    int curr = idx;
    while (table[curr].next != -1) {
        curr = table[curr].next;
    }
    // 寻找第一个空槽
    int empty_slot = -1;
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (!table[i].used) {
            empty_slot = i;
            break;
        }
    }
    if (empty_slot == -1) return 0; // 哈希表已满
    // 在空槽插入新节点，并链接到链尾
    table[empty_slot].key = key;
    table[empty_slot].used = 1;
    table[empty_slot].next = -1;
    table[curr].next = empty_slot;
    return 1;
}

// 查找函数逻辑
int HashFind(int key) {
    int idx = hash(key);
    int curr = idx;
    // 遍历冲突链直到链尾
    while (curr != -1) {
        if (table[curr].used && table[curr].key == key) {
            return curr; // 返回找到的槽位索引
        }
        curr = table[curr].next;
    }
    return -1; // 未找到
}

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