Маркировка ведра как удаленного в Hash Table
У меня были некоторые проблемы с поиском достойного объяснения этому. Я пишу хэш-таблицу с линейным зондированием, используя C ++, но у меня возникли проблемы с remove() операция. Я хэширую коллекцию словарей stringsи мне интересно, как бы я установить индекс i удалить из как удалено, так что search() а также insert() работать должным образом. Любая помощь / псевдокод будет здорово, спасибо. Моя лучшая догадка сейчас, это сделать какой-то объект структуры с именем deleted и поместите это там.
Решение
Каждое ведро может быть 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
};
Другие решения
Других решений пока нет …