12

我实现了一个搜索缓存结果，它由 State 类型的键（具有 7 个短整数的类）和类型的值Score（3 个双精度类）组成。使用 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() 函数来报告平均碰撞次数。

4

4 回答 4

17

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

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

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

你需要做的是看两件事：

  1. 你用的是什么哈希函数？处理是否花费了可笑的时间？
  2. 它产生了多少次碰撞？也就是说，有多少独特的元素被映射到同一个哈希值？

其中任何一个都可以而且会扼杀性能。

于 2011-01-31T01:25:27.603 回答
10

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

std::map另一方面比 更简单std::unordered_map。访问元素所需的时间取决于元素的数量，但随着元素数量的增加，时间会越来越少。与. c_std::unordered_map

通常，除非您有特定的理由使用 ，否则std::map更喜欢使用. 如果您没有大量元素，这尤其适用。std::unordered_mapstd::unordered_map

于 2011-01-31T01:16:36.553 回答
8

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

于 2011-01-31T01:24:55.043 回答
0

为了

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

于 2011-01-31T03:38:26.747 回答