为什么map比unordered_map快得多？

Question

我实现了一个搜索缓存结果，由类型为 State（一个带有 7 个 short int 的类）的键和类型为 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() 函数，可以报告平均冲突次数。

- Neil G

---

你正在使用 unordered_map 的哈希函数吗？ - Chris O

如果我不是这样，它会起作用吗？ - Neil G

对于六十万次插入，我可能仍然会使用 std::map。只有大约19个操作来访问一个元素。任何计算机都可以非常快速地执行19个操作，即使是20世纪50年代的原型计算机也是如此。 - wilhelmtell

在值返回函数的结尾处掉落实际上是未定义行为。GCC对此有一个警告，即-Wreturn-type，它包含在-Wall中。 - Fred Nurk

太棒了，你已经学会如何将cmake用作IDE了。 - Steven Lu

Answer 1

unordered_map的速度与你的哈希函数的速度成正比。这并不是一个简单的关系。例如，如果使用最简单的哈希函数：

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

如果这样做，你最终得到的是一个表现类似于列表而非哈希容器的集合。所有项目都将映射到单个存储桶(bucket)，你必须遍历整个存储桶(bucket)直到访问所需的项目（可能需要O(N)时间）。

你需要做的是看两件事：

1. 你正在使用哪种哈希函数？处理它的时间是否太长了？
2. 它产生了多少冲突(collisions)？也就是说，有多少个唯一的元素被映射到相同的哈希值？

其中任何一项都可以并且会影响性能。

- wheaties

---

这是让我意识到可能出了什么问题的答案，因此接受它。 - Neil G

Answer 2

std::unordered_map由于哈希函数的原因，在元素数量较少时通常速度较慢。它需要一个固定（大致）的时间，但可能仍然需要相当长的时间。

std::map相比之下要简单一些。访问其中一个元素所需的时间取决于元素的数量，但随着元素数量的增加，这种影响会逐渐变小。而且与std::unordered_map相比，std::map的大O系数通常也非常小。

通常情况下，除非你有特殊原因使用std::unordered_map，否则应该优先使用std::map。尤其是当你没有大量元素时。

- wilhelmtell

---

难以置信一个哈希函数会比遍历二叉树慢20倍。 - ThomasMcLeod

@ThomasMcLeod：OP没有提供任何关于这个的细节。不仅哈希函数可能比预期的时间更长，而且朴素的哈希函数可能会生成大量冲突。 - Fred Nurk

@Fred，我不明白你所说的“没有任何细节”。我们确实缺少访问模式的信息。但是假设典型的冲突情况，20倍并不合理。 - ThomasMcLeod

谢谢您的建议。我下次一定会记住的。 - Neil G

@Fred，抱歉，我在问题下面的评论中提供了一些信息。 - Neil G

Answer 3

unordered_map使用哈希表来实现，因此哈希表性能差的最明显原因是碰撞太多。您可以考虑使用不同的非默认哈希函数，以获得更好的针对您键类型的结果。

- Alexei Polkhanov

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，哈希函数就会更好。

- Arun

---

我看了一下load_factor，但问题不在于元素（E[elements]）与桶的比例，而是元素平方的期望（E[elements^2]）。 - Neil G