C++ unordered_map 碰撞处理、调整大小和重新哈希
这是我之前提出的问题，我发现我对unordered_map的实现方式很困惑。我相信许多人和我一样也感到困惑。根据我所知道的信息，未读取标准：
每个unordered_map实现都在桶数组中存储指向外部节点的链表...不，这绝不是实现哈希映射的大多数常见用途的最有效方法。不幸的是，在unordered_map规范中有一个小的“疏忽”，几乎要求这种行为。所需的行为是：插入或删除其他元素时迭代器必须保持有效。
我希望有人可以解释实现方式以及它如何符合C++标准定义（就性能要求而言），如果它真的不是实现哈希映射数据结构的最有效方法，该如何改进？
该标准有效地要求实现 std::unordered_set 和 std::unordered_map，以及它们的“multi”版本，使用 开链法(也称为分离链接)，这意味着一个桶数组，每个桶都持有一个指向链接列表头部的指针. 这一要求很微妙：它是以下结果的必然:
max_load_factor() 为1.0（这意味着每当 size() 超过 1.0 倍的 bucket_count()时，表格将重新调整大小），和如果不使用开链法，那么将无法实现这一点，因为与哈希表的另一主要实现类别 - 闭链法(也称为开放地址法) - 相比，当 load_factor()](https://en.cppreference.com/w/cpp/container/unordered_map/load_factor) 接近 1 时，冲突变得无法控制。
参考资料：
23.2.5/15: 如果 (N+n) < z * B，其中 N 是插入操作之前容器中元素的数量，n 是插入的元素数量，B 是容器的桶数，z 是容器的最大负载因子，则 insert 和 emplace 成员将不会影响迭代器的有效性。
在 23.5.4.2/1 的构造函数的 Effects 中： max_load_factor() 返回 1.0。
关于你引用的文本：
不，对于大多数常见用途来说，这不是实现哈希映射的最有效方法。不幸的是，无序映射规范中的一个小“疏忽”几乎要求这种行为。所需行为是，当插入或删除其他元素时，对元素的迭代器必须保持有效。
这并不是一个“疏忽”... 这是非常有意识地进行的，并且是在完全意识到后果的情况下进行的。虽然可以做出其他妥协，但开放式哈希/链接方法是一种合理的妥协，适用于一般用途，可以相当优雅地处理来自中等哈希函数的冲突，并且对于小型或大型键/值类型不会太浪费，并且可以处理任意数量的 insert/erase 对而不会逐渐降低性能，就像许多闭合式哈希实现那样。
从Matthew Austern 提出的建议中可以看到，这一点是有意考虑到了的：
为了提供最佳的迭代而不需要通过任何空桶，GCC 的实现将桶填充为指向所有值的单个单向链接列表中的迭代器：这些迭代器指向该桶元素之前的元素，因此如果删除桶的最后一个值，则可以重新连接那里的
next指针。
我不知道是否有一种令人满意的通用框架实现了开放地址法。开放地址法存在许多问题：
• 必须区分空位置和占用位置。
• 必须将哈希表限制为具有默认构造函数的类型，并提前构造每个数组元素，或者维护一些元素是对象而其他元素是原始内存的数组。
• 开放地址法使得冲突管理变得困难：如果要插入一个哈希码映射到已占用位置的元素，则需要一种策略告诉您下一个尝试的位置。这是一个解决的问题，但已知的最佳方案非常复杂。
• 当允许擦除元素时，冲突管理尤其复杂。（见Knuth进行讨论）。标准库的容器类应该允许擦除。
• 开放地址法的冲突管理方案往往假定固定大小的数组可以容纳最多N个元素。标准库的容器类应能够在插入新元素时根据需要增长，直到可用内存的限制。
解决这些问题可能是一个有趣的研究项目，但在C++上下文中缺乏实现经验的情况下，标准化开放地址容器类是不合适的。
对于只插入表格、数据小到足以直接存储在桶中、有一个方便的未使用桶的哨兵值和良好的哈希函数，闭散列方法可能快大约一个数量级并且使用的内存显著减少，但这不是通用的。
完整比较和阐述哈希表设计选项及其影响超出了S.O.的范围，因为它太广泛，无法在此适当地处理。