怎样的std :: unordered_map实现

Question

c++ unordered_map collision handling , resize and rehash

这是我开了一个以前的问题，我已经看到，我有一个关于如何unordered_map实现很多混乱。我相信很多其他人也与我混淆。在我知道的信息基础没有阅读的标准：

每unordered_map实现存储链表外部 节点桶的阵列中......不，那是不是所有的最 有效的方式来为大多数常见用途实施哈希映射。 不幸的是， unordered_map规范中的一个小“监督”都需要这种行为。所需的行为是 是迭代器的元素插入或删除其他 元素

我希望有人可以解释的实施以及何时必须保持有效的它是如何对应于C++标准清晰度（在性能方面的要求）并且如果它实际上不是实现散列映射数据结构的最有效方式，它可以如何改进？

Answer 1

该标准有效强制要求使用开放散列的std::unordered_set和std::unordered_map实现，这意味着一个存储桶阵列，每个存储桶都包含一个逻辑（通常是实际的）列表的头部。这个要求是微妙的：这是默认最大负载因子为1.0的结果，并且保证了表格不会被重新生成，除非生长超过该负载因子：如果没有链接，这将是不切实际的，因为与封闭哈希的碰撞变得压倒性的负载因数接近1：

23.2.5/15：本insert和emplace成员不应影响迭代器的有效性，如果(N+n) < z * B，其中N是在之前的插入操作的容器中的元素的数量，n是插入元素的数量，B是容器的桶数，z是容器的最大负载因子。

当中效果在23.5.4.2/1构造函数：max_load_factor()返回1.0。

（允许最佳的迭代，而不越过任何空水桶，GCC的实现充满迭代器来保存所有值水桶到一个单一的单链表：迭代器指向元素立即铲斗的元素之前，所以接下来的指针也可以，如果删除桶的最后的值进行布线）

关于你引用的文字：

不，这不是在所有实施最常见的一个哈希表的最有效方法使用。不幸的是，unordered_map规范中的一个小“监督”都需要这种行为。所需的行为是，在插入或删除其他元素时，元素的迭代器必须保持有效。

没有“监督”......所做的事情非常慎重，完全意识到。诚然，其他妥协可能已经触及，但开放散列/链接方法是一般用途的合理折衷方案，优雅地适应平庸散列函数的冲突，对于小型或大型键/值类型并不太浪费，并且可以处理任意很多对，而不会像许多封闭散列实现那样逐渐降低性能。

随着意识的证据，从Matthew Austern's proposal here：

我不知道任何令人满意的实现开一个通用框架解决的。开放寻址存在若干问题：

•有必要区分空置位置和占用位置。

•有必要将哈希表限制为具有默认构造函数的类型，并提前构造每个数组元素，否则需要维护一个元素的对象，其中一些元素是原始内存。

•开放寻址使得碰撞管理变得困难：如果要插入哈希码映射到已占用位置的元素，则需要一个策略，告诉您下一步尝试的位置。这是一个解决的问题，但最有名的解决方案很复杂。

•当允许擦除元素时，碰撞管理特别复杂。 （请参阅Knuth进行讨论。）标准库的容器类应允许擦除。

•用于开放寻址的碰撞管理方案倾向于假定固定大小的阵列可容纳N个元素。当插入新元素时，标准库的容器类应该能够根据需要增长，直到可用内存的限制。

解决这些问题可能是一个有趣的研究项目，但是，由于缺乏C++环境下的实施经验，标准化开放寻址容器类将是不恰当的。

具体地，对于与数据小到足以直接存储在桶中，未使用的铲斗一个方便的标记值，以及良好的散列函数仅嵌件表，一个封闭的散列方法可以大致一个数量级更快使用大大减少内存，但这不是通用目的。

哈希表设计选项及其含义的全面比较和阐述是S.O.的主题。因为它太宽泛，无法在这里正确处理。