c++ unordered_map 碰撞处理，调整大小和重新散列
c++ unordered_map collision handling , resize and rehash
我没有读过 C++ 标准，但这就是我认为 c++ 的 unordered_map 应该工作的方式。
- 在堆中分配一个内存块。
- 对于每个放置请求，散列对象并将其映射到此内存中的 space
- 在此过程中，通过链接或开放寻址处理冲突处理..
我很惊讶我找不到太多关于 unordered_map 如何处理内存的信息。是否有 unordered_map 分配的特定初始内存大小。如果假设我们分配了 50 个 int 内存并且我们最终插入了 5000 个整数会怎样？
这会发生很多冲突，所以我相信应该有一种类似于重新散列和调整大小的算法，以在达到一定程度的冲突阈值后减少冲突次数。由于它们作为成员函数明确提供给 class，我假设它们也在内部使用。有没有这样的机制？
std::unordered_map 包含一个负载因子，用于管理其内部桶的大小。 std::unordered_map 使用这个奇数因子将容器的大小保持在 0.0 和 1.0 因子之间。这降低了桶中发生碰撞的可能性。在那之后，我不确定他们是否回退到发现碰撞的桶内的线性探测，但我假设是这样。
With every put request, hash the object and map it to a space in this memory
不幸的是，事实并非如此。您指的是 开放寻址 或 封闭散列 数据结构，这不是 unordered_map 的指定方式。
每个 unordered_map 实现都将链表存储到存储桶数组中的外部节点。这意味着插入一个项目将始终分配至少一次（新节点）如果不是两次（调整桶数组的大小，然后是新节点）。
不，这根本不是实现最常见用途的哈希映射的最有效方法。不幸的是，unordered_map 规范中的一个小 "oversight" 几乎需要这种行为。所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效。因为插入可能会导致桶数组增长（重新分配），所以通常不可能有一个迭代器直接指向桶数组并满足稳定性保证。
unordered_map 如果您将复制成本高的项目存储为键或值，则它是一种更好的数据结构。这是有道理的，因为它的总体设计是从 Boost 的移动前语义设计中提取出来的。
Chandler Carruth (Google) 在他的 CppCon '14 演讲中提到了这个问题 "Efficiency with Algorithms, Performance with Data Structures"。
Allocate a memory block in the heap.
正确 - 有一个内存块用于“桶”数组，在 GCC 的情况下，它实际上是迭代器，能够在前向linked 列表中记录一个位置。
With every put request, hash the object and map it to a space in this memory
不...当您 insert/emplace 将更多项目添加到列表中时，将使用 space 为节点的 next [=85= 完成额外的动态（即堆）分配]，值为 inserted/emplaced。 linked 列表相应地重新连接，因此新插入的元素从散列到同一桶的其他元素 linked 到 and/or，如果其他桶也有元素，则组将从这些元素的节点 linked 到 and/or。
在某些时候，散列 table 内容 可能 看起来像这样（GCC 以这种方式做事，但可以做一些更简单的事情）：
+-------> head
/ |
bucket# / #503
[0]----\/ |
[1] /\ /===> #1003
[2]===/==\====/ |
[3]--/ \ /==> #22
[4] \ / |
[5] \ / #7
[6] \ |
[7]=========/ \-----> #177
[8] |
[9] #100
左边的桶是原始分配的数组：图示数组中有10个元素，所以“bucket_count()”== 10。
具有散列值 X 的密钥 - 表示为 #x，例如#177 - 散列到桶 X % bucket_count()；该桶需要将迭代器存储到单linked 列表元素紧接第一个元素散列到该桶之前，因此它可以从桶中删除最后一个元素并重新连接 head 或另一个桶的下一个指针，以跳过已删除的元素。
虽然桶中的元素在前向linked列表中需要连续，但该列表中桶的排序是元素插入顺序的不重要结果容器，标准中没有规定。
During this process handle collision handling via chaining or open addressing..
由散列 table 支持的标准库容器始终使用 单独链接 。
I am quite surprised that I could not find much about how the memory is handled by unordered_map. Is there a specific initial size of memory which unordered_map allocates.
不，C++ 标准没有规定初始内存分配应该是什么；由 C++ 实现来选择。你可以通过打印出 .bucket_count() 来查看新创建的 table 有多少个桶，如果你将它乘以你的指针大小，你很可能会得到无序堆分配的大小制作的容器：myUnorderedContainer.bucket_count() * sizeof(int*)。也就是说，没有禁止您的标准库实现以任意和奇怪的方式改变初始 bucket_count()（例如，优化级别，取决于密钥类型），但我无法想象为什么会这样。
What happens if lets say we allocated 50 int memory and we ended up
inserting 5000 integer? This will be lot of collisions so I believe there should be kind of like a re-hashing and re-sizing algorithm to decrease the number of collisions after a certain level of collision threshold is reached.
Rehashing/resizing 不是由一定数量的碰撞触发，而是由 负载因子 衡量的特定 碰撞倾向 ，也就是 .size() / .bucket_count().
当插入将推送 .load_factor() above the .max_load_factor() 时，您可以更改但 C++ 标准要求默认为 1.0，然后调整散列 table 的大小。这实际上意味着它分配了更多的桶——通常在接近但不一定正好两倍的地方——然后它将新桶指向 linked 列表节点，然后最后删除旧桶的堆分配。
Since they are explicitly provided as member functions to the class, I assume they are used internally as well. Is there a such mechanism?
C++ 标准没有关于如何实现大小调整的要求。也就是说，如果我要实现 resize()，我会考虑创建一个函数局部容器，同时指定新需要的 bucket_count，然后遍历 *this 对象中的元素，调用 extract() to detach them, then merge() 将它们添加到函数本地容器对象，然后最终在 *this 和函数本地容器上调用交换。
我没有读过 C++ 标准，但这就是我认为 c++ 的 unordered_map 应该工作的方式。
- 在堆中分配一个内存块。
- 对于每个放置请求，散列对象并将其映射到此内存中的 space
- 在此过程中，通过链接或开放寻址处理冲突处理..
我很惊讶我找不到太多关于 unordered_map 如何处理内存的信息。是否有 unordered_map 分配的特定初始内存大小。如果假设我们分配了 50 个 int 内存并且我们最终插入了 5000 个整数会怎样？
这会发生很多冲突，所以我相信应该有一种类似于重新散列和调整大小的算法，以在达到一定程度的冲突阈值后减少冲突次数。由于它们作为成员函数明确提供给 class，我假设它们也在内部使用。有没有这样的机制？
std::unordered_map 包含一个负载因子，用于管理其内部桶的大小。 std::unordered_map 使用这个奇数因子将容器的大小保持在 0.0 和 1.0 因子之间。这降低了桶中发生碰撞的可能性。在那之后，我不确定他们是否回退到发现碰撞的桶内的线性探测，但我假设是这样。
With every put request, hash the object and map it to a space in this memory
不幸的是，事实并非如此。您指的是 开放寻址 或 封闭散列 数据结构，这不是 unordered_map 的指定方式。
每个 unordered_map 实现都将链表存储到存储桶数组中的外部节点。这意味着插入一个项目将始终分配至少一次（新节点）如果不是两次（调整桶数组的大小，然后是新节点）。
不，这根本不是实现最常见用途的哈希映射的最有效方法。不幸的是，unordered_map 规范中的一个小 "oversight" 几乎需要这种行为。所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效。因为插入可能会导致桶数组增长（重新分配），所以通常不可能有一个迭代器直接指向桶数组并满足稳定性保证。
unordered_map 如果您将复制成本高的项目存储为键或值，则它是一种更好的数据结构。这是有道理的，因为它的总体设计是从 Boost 的移动前语义设计中提取出来的。
Chandler Carruth (Google) 在他的 CppCon '14 演讲中提到了这个问题 "Efficiency with Algorithms, Performance with Data Structures"。
Allocate a memory block in the heap.
正确 - 有一个内存块用于“桶”数组，在 GCC 的情况下，它实际上是迭代器，能够在前向linked 列表中记录一个位置。
With every put request, hash the object and map it to a space in this memory
不...当您 insert/emplace 将更多项目添加到列表中时，将使用 space 为节点的 next [=85= 完成额外的动态（即堆）分配]，值为 inserted/emplaced。 linked 列表相应地重新连接，因此新插入的元素从散列到同一桶的其他元素 linked 到 and/or，如果其他桶也有元素，则组将从这些元素的节点 linked 到 and/or。
在某些时候，散列 table 内容 可能 看起来像这样（GCC 以这种方式做事，但可以做一些更简单的事情）：
+-------> head
/ |
bucket# / #503
[0]----\/ |
[1] /\ /===> #1003
[2]===/==\====/ |
[3]--/ \ /==> #22
[4] \ / |
[5] \ / #7
[6] \ |
[7]=========/ \-----> #177
[8] |
[9] #100
左边的桶是原始分配的数组：图示数组中有10个元素，所以“bucket_count()”== 10。
具有散列值
X的密钥 - 表示为#x，例如#177- 散列到桶X % bucket_count()；该桶需要将迭代器存储到单linked 列表元素紧接第一个元素散列到该桶之前，因此它可以从桶中删除最后一个元素并重新连接 head 或另一个桶的下一个指针，以跳过已删除的元素。虽然桶中的元素在前向linked列表中需要连续，但该列表中桶的排序是元素插入顺序的不重要结果容器，标准中没有规定。
During this process handle collision handling via chaining or open addressing..
由散列 table 支持的标准库容器始终使用 单独链接 。
I am quite surprised that I could not find much about how the memory is handled by unordered_map. Is there a specific initial size of memory which unordered_map allocates.
不，C++ 标准没有规定初始内存分配应该是什么；由 C++ 实现来选择。你可以通过打印出 .bucket_count() 来查看新创建的 table 有多少个桶，如果你将它乘以你的指针大小，你很可能会得到无序堆分配的大小制作的容器：myUnorderedContainer.bucket_count() * sizeof(int*)。也就是说，没有禁止您的标准库实现以任意和奇怪的方式改变初始 bucket_count()（例如，优化级别，取决于密钥类型），但我无法想象为什么会这样。
What happens if lets say we allocated 50 int memory and we ended up inserting 5000 integer? This will be lot of collisions so I believe there should be kind of like a re-hashing and re-sizing algorithm to decrease the number of collisions after a certain level of collision threshold is reached.
Rehashing/resizing 不是由一定数量的碰撞触发，而是由 负载因子 衡量的特定 碰撞倾向 ，也就是 .size() / .bucket_count().
当插入将推送 .load_factor() above the .max_load_factor() 时，您可以更改但 C++ 标准要求默认为 1.0，然后调整散列 table 的大小。这实际上意味着它分配了更多的桶——通常在接近但不一定正好两倍的地方——然后它将新桶指向 linked 列表节点，然后最后删除旧桶的堆分配。
Since they are explicitly provided as member functions to the class, I assume they are used internally as well. Is there a such mechanism?
C++ 标准没有关于如何实现大小调整的要求。也就是说，如果我要实现 resize()，我会考虑创建一个函数局部容器，同时指定新需要的 bucket_count，然后遍历 *this 对象中的元素，调用 extract() to detach them, then merge() 将它们添加到函数本地容器对象，然后最终在 *this 和函数本地容器上调用交换。