c++ - 在哈希表中将存储桶标记为已删除

Question

我一直很难找到一个体面的解释。我正在使用 C++ 编写一个线性探测哈希表，但我遇到了remove()操作问题。我正在散列一个字典集合strings，我想知道如何将索引i删除设置为已删除，以便search()andinsert()正常工作。任何帮助/伪代码都会很棒，谢谢。我现在最好的猜测是调用某种结构对象deleted并将其放置在那里。

Answer 1

每个桶可以是一个struct包含键、值和一个标志来指示桶是否为空，如下所示：

struct bucket
{
    std::string key;
    std::string value;
    bool empty = true;
};

然后你可以有一个std::vector这样的桶：

class hash_table
{
public:
    hash_table(): buckets(100) {} // hash table has 100 buckets

    void put(std::string const& key, std::string const& value)
    {
        // ...
    }

    // etc...

private:
    std::vector<bucket> buckets; // the table
};