为什么 map 比 unordered_map 快得多？

Question

我实现了一个搜索缓存结果，其中包含 State 类型的键（一个包含 7 个短整数的类）和 Score 类型的值（一个包含 3 个双精度数的类）。使用 unordered_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);
        }
    }
}

我忘记返回 retval ，所以它全部发生冲突！我希望 unordered_map 有一个 hash_function_quality() 函数来报告平均冲突数。

Answer 1

unordered_map 的速度与哈希函数的速度成正比。这从来都不是一种直接的关系。举个例子，如果您使用最简单的散列函数：

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

那么您最终会得到一个行为类似于列表而不是散列容器的集合。所有项目都将映射到一个存储桶，您必须遍历整个存储桶，直到找到所需的项目（这可能需要 O(N) 时间。）

您需要做的是查看两件事：

1. 您使用什么哈希函数？处理过程是否需要花费大量时间？
2. 它产生了多少次碰撞？也就是说，有多少唯一元素被映射到相同的哈希值？

其中任何一个本身都可能并且将会破坏性能。

Answer 2

由于哈希函数的原因，std::unordered_map 对于少量元素来说通常很慢。这需要固定的（-ish）时间，但可能仍然是相当长的时间。

另一方面，std::map 比 std::unordered_map 更简单。访问元素所需的时间取决于元素的数量，但随着元素数量的增加，时间会越来越少。与 std::unordered_map 相比，std::map 的大哦因子 c 通常也非常小。

一般来说，优先使用 std::map 而不是 std::unordered_map，除非您有特定原因使用 std::unordered_map。如果您没有大量元素，则尤其如此。

Answer 3

unordered_map 在底层使用哈希表，因此哈希性能不佳的最明显原因是冲突太多。您可以考虑使用不同的非默认哈希函数，这将为您的键类型提供更好的结果。

Answer 4

为了

我希望 unordered_map 有一个
hash_function_quality() 函数
报告平均数量
碰撞。

我认为以下功能可能会有所帮助。

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

load_factor 越低，哈希函数越好。