c++ - 插入到 std::unordered_multimap 时有没有办法避免散列/equalityChecking？

Question

我正在使用 std::unordered_multimap mymap 作为我的数据结构，用于保存和快速访问超过 1000 万个 T 类型的元素(~10GB 数据)作为键使用自定义和不可避免的昂贵散列和相等(operator==)函数。

问题是将所有数据集加载并存储到 mymap 所需的时间比我熟悉的时间(大约 45 分钟左右)长得多，并且由于在存储数据后它不会改变，所以我决定迭代buckets 并将它们的元素写入单独的文件(序列化)，所以下次我只需要创建足够的 buckets，保留内存，然后直接将它们放在它们的位置(反序列化)并避免散列和相等性检查。

这将大大减少加载时间。 (低至 ~60 秒)

遗憾的是，我找不到将元素直接插入到 std::unordered_multimap 的底层数据结构并绕过散列/equalityChecking 的方法。

更新:

• 原来我的哈希算法有一个错误，导致我的元素只堆积在几个桶中，我修复了这个问题，然后只用了 81 秒就将数据集加载到 map 中。 (从大约 45 分钟减少)
• 正如@aconcagua 所建议的，我尝试为我的数据类型使用预先计算的哈希值，并将加载时间减少到 79 秒。所以看起来我的散列算法毕竟不是那么昂贵，我已经尽力确保我的相等函数针对每个操作进行了优化，我猜它并没有变得更快。我应该研究编写自己的 HashMap 。

Answer 1

std::unordered_map 不提供此类功能，您将依赖肮脏的 hacks。因此，您可以编写自己的 HashMap 以允许此类操作 - 或者您可以按如下方式减少哈希计算所花费的时间:

class C
{
    size_t m_hashCode;
    bool m_isHashDirty;

public:
    C() : m_isHashDirty(true);

    size_t hashCode()
    {
        if(m_isHashDirty)
        {
             m_hashCode = /* result of complex calculations */;
        }
        return m_hashCode;
    }
};

对该对象的任何修改都会设置脏标志，但您只会在需要时以及如果对之前的调用有更改时才计算哈希值。

您当然会在序列化时存储哈希码，并在反序列化时恢复它，将脏标志设置为 false。

相等运算符提供较少的优化选项，当然您可以在第一个检测到的不同成员上简化结果，但直到检查最后一个成员时才能确定是否相等。因此，您可能宁愿改进哈希函数以减少冲突。