为什么C++11/Boost的`unordered_map`在删除元素时不会重新哈希？

Question

我想知道为什么C++11和Boost的哈希表在迭代删除元素时不会进行调整大小。即使这不是技术上的内存泄漏，我认为它可能是应用程序中的严重问题（对我来说是一个隐藏的问题，很难追踪回去），并且实际上可能影响许多应用程序。这是容器的“设计缺陷”吗？

我进行了基准测试，似乎影响了几个编译器版本（包括VS、Clang、GCC）。

复现此问题的代码如下：

std::unordered_map<T1,T2> m;

for (int i = 0; i < 5000000; i++)
        m.insert(std::make_pair(i, new data_type));


for (map_type::iterator it = m.begin(); it != m.end();) {
        delete it->second;
        it = m.erase(it);
}   

我创建了一个自包含测试文件，使用自定义分配器来跟踪内存使用情况。

据我所知，这样做的原因是允许在迭代过程中擦除元素并保持有效的迭代器以不被擦除的元素。这似乎是一个有点奇怪的要求，因为插入元素可能会导致重新哈希，从而使迭代器无效。

但是你可以直接销毁映射表。

这就是我解决这个问题的方式（我将映射表包装在智能指针中，当它为空时，我只需重新创建一个新的空映射表，结果比重新哈希更快，不知道为什么）。

一般来说，任何使用unordered_map作为缓存元素容器的应用程序都可能遇到这个问题（您可能想从缓存中删除元素，但通常没有人执行“缓存重置”）。

- CoffeDeveloper

---

我认为你已经正确回答了自己的问题，只是不同意理由。这里有一个包含设计理念的提案链接：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html - Howard Hinnant

看起来很明显的原因是为了避免使任何其他迭代器无效。此外，如果你正在使用erase作为实际上的clear（希望获得shrink_to_size的效果），那么就要明确地编写代码。即使在这种情况下保持相同的大小也有价值，如果哈希表反复使用并且最终的人口密度具有相同类型的桶负载，则重用比重新开始增长更有效。 - sehe

部分原因与 vector 在擦除时不重新分配的原因相同。 - sbabbi

一些人认为std::unordered_map规范过于详细，这意味着std实现者无法很大程度上改变其工作方式。据我所知，编写了一个示例实现，然后根据其操作行为制定了抽象需求...... - Yakk - Adam Nevraumont

抱歉打扰您，但我仍然有些疑问。您是否担心内存占用，因为您有一些地图，它们有时非常大（以元素计数为单位），但大多数时间很小？还是您担心性能？因为在您的特定示例中，定期重新哈希会慢得多，并且至少平均而言会消耗更多的内存带宽。 - MikeMB

Answer 1

据我所知，这种行为不是因为需要避免使迭代器失效（std::unordered_map::rehash也不会使它们失效），而是由于对std::unordered_map::erase的复杂度要求，其平均时间应该是常数。

我不知道为什么会被规定成这样，但我可以告诉你，为什么这对我来说是正确的默认行为：

1. 在许多应用程序中，我的哈希表的内容在初始化后基本上是不变的 - 所以这里我不关心。 2. 在这种情况下，至少平均元素数量保持更或多或少相同（在数量级内）。因此，即使某个时刻删除了很多对象，新元素很可能很快就会被添加。在这种情况下，它实际上不会减少内存占用，并且重新散列两次（一次在删除后，一次在添加新元素后）的开销通常会超过我通过更紧凑的表格获得的任何性能提升。 3. 如果您无法控制启发式方法（例如通过修改max_load_factor插入元素时），则通过筛选函数删除大量元素将受到中间重新散列的严重减速。因此，即使在那些实际上有益于重新散列的情况下，我通常也可以做出更好的决策，例如何时进行重新散列或复制和交换，而不是std::unordere_map中的通用启发式方法。

总之，这些观点适用于我的典型用例，我并不声称它们对其他人的软件普遍适用，也不声称它们是规范unordered_map背后的动机。

有趣的是，VS2015和libstc++似乎以不同的方式实现了rehash(0)：

- libstc++将实际缩小（重新分配）存储表的内存。 - VS2015会减少表的大小（也就是桶数），但不会重新分配表。因此，即使在重新散列空哈希映射后，表格的多余内存也不会被返回。

显然，最小化内存占用的唯一可移植方法是复制和交换。

关于文档，我同意可能应该在某个地方明确提到这一点，但另一方面，它与std::vector::erase()的文档相一致。此外，我不确定是否真的不可能编写一个在删除时至少有时重新散列的实现，而不违反要求。

- MikeMB

---

感谢您的时间，是的，默认行为非常合理，似乎VS2015有些bug？唯一释放内存的方法是销毁地图P_P。 - CoffeDeveloper

@DarioOO：它的优点在于需要较少的动态内存分配。是否做出了正确的选择当然是有争议的，特别是如果元素复制起来很昂贵。 - MikeMB