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

Question

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

假设我们正在通过迭代器迭代哈希表，在迭代过程中插入一个元素，并且该插入导致全部或部分表重新哈希。我正在寻找允许继续迭代的哈希表变体，并确保所有元素都被访问(除了新插入的元素，这无关紧要)并且没有元素被访问两次。

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

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

Answer 1

AFAIK C++ unordered_map invalidates iterators during rehash.

正确。 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() 在开始迭代/插入之前，避免重新散列
• 将要插入的元素存储在 vector 中在迭代期间，然后将它们移动到 unordered_map 中之后
• 创建例如vector<T*>或 vector<reference_wrapper<T>>对于元素，迭代它而不是 unordered_map , 但仍然在 unordered_map 中插入

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