如何在C语言结构体中实现自定义大小数组及哈希表扩容？

核心思路 #

把结构体中固定大小的数组替换为动态分配的指针，就能在运行时自由调整容量，彻底摆脱INITIAL_SIZE的限制。以下是具体实现步骤：

1. 修改哈希表结构体定义 #

移除INITIAL_SIZE宏定义（或保留但不再使用），将所有固定数组改为指针类型：

#ifndef HASHTABLE_H
#define HASHTABLE_H

#define LOAD_FACTOR 0.7
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct hashtable
{
    int *keyArray;               // 动态分配的key数组
    char **valueArray;           // 动态分配的字符串数组（每个元素长度101）
    bool *isActiveArray;         // 动态分配的活跃标记数组
    int count;                   // 当前元素数量
    int capacity;                // 当前容量
    double loadFactor;           // 负载因子阈值
    bool collisionHandler;       // true:线性探测，false:二次探测
} table;

#endif

2. 重构初始化函数 #

初始化时动态分配内部数组的内存，不再依赖固定大小：

void initTable(table* p, int initialSize, double loadFactor, bool collisionHandler) {
    p->count = 0;
    p->capacity = initialSize;
    p->loadFactor = loadFactor;
    p->collisionHandler = collisionHandler;

    // 分配key数组
    p->keyArray = (int*)malloc(sizeof(int) * initialSize);
    // 分配value数组：先分配指针数组，再为每个指针分配字符串空间
    p->valueArray = (char**)malloc(sizeof(char*) * initialSize);
    for (int i = 0; i < initialSize; i++) {
        p->valueArray[i] = (char*)malloc(sizeof(char) * 101);
        memset(p->valueArray[i], 0, 101);
    }
    // 分配活跃标记数组
    p->isActiveArray = (bool*)malloc(sizeof(bool) * initialSize);

    // 初始化数组内容
    memset(p->keyArray, 0, sizeof(int) * initialSize);
    memset(p->isActiveArray, 0, sizeof(bool) * initialSize);
}

3. 实现扩容函数 #

当负载因子超过阈值时，创建更大容量的新数组，重新哈希所有有效元素，替换旧数组并释放内存：

bool resizeTable(table* p, int newCapacity) {
    // 保存旧数组指针和容量，用于分配失败时回滚
    int* oldKeys = p->keyArray;
    char** oldValues = p->valueArray;
    bool* oldActive = p->isActiveArray;
    int oldCapacity = p->capacity;

    // 分配新数组
    p->keyArray = (int*)malloc(sizeof(int) * newCapacity);
    p->valueArray = (char**)malloc(sizeof(char*) * newCapacity);
    p->isActiveArray = (bool*)malloc(sizeof(bool) * newCapacity);
    if (!p->keyArray || !p->valueArray || !p->isActiveArray) {
        // 分配失败，恢复旧数组
        p->keyArray = oldKeys;
        p->valueArray = oldValues;
        p->isActiveArray = oldActive;
        return false;
    }

    // 初始化新数组的字符串空间
    memset(p->keyArray, 0, sizeof(int) * newCapacity);
    memset(p->isActiveArray, 0, sizeof(bool) * newCapacity);
    for (int i = 0; i < newCapacity; i++) {
        p->valueArray[i] = (char*)malloc(sizeof(char) * 101);
        memset(p->valueArray[i], 0, 101);
        if (!p->valueArray[i]) {
            // 部分分配失败，清理已分配内存并回滚
            for (int j = 0; j < i; j++) free(p->valueArray[j]);
            free(p->valueArray);
            free(p->keyArray);
            free(p->isActiveArray);
            p->keyArray = oldKeys;
            p->valueArray = oldValues;
            p->isActiveArray = oldActive;
            return false;
        }
    }

    // 重新哈希所有有效元素到新表（调用你的插入函数）
    p->count = 0;
    for (int i = 0; i < oldCapacity; i++) {
        if (oldActive[i]) {
            insert(p, oldKeys[i], oldValues[i]); // 假设你已有insert函数实现
        }
    }

    // 释放旧数组内存
    free(oldKeys);
    for (int i = 0; i < oldCapacity; i++) free(oldValues[i]);
    free(oldValues);
    free(oldActive);

    // 更新容量
    p->capacity = newCapacity;
    return true;
}

4. 在插入时自动触发扩容 #

每次插入元素前检查负载因子，超过阈值则自动扩容（通常扩容为原容量的2倍）：

bool insert(table* p, int key, const char* value) {
    // 检查负载因子，触发扩容
    if ((double)p->count / p->capacity >= p->loadFactor) {
        if (!resizeTable(p, p->capacity * 2)) {
            return false; // 扩容失败
        }
    }

    // 这里编写你的哈希计算和冲突处理（线性/二次探测）逻辑
    // ... 省略具体插入实现 ...
    return true;
}

5. 添加销毁函数避免内存泄漏 #

使用完哈希表后，释放所有动态分配的内存：

void destroyTable(table* p) {
    free(p->keyArray);
    for (int i = 0; i < p->capacity; i++) {
        free(p->valueArray[i]);
    }
    free(p->valueArray);
    free(p->isActiveArray);
    // 如果table本身是动态分配的，记得加上 free(p);
}

关键改动总结 #

• 彻底移除固定大小数组限制，改为动态内存分配，支持任意初始容量和扩容
• 扩容时通过重新哈希迁移元素，保证哈希表的查询性能
• 增加内存泄漏防护，所有动态分配的内存都有对应的释放逻辑

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