Хэш-таблица Робина Гуда медленнее, чем std::unordered_map — проблема с производительностью ⇐ C++

[Anonymous]

Я реализовал хеш-таблицу Робин Гуда, используя классический алгоритм «украсть у богатых, отдать бедным», основанный на PSL (длина последовательности зонда). Однако когда я сравниваю его с std::unordered_map в рабочей нагрузке хеш-соединения, моя реализация работает хуже или равной, что указывает на ошибку производительности.
Я заменяю std::unordered_map на специальную RobinHoodTable для хеш-соединения базы данных. Каждая запись хэш-таблицы должна хранить несколько индексов строк для каждого ключа (для обработки повторяющихся ключей соединения).
Вставка на основе PSL с заменой записей
Записи, хранящиеся как std::optional
where Entry = {Key key, size_t psl, std::vector index
Дубликаты ключей добавляются к индексам вектор
Таблица фиксированного размера (без динамического изменения размера)
Начальная емкость: build_size * 2, где build_size — количество вставляемых строк
void insert(const Key& key, size_t idx) {
size_t p = hash(key) % size;
size_t vpsl = 0;
Key k = key;
std::vector v{idx};

while(table[p].has_value()) {
if(table[p]->key == key) {
table[p]->indices.push_back(idx);
return;
}

if(vpsl > table[p]->psl) {
std::swap(k, table[p]->key);
std::swap(v, table[p]->indices);
std::swap(vpsl, table[p]->psl);
}
p = (p + 1) % size;
vpsl++;
}
table[p] = Entry{k, vpsl, std::move(v)};
}

std::optional search(const Key& key) {
size_t p = hash(key) % size;
size_t vpsl = 0;

while(table[p].has_value()) {
if(table[p]->key == key) {
return &table[p]->indices;
}
if(vpsl > table[p]->psl) {
return std::nullopt;
}
p = (p + 1) % size;
vpsl++;
}
return std::nullopt;


Подробнее здесь: https://stackoverflow.com/questions/797 ... ance-issue