std::unordered_map中的桶接口有什么用途？

Question

我一直在观看CppCon 2014的视频，发现有一个接口可以访问std::unordered_map下面的桶。现在我有几个问题：

• 是否有任何合理的使用此接口的示例？
• 为什么委员会决定定义这个接口，通常的STL容器接口不足以满足需求吗？

- Kostya

---

@πάνταῥεῖ 不，这不是特定于实现的。std::unordered_map 的标准接口暴露了这个实现细节。这太可怕了。 - The Paramagnetic Croissant

@πάνταῥεῖ说：这是标准库的一部分，可以在此处查看：http://en.cppreference.com/w/cpp/container/unordered_map/begin2。 - Kerrek SB

@KerrekSB 虽然问题应该是自包含的，不是吗？ - πάντα ῥεῖ

@TheParamagneticCroissant：有什么可怕的？它需要一个哈希函数，具有平摊O(1)插入，平均O(1)搜索... 它不像是一个必须实现为哈希表的神秘物品，而且能够利用它的所有属性非常有用（与例如std::priority_queue相比，后者虽然要求特定的实现但接口非常有限，几乎对任何具体用途都没什么用）。 - Matteo Italia

常数因子。标准中接口的表述方式意味着它必须使用链表来处理冲突，这是实现哈希表最慢的方法之一。标准应该允许更大的灵活性，以便库提供者有机会使其尽可能快。 - The Paramagnetic Croissant

Answer 1

通常寻找引入某一项的提案是有启发性的，因为通常会有相应的解释。在这种情况下，N1443 这篇文章说：

G. Bucket接口

像所有标准容器一样，每个哈希容器都有成员函数begin()和end()。 范围[c.begin()，c.end())包含容器中的所有元素，呈现为平面范围。 桶内的元素是相邻的，但迭代器接口不提供任何关于一个桶何时结束另一个桶开始的信息。

公开桶结构也很有用，原因有两个。 首先，它允许用户调查其哈希函数的性能：它允许他们测试元素如何均匀地分布在桶内，并查看桶内的元素以查看它们是否具有任何共同属性。 其次，如果迭代器具有底层分段结构（就像它们在现有的单向链表实现中所做的那样），利用该结构的算法，使用显式嵌套循环的算法可能比视图将元素视为平面范围的算法更有效率。

桶接口的最重要部分是对begin()和end()的重载。如果n是一个整数，则[begin（n），end（n））是指向第n个桶中元素的迭代器范围。当然，这些成员函数返回迭代器，但不是X :: iterator或X :: const_iterator类型的迭代器。相反，它们返回X :: local_iterator或X :: const_local_iterator类型的迭代器。局部迭代器能够在桶内进行迭代，但不一定能够在桶之间进行迭代； 在某些实现中，X :: local_iterator可以是比X :: iterator更简单的数据结构。 X :: iterator和X :: local_iterator被允许成为同一种类型；使用双向链表的实现可能会利用该自由度。

SGI、Dinkumware和Metrowerks实现中均未提供此桶（Bucket）接口。这一接口部分启发自Metrowerks碰撞检测接口，部分启发自早期对于分段容器算法的研究（请参见Austern 1998）。

- Howard Hinnant

Answer 2

我想，如果你处于高性能环境中，冲突最终导致你失败，你可以从这方面获得很大的好处。定期迭代桶并查看桶大小可以告诉你是否哈希策略足够好。

无序映射在性能方面非常依赖于其哈希策略。

- NG.

---

如果性能是一个问题，那么你就不应该首先使用unordered_map。 - The Paramagnetic Croissant

@TheParamagneticCroissant unordered_map 存在的主要原因就是为了提供比有序映射更好的性能优势。 - David Schwartz

@DavidSchwartz 在这种情况下它因其可怕的为每个节点分配内存的本质（更不用说高速缓存局部性了...）而无助地失败。使用开放定址法在C++中编写哈希表几乎是微不足道的，可以获得比“unordered_map”快3-4-5-10倍的性能。 - The Paramagnetic Croissant

对于几乎所有的C++集合，你都可以说它几乎不可能是最佳解决方案。但是有很多现实世界的问题，它已经足够好了。 - David Schwartz

@DavidSchwartz 是的，没错。我并没有反对。我自己经常使用 unordered_map。我只是断言，在这些情况下，性能意识的微调并不重要。 - The Paramagnetic Croissant

Answer 3

有一些算法需要将对象哈希到一些桶中，然后处理每个桶。

比如说，你想在一个集合中查找重复项。你将集合中的所有项进行哈希，然后在每个桶中逐对比较项。

再举一个不太琐碎的例子是用于查找频繁项集的Apriori算法。

- Anton Savin

Answer 4

我曾经需要使用接口的唯一原因是在不必持有地图锁或复制地图的情况下遍历地图中的所有对象。这可用于对地图中的对象进行不精确的过期检查或其他类型的定期检查。

遍历工作如下：

1. 锁定地图。 2. 按桶顺序开始遍历地图，操作遇到的每个对象。 3. 当您认为已经持有锁太长时间时，请隐藏您最后操作的对象的键。 4. 等待您希望恢复操作的时候。 5. 锁定地图，并从步骤2开始，从您停止的键（按桶顺序）开始或附近开始。如果到达末尾，请从头开始。

- David Schwartz