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

[Anonymous]

Я реализовал хеш-таблицу Робин Гуда для операции хеш-соединения базы данных. Он компилируется и работает правильно, но работает значительно хуже, чем std::unordered_map, что указывает на логическую ошибку в моей реализации.
Проблема: хеш-таблица работает функционально, но медленнее, чем ожидалось. Я подозреваю, что в моей логике вставки или поиска есть ошибка.
Контекст:
Я заменяю std::unordered_map на специальную RobinHoodTable для хэш-соединения базы данных. Каждая запись хеш-таблицы хранит несколько индексов строк для каждого ключа (для обработки повторяющихся ключей соединения).
Детали реализации:
Вставка на основе PSL с заменой записей
Записи сохраняются как std::optional где 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 ... rdered-map