开放寻址冲突解决的哈希表实现：动态数组调用与扩容疑问

第一个问题：Create中创建的数组能否被其他成员函数调用 #

答案是不能
你当前在Create函数中定义的hashtable和A_Array都是函数内部的局部变量，函数执行完成后就会被自动销毁，类的其他成员函数（Insert/Delete等）完全无法访问这两个变量，更别说正常调用了。

第二个问题：能否重复调用Create实现扩容 #

当前实现下完全不可以
除了上面提到的局部变量问题外，就算你把两个数组改成类成员，直接重复调用Create也会直接丢弃原有数组里存储的所有哈希映射关系和字符串数据，没有做旧数据的迁移，完全不符合扩容的要求。

当前结构设计存在的问题 #

• 冗余成员变量：int& rN = N完全没有存在必要，直接使用N即可；私有成员string key也属于冗余设计，所有字符串值应该存储在A数组中，不需要类全局保留单个key。
• 动态数组没有作为类成员存在，生命周期仅局限在Create函数内，无法实现哈希表的持久存储。

更合理的实现方式 #

第一步：修改类成员定义 #

把两个动态数组改为类私有成员，示例代码如下：

class Lexicon {
   private:
        int N; // 哈希表槽位数量
        int used_slot_count; // 已使用槽位数量，用于计算负载因子触发扩容
        std::unique_ptr<int[]> hashtable; // 哈希表数组，存储A数组的索引，空槽可以用-1标记，删除标记用-2
        std::unique_ptr<char[]> A_Array; // 存储实际字符串的数组
        int A_used; // A数组已使用的偏移量，用于写入新字符串
    
    public:
        Lexicon (int init_slot_size); // 构造函数直接初始化，不需要单独的Create函数
        void Insert(string key);
        void Delete(string key);
        void Resize(int new_slot_size); // 单独抽离扩容函数
};

第二步：初始化逻辑 #

建议把初始化逻辑放到构造函数中，不需要单独的Create函数，避免重复调用导致的问题，构造函数示例：

Lexicon::Lexicon(int init_slot_size) : N(init_slot_size), used_slot_count(0), A_used(0) {
    hashtable = std::make_unique<int[]>(N);
    // 初始化所有哈希槽为-1，表示空槽
    for(int i=0; i<N; i++) hashtable[i] = -1;
    A_Array = std::make_unique<char[]>(15 * N);
}

第三步：扩容逻辑实现 #

扩容需要单独抽离Resize函数处理，核心逻辑是：

1. 申请新大小的哈希表数组和A数组
2. 遍历旧哈希表的所有有效槽位，把对应的字符串重新哈希插入到新的哈希表中，同时把字符串复制到新的A数组
3. 替换类成员的哈希表、A数组指针，更新N、used_slot_count、A_used等统计变量
4. 旧数组会被unique_ptr自动释放，不需要手动管理内存

其他注意点 #

• 开放寻址需要处理冲突的探查逻辑，比如线性探查、二次探查，插入、删除、查找都要遵循同一套探查规则
• 负载因子超过阈值（通常开放寻址设为0.7左右）就自动触发扩容，不需要手动调用扩容函数
• A数组如果存储字符串要注意预留结束符\0的位置，或者改用std::unique_ptr<std::string[]>存储字符串，会更方便管理内存，不需要手动处理char数组的写入和偏移。

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