C语言分离链接法哈希表Insert插入函数仅成功插入2个键原因排查

你的代码存在以下几处错误，导致仅部分键插入成功：

• 节点存储类型与比较逻辑错误：struct ListNode的Element成员被定义为int类型，与你要存储的字符串指针类型不匹配。同时Find函数中直接使用!=比较Element和Key，本质是比较指针地址而非字符串内容，会出现大量误判。
• 插入链表逻辑错误：采用头插法插入新节点时，没有给NewCell->Next赋值为原链表的首节点，直接将L->Next覆盖为新节点，导致同一个哈希槽中之前插入的节点被直接丢弃。
• 语法错误：Insert函数返回值为void，但内存分配失败分支中写了return NULL，属于返回类型不匹配。
• 表大小计算错误：main函数中计算表初始大小的逻辑错误，你当前得到的是单个人名数组的长度20，而非要存储的人名总数6，虽不直接导致插入失败，但会造成空间浪费。

修正后的完整代码 #

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

#define MinTableSize 1

// 分离链接法解决哈希冲突
struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

typedef unsigned int Index;

Index Hash(const char *Key, int Tablesize)
{
    unsigned int HashVal = 0;
    while (*Key != '\0')
    {
        HashVal += *Key++;
    }
    return HashVal % Tablesize;
}

struct ListNode
{
    // 修改为存储字符串指针
    const char *Element;
    Position Next;
};

typedef Position List;
struct HashTbl
{
    int TableSize;
    List *TheLists;
};

// 判断是否为素数
bool isPrime(int n)
{
    if (n <= 1)
    {
        return false;
    }

    if (n <= 3)
    {
        return true;
    }

    if (n % 2 == 0 || n % 3 == 0)
    {
        return false;
    }

    for (int i = 5; i * i <= n; i = i + 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
    }
    return true;
}

// 查找下一个素数
int NextPrime(int N)
{
    if (N <= 1)
    {
        return 2;
    }
    int prime = N;
    bool found = false;

    while (!found)
    {
        prime++;
        if (isPrime(prime))
        {
            found = true;
        }
    }
    return prime;
}

// 初始化哈希表
HashTable InitializeTable(int TableSize)
{
    HashTable H;
    int i;
    if (TableSize < MinTableSize)
    {
        printf("Table size is too small\n");
        return NULL;
    }
    H = malloc(sizeof(struct HashTbl));
    if (H == NULL)
    {
        printf("Out of space\n");
        return NULL;
    }
    H->TableSize = NextPrime(TableSize);
    H->TheLists = malloc(sizeof(List) * H->TableSize);
    if (H->TheLists == NULL)
    {
        printf("Out of space\n");
        return NULL;
    }
    for (i = 0; i < H->TableSize; i++)
    {
        H->TheLists[i] = malloc(sizeof(struct ListNode));
        if (H->TheLists[i] == NULL)
        {
            printf("Out of space\n");
            return NULL;
        }
        else
        {
            H->TheLists[i]->Next = NULL;
        }
    }
    return H;
}

// 查找键
Position Find(const char *Key, HashTable H)
{
    Position P;
    List L;
    L = H->TheLists[Hash(Key, H->TableSize)];
    P = L->Next;
    // 修改为用strcmp比较字符串内容
    while (P != NULL && strcmp(P->Element, Key) != 0)
    {
        P = P->Next;
    }
    return P;
}

// 插入键
void Insert(const char *Key, HashTable H)
{
    Position Pos;
    Position NewCell;
    List L;
    Pos = Find(Key, H);
    if (Pos == NULL)
    {
        NewCell = malloc(sizeof(struct ListNode));
        if (NewCell == NULL)
        {
            printf("Out of space\n");
            // 修正返回值错误，void函数不需要返回值
            return;
        }
        else
        {
            L = H->TheLists[Hash(Key, H->TableSize)];
            // 修正头插法逻辑，先将新节点的next指向原首节点
            NewCell->Next = L->Next;
            NewCell->Element = Key;
            L->Next = NewCell;
            printf("Key %s inserted\n", Key);
        }
    }
    else
    {
        printf("Key %s already exist\n", Key);
    }
}

int main()
{
    char Name[6][20] = { "Joshua", "Erica", "Elizabeth", "Monica", "Jefferson", "Andrian" };
    // 修正表大小计算，获取名字总数6
    int Size = sizeof(Name) / sizeof(Name[0]);
    HashTable H = InitializeTable(Size);

    Insert(Name[0], H);
    Insert(Name[1], H);
    Insert(Name[2], H);
    Insert(Name[3], H);
    Insert(Name[4], H);
    Insert(Name[5], H);

    return 0;
}

运行结果 #

修正后所有6个人名都会正常插入，输出如下：

Key Joshua inserted
Key Erica inserted
Key Elizabeth inserted
Key Monica inserted
Key Jefferson inserted
Key Andrian inserted

内容的提问来源于stack exchange，提问作者Maria Marchella Gandhi