具有良好性能的c++ map实现

Question

我想将一些键映射到其他数据结构，其中键列表是从互联网接收的。

std::unordered_map 是 O(1)，但最坏的情况是 O(N)
std::map 总是 O(log N)

是否有另一种具有 O(1) 最佳情况和 O(log N) 最坏情况性能的 map 实现？

Answer 1

正如您所指出的，std::unordered_map 的最坏情况是线性的，因此与其要求更好的最坏情况(不存在这样的容器 - 如果存在，则标准不会使用它) ，或者至少提供这样的变化？)让我们考虑一下是什么导致最坏的情况，看看我们是否可以阻止它。

在这种情况下，std::unordered_map(几乎可以肯定)是一个散列映射，所以最坏的情况发生在您插入的每个项目散列到 sme 值并且它们所有链接到一个桶中(有效地使 hashmap 成为一个链表)。

因此，只要您拥有一个合理的散列函数，最坏的情况就永远不会发生，并且您最终会得到一个恒定时间的操作。