为什么地图会比unordered_map快得多？

Question

我实现了一个搜索缓存结果，该结果由State类型的键（一个具有7个短整数的类）和类型Score的值（一个3个double的类）组成。使用unordered_map至少比map慢20倍。为什么？

编辑：该死！我的哈希函数是

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

我忘记了return retval，所以一切都在碰撞！我希望unordered_map有一个hash_function_quality（）函数来报告平均碰撞次数。

Answer 1

unordered_map的速度与您的哈希函数的速度成正比。这绝不是直接的关系。例如，如果您使用最简单的哈希函数：

std::size_t myHash(MyObjectType _object){ return 1; }

Answer 2

std::unordered_map通常由于散列函数而对于少数元素而言较慢。它花费固定的时间（-ish），但仍然可能要花费大量时间。

Answer 3

unordered_map在后台使用哈希表，所以哈希执行不佳的最明显原因是因为冲突太多。您可以考虑使用其他非默认的哈希函数，该函数将为您的键类型提供更好的结果。

Answer 4

对于