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

Question

我一直在为这件事找一个像样的解释。我正在使用C++编写一个线性探测哈希表，但是我在使用remove()操作时遇到了问题。我正在散列strings的字典集合，我想知道如何将索引i remove from设置为deleted，这样search()和insert()才能正常工作。任何帮助/伪代码都会很棒，谢谢。我现在最好的猜测是创建一个名为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
};