双重哈希开放寻址哈希表实现求助：排查插入删除逻辑错误

我正在实现一个基于双重哈希的开放寻址哈希表，支持插入和删除操作。哈希表包含37个哈希槽，使用给定的hash1和hash2函数（hash2是双重哈希的增量函数）。

• 插入函数返回键比较次数：插入重复键返回-1；若键比较次数超过表大小，说明表已满
• 删除函数返回键比较次数：要删除的键不存在返回-1；删除过程中的键比较次数不能超过表大小

目前代码在隐藏测试用例中出错，需要找出代码中的问题。

原代码 #

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

#define TABLESIZE 37
#define PRIME     13

enum Marker {EMPTY,USED,DELETED};

typedef struct _slot{
    int key;
    enum Marker indicator;
} HashSlot;

int HashInsert(int key, HashSlot hashTable[]);
int HashDelete(int key, HashSlot hashTable[]);


int hash1(int key);
int hash2(int key);

int main()
{
    int opt;
    int i;
    int key;
    int comparison;
    HashSlot hashTable[TABLESIZE];

    for(i=0;i<TABLESIZE;i++){
        hashTable[i].indicator = EMPTY;
        hashTable[i].key = 0;
    }

    printf("============= Hash Table ============\n");
    printf("|1. Insert a key to the hash table  |\n");
    printf("|2. Delete a key from the hash table|\n");
    printf("|3. Print the hash table            |\n");
    printf("|4. Quit                            |\n");
    printf("=====================================\n");
    printf("Enter selection: ");
    scanf("%d",&opt);
    while(opt>=1 && opt <=3){
        switch(opt){
        case 1:
            printf("Enter a key to be inserted:\n");
            scanf("%d",&key);
            comparison = HashInsert(key,hashTable);
            if(comparison <0)
                printf("Duplicate key\n");
            else if(comparison < TABLESIZE)
                printf("Insert: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Key Comparisons: %d. Table is full.\n",comparison);
            break;
        case 2:
            printf("Enter a key to be deleted:\n");
            scanf("%d",&key);
            comparison = HashDelete(key,hashTable);
            if(comparison <0)
                printf("%d does not exist.\n", key);
            else if(comparison <= TABLESIZE)
                printf("Delete: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Error\n");
            break;
        case 3:
            for(i=0;i<TABLESIZE;i++) printf("%d: %d %c\n",i, hashTable[i].key,hashTable[i].indicator==DELETED?'*':' ');
            break;
        }
        printf("Enter selection: ");
        scanf("%d",&opt);
    }
    return 0;
}

int hash1(int key)
{
    return (key % TABLESIZE);
}

int hash2(int key)
{
    return (key % PRIME) + 1;
}

int HashInsert(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 0;

    while (hashTable[hash].indicator == USED && hashTable[hash].key != key && i < TABLESIZE) {
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
        comparisons++;
    }

    if (hashTable[hash].key == key&&hashTable[hash].indicator == USED) {
        return -1;  // Key already exists
    }

    if (i >= TABLESIZE) {
        return comparisons ;  // Table is full, count initial comparison
    }

    hashTable[hash].key = key;
    hashTable[hash].indicator = USED;
    return comparisons ;  // Count initial comparison
}

int HashDelete(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 1;

    while (hashTable[hash].indicator != EMPTY && i < TABLESIZE) {
        if (hashTable[hash].indicator == USED && hashTable[hash].key == key) {
            hashTable[hash].indicator = DELETED;
            return comparisons;
        }
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
        comparisons++;
    }

    return -1;  // Key not found
}

代码中的错误分析 #

插入函数（HashInsert）的问题

1. 比较次数统计遗漏初始检查
   进入循环前，已经对第一个哈希槽进行了状态和键的检查，这一次操作应该计入比较次数。当前代码中comparisons初始为0，仅在循环内递增，导致第一次比较未被统计。例如，当键正好落在hash1计算的位置时，返回的比较次数是0，但实际应为1。
2. 未利用已删除的槽位
   循环条件仅判断USED状态的槽，忽略了DELETED状态的槽。在开放寻址哈希表中，DELETED的槽应该可以被新插入的键复用，当前逻辑会跳过这些槽，导致空间浪费，提前触发表满的错误。
3. 表满时的比较次数返回错误
   当遍历完所有TABLESIZE个槽后，i的值会等于TABLESIZE，此时实际进行了TABLESIZE次比较，但当前代码返回的comparisons是TABLESIZE-1，不符合题目要求。

删除函数（HashDelete）的问题

1. 循环终止条件逻辑错误
   循环条件hashTable[hash].indicator != EMPTY && i < TABLESIZE存在问题：当遍历过程中遇到EMPTY槽时，说明要找的键肯定不存在（因为插入时遇到EMPTY就会停止），此时应直接终止循环。但当前逻辑会同时判断i < TABLESIZE，可能导致不必要的遍历；另外，当i达到TABLESIZE时，无论当前槽状态如何，都必须终止循环，避免数组越界。
2. 比较次数可能超过表大小
   当遍历到第TABLESIZE个槽时，comparisons会被递增到TABLESIZE+1，违反了题目中“删除过程中的键比较次数不能超过表大小”的要求。

修正后的代码 #

修正后的HashInsert函数

int HashInsert(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 0;
    int first_deleted = -1; // 记录第一个遇到的DELETED槽位

    while (i < TABLESIZE) {
        comparisons++; // 每次进入循环都计数一次比较
        if (hashTable[hash].indicator == USED) {
            if (hashTable[hash].key == key) {
                return -1; // 重复键
            }
        } else if (hashTable[hash].indicator == EMPTY) {
            // 找到空槽，直接插入
            hashTable[hash].key = key;
            hashTable[hash].indicator = USED;
            return comparisons;
        } else { // DELETED状态
            if (first_deleted == -1) {
                first_deleted = hash; // 记录第一个可复用的槽
            }
        }
        // 继续探测下一个槽
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
    }

    // 遍历完所有槽，检查是否有可复用的DELETED槽
    if (first_deleted != -1) {
        hashTable[first_deleted].key = key;
        hashTable[first_deleted].indicator = USED;
        return comparisons;
    }

    // 表已满
    return comparisons;
}

修正后的HashDelete函数

int HashDelete(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 0;

    while (i < TABLESIZE) {
        comparisons++;
        if (hashTable[hash].indicator == EMPTY) {
            // 遇到空槽，键不存在
            return -1;
        }
        if (hashTable[hash].indicator == USED && hashTable[hash].key == key) {
            hashTable[hash].indicator = DELETED;
            return comparisons;
        }
        // 继续探测下一个槽
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
    }

    // 遍历完所有槽，未找到键
    return -1;
}

修正说明 #

• 插入函数：新增了记录第一个DELETED槽的逻辑，确保可以复用已删除的空间；修正了比较次数的统计，每次循环都计数；遍历完所有槽后优先使用DELETED槽，否则返回表满。
• 删除函数：修正了比较次数的统计逻辑，每次循环计数一次；遇到EMPTY槽直接终止并返回-1；确保最多进行TABLESIZE次比较，不会超过限制。

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