C++无序映射冲突处理、调整大小和重新哈希

Question

C++无序映射冲突处理、调整大小和重新哈希

17

虽然我没有阅读 C++ 标准，但我认为 C++ 的 unordered_map 应该是这样工作的：

在堆中分配一块内存。
每次 put 请求时，对对象进行哈希并将其映射到此内存的某个空间。
在此过程中，通过链接或开放地址法处理冲突。

我很惊讶我没有找到太多关于 unordered_map 如何处理内存的资料。unordered_map 分配的内存有特定的初始大小吗？如果我们分配了 50 个 int 内存，却需要插入 5000 个整数会发生什么？这将导致大量冲突，因此我相信应该有某种重新哈希和调整大小的算法，在达到一定的冲突阈值后降低碰撞次数。由于它们作为类的成员函数被明确提供，我认为它们也被用于内部。是否存在这样的机制呢?

- ralzaul

3个回答

2

在堆中分配一个内存块。

错误 - 这里有一个用于“bucket”数组的内存块，在GCC的情况下，它们实际上是迭代器，能够记录前向链接列表中的位置。

对于每个put请求，将对象进行哈希处理，并将其映射到该内存中的一个空间。

不是的...当你将更多项目插入/嵌入列表时，会进行额外的动态（即堆）分配，为节点的next链接和要插入/嵌入的值提供空间。链接列表相应地进行了重连，因此新插入的元素与哈希到同一桶的其他元素链接，并且如果其他桶也有元素，则该组将链接到那些元素的节点。

在某些情况下，哈希表内容可能看起来像这样（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()；该桶将需要存储一个迭代器，指向单链表元素，其紧挨着哈希到该桶的第一个元素之前，以便它可以从桶中删除最后一个元素，并重新连接头部或另一个桶的下一个指针，以跳过已擦除的元素。

虽然桶内的元素需要在前向链接列表中连续，但是桶的排序顺序不重要，这是容器中插入元素顺序的无关后果，并未在标准中规定。

在此过程中，通过链接或开放寻址处理冲突。标准库容器使用分离链接实现哈希表。

我很惊讶地发现关于unordered_map如何处理内存的资料不多。unordered_map分配的内存有特定的初始大小吗？

不，C++标准没有规定初始内存分配应该是什么，这由C++实现来选择。您可以通过打印.bucket_count()来查看新创建的表有多少个桶，很可能如果您将其乘以指针大小，您将得到无序容器所做的堆分配的大小：myUnorderedContainer.bucket_count() * sizeof(int*)。尽管如此，标准库实现对初始bucket_count()进行任意和奇怪的变化（例如，根据键类型进行优化级别），但我想象不出为什么会这样做。

如果我们分配了50个int内存，而我们最终插入了5000个整数会发生什么？这将导致很多冲突，因此我认为应该有一种重新哈希和重新调整大小的算法，在达到一定的冲突阈值后降低冲突数量。

重新散列/调整大小不是由一定数量的冲突触发的，而是由冲突易感性触发的，这是通过负载因子来衡量的，即 .size() / .bucket_count()。

当插入操作将 .load_factor() 推高到 .max_load_factor() 以上时，哈希表会被调整大小。这实际上意味着它分配了更多的桶 - 通常接近但不一定完全是两倍 - 然后将新的桶指向链表节点，最后删除旧桶的堆分配。

由于它们明确地作为类的成员函数提供，我认为它们也会在内部使用。是否存在这样的机制？

关于如何实现重新调整大小，没有C++标准的要求。话虽如此，如果我要实现resize()函数，我会考虑创建一个函数局部容器，同时指定新的bucket_count，然后遍历*this对象中的元素，调用extract()将它们分离，然后调用merge()将它们添加到函数局部容器对象中，最后调用swap()交换*this和函数局部容器。

- Tony Delroy

2

std::unordered_map包含了一个负载因子，用来管理它的内部桶(bucket)的大小。std::unordered_map使用这个奇怪的因子来保持容器的大小在0.0和1.0之间。这样可以减少桶(bucket)中碰撞的可能性。在此之后，我不确定它们是否会回退到桶(bucket)内的线性探测(linear probing)，但我认为应该是这样。

- kevr

默认的最大负载因子实际上是 1.0，而实际负载因子通常在表重新调整大小后再次增长时在 ~0.5 和 1.0 之间波动。是的 - 在冲突元素中进行线性搜索。 - Tony Delroy

谢谢，Tony D. 已更新。 - kevr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sean Middleditch · Accepted Answer

每次put请求时，将对象哈希并映射到内存中的一个空间。很遗憾，这不是完全正确的。您正在引用一种开放寻址或闭合哈希数据结构，这不是unordered_map的规定方式。每个unordered_map实现在桶数组中存储指向外部节点的链接列表。这意味着插入项目始终至少会分配一次（新节点），如果需要则会分配两次（调整桶数组大小，然后是新节点）。对于大多数常见用途来说，这并不是实现哈希映射表最有效的方法。不幸的是，在unordered_map的规范中存在一个小的“疏忽”，几乎要求此行为。所需的行为是，在插入或删除其他元素时，元素的迭代器必须保持有效。因为插入可能导致桶数组增长（重新分配），所以通常无法直接将迭代器指向桶数组并满足稳定性保证。如果您将昂贵的副本作为键或值存储，则unordered_map是更好的数据结构。鉴于其设计通常来自于移动语义之前的Boost设计，这是有道理的。

Chandler Carruth(谷歌)在他的CppCon'14演讲"算法效率，数据结构性能"中提到了这个问题。