3. 散列表

习题

#30016

⚡5⏳4

在 30004 的开放寻址字符串集合上增加删除操作：

#include <stdbool.h>

bool string_set_remove(
    StringSet *set,
    const char *key,
    bool *out_removed
);

要求：

1. 删除后必须使用墓碑标记，不能直接把槽恢复为空；查询遇到墓碑时必须继续探测。
2. 插入重复键时仍应识别原键；可以复用最早遇到的墓碑，但必须继续探测以确认不存在重复键。
3. 当墓碑数量达到实现所规定的阈值时，重新散列全部现存键并清除墓碑；重建失败时集合和输出对象保持不变。
4. 删除不存在的键应成功返回并设置 *out_removed = false；参数无效时返回 false，不得修改输出对象。
5. 说明开放寻址删除为什么需要墓碑，并保持查询、插入和删除的期望时间复杂度为 $O(1)$。