algorithm - 哈希表重新散列和迭代器失效

Question

有哪些已知技术可以防止迭代器在重新散列之后/期间失效？特别是，我对具有增量重新散列的冲突链哈希表感兴趣。

假设我们正在通过迭代器迭代哈希表，在迭代期间插入一个元素，并且该插入导致完整或部分表重新哈希。我正在寻找允许继续迭代并确保所有元素都被访问的哈希表变体（可能除了新插入的元素，没关系）并且没有元素被访问两次。

AFAIK C++ unordered_map 在重新散列期间使迭代器无效。此外，AFAIK Go 的地图具有增量重新散列并且不会使迭代器无效（范围循环状态），所以它可能是我正在寻找的，但到目前为止我还不能完全理解源代码。

一种可能的解决方案是有一个所有元素的双向链表，与散列表平行，不受重新散列的影响。此解决方案需要每个元素两个额外的指针。我觉得应该存在更好的解决方案。

标签： algorithmgodata-structureshashmaphashtable

Answer 1

AFAIK C++unordered_map在重新散列期间使迭代器无效。

正确的。cppreference.com 总结了unordered_map迭代器失效：

Operations                                     Invalidated
==========                                     ===========
All read only operations, swap, std::swap      Never
clear, rehash, reserve, operator=              Always
insert, emplace, emplace_hint, operator[]      Only if causes rehash
erase                                          Only to the element erased 

如果你想使用unordered_map，你的选择是：

• reserve()在开始迭代/插入之前调用，以避免重新散列
• max_load_factor()在开始迭代/插入之前进行更改，以避免重新散列
• 在迭代期间将要插入的元素存储在 avector中，然后将它们移动到unordered_map之后
• 创建 egvector<T*>或vector<reference_wrapper<T>>到元素，迭代它而不是unordered_map，但仍然插入到unordered_map

如果你真的想要增量重新散列，你可以编写一个包装两个unordered_maps 的类，当你看到一个会导致第一个映射重新散列的插入时，你开始插入第二个（为此你会保留两倍的大小第一张地图）。您可以手动控制第一个地图中的所有元素何时转移到第二个地图，或者让它作为某些其他操作的副作用发生（例如，每次插入新元素时迁移一个元素）。这种包装方法比从头开始编写增量重新散列表要容易得多。