为什么map会比unordered_map快得多？

Question

我实现了一个搜索缓存结果,它包含State类型的键(一个有7个短整数的类)和一个类型为Socre的类(一个3个双精度类.)使用unordered_map比map慢至少20倍.为什么？

编辑:Darn it!我的哈希函数是

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; }

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

你需要做的是看两件事:

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

它们中的任何一个都可以并且将会杀死性能.

Answer 2

std::unordered_map由于散列函数,对于少量元素通常很慢.它需要一段固定的( - )时间,但可能还需要相当长的时间.

std::map另一方面比简单std::unordered_map.访问元素所花费的时间取决于元素的数量,但随着元素数量的增加越来越少.与cstd :: map相比,std :: map 的大哦因素通常也非常小std::unordered_map.

在一般情况下,倾向于使用std::map过std::unordered_map,除非你有特别原因需要使用std::unordered_map.如果您没有大量元素,这尤其适用.

Answer 3

unordered_map在底层使用哈希表,因此哈希表现不佳的最明显原因是因为你有太多的冲突.您可以考虑使用不同的非默认哈希函数,它可以为您的键类型提供更好的结果.