我没有读过 C++ 标准，但这就是我认为 c++ 的 unordered_map 应该工作的方式。
- 在堆中分配一个内存块。
- 对于每个放置请求，散列对象并将其映射到该内存中的一个空间
- 在此过程中，通过链接或开放寻址处理冲突处理..
我很惊讶我找不到太多关于 unordered_map 如何处理内存的信息。 unordered_map 分配的内存是否有特定的初始大小。如果假设我们分配了 50 个 int 内存并最终插入了 5000 个整数，会发生什么情况？
这会发生很多冲突，所以我相信应该有一种类似于重新散列和重新调整大小的算法，以在达到一定级别的冲突阈值后减少冲突次数。由于它们是作为成员函数显式提供给类的，因此我假设它们也在内部使用。有这样的机制吗？
最佳答案
With every put request, hash the object and map it to a space in this memory
不幸的是，这并不完全正确。您指的是 开放寻址 或 封闭散列 数据结构，这不是 unordered_map 的指定方式。
每个 unordered_map 实现都将链表存储到桶数组中的外部节点。这意味着插入一个项目将始终至少分配一次(新节点)如果不是两次(调整桶数组的大小，然后是新节点)。
不，这根本不是实现最常见用途的 HashMap 的最有效方法。不幸的是，unordered_map 规范中的一个小“疏忽”几乎需要这种行为。所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效。因为插入可能会导致桶数组增长(重新分配)，所以通常不可能有一个迭代器直接指向桶数组并满足稳定性保证。
unordered_map 是一种更好的数据结构，如果您将复制成本高昂的项目存储为您的键或值。这是有道理的，因为它的总体设计是从 Boost 的移动前语义设计中提取的。
Chandler Carruth(谷歌)在他的 CppCon '14 演讲中提到了这个问题 "Efficiency with Algorithms, Performance with Data Structures" .
关于c++ unordered_map 冲突处理、调整大小和重新散列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31098123/