为什么地图比unordered_map快得多？

问题描述：

我实现了一个搜索缓存结果，它包含State类型的键（有7个短整数的类）和Socre类型的值（一个3双的类）。使用unordered_map的速度至少比map快20倍。为什么？为什么地图比unordered_map快得多？

编辑：收藏！我的哈希函数是

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（）函数。

什么是您的访问模式？ – 2011-01-31 01:09:05

什么平台/编译器？ – ThomasMcLeod 2011-01-31 01:10:30

英特尔i5，海湾合作委员会，60万插入和查找 – 2011-01-31 01:12:22

答

unordered_map的速度与您的散列函数的速度成正比。这从来都不是直接的关系。典型的例子，如果你用最简单的散列函数：

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

那么你就会有最终是表现得像一个列表，而不是一个散列容器的集合。所有的物品都会映射到一个桶，你必须穿过整个桶，直到你到达你想要的物品（可能需要O（N）时间。）

你需要做的是看有两件事：

你使用的是什么散列函数？这会花费大量的时间来处理吗？
它产生多少次碰撞？也就是说，有多少独特的元素被映射到相同的散列值？

这些都是他们自己能够而且会杀死的表现。

答

std::unordered_map由于散列函数对少数元素通常很慢。它需要固定的时间，但可能需要很长时间。

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

一般而言，除非您有特定的理由使用std::unordered_map，否则更喜欢使用std::map而不是std::unordered_map。如果你没有大量元素，这尤其适用。

答

unordered_map在引擎盖下使用了一个哈希表，所以哈希性能差的原因最明显的原因是因为碰撞太多。您可以考虑使用不同的非默认哈希函数，以便为您的键类型提供更好的结果。

答

对于

我希望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，更好的是散列函数。

为什么地图比unordered_map快得多？

相关推荐