如何实现std :: unordered_map

Question

c ++ unordered_map碰撞处理,调整大小和重新散列

这是我之前提出的一个问题,我看到我对unordered_map的实现方式感到很困惑.我相信很多其他人都会和我分享这种困惑.基于我所知道的信息而不阅读标准:

每个unordered_map实现都将链表存储到存储桶数组中的外部节点...不,这对于实现最常见用途的哈希映射来说并不是最有效的方法.不幸的是,unordered_map规范中的一个小"疏忽"都需要这种行为.所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效

我希望有人可以解释实现以及它如何与c ++标准定义(在性能要求方面)相对应,以及它是否真的不是实现哈希映射数据结构的最有效方法如何改进它？

Answer 1

标准有效地强制要求std::unordered_set和std::unordered_map使用开放散列的实现,这意味着一个桶阵列,每个桶都包含一个逻辑(通常是实际)列表的头部.这个要求是微妙的:它是默认最大载荷因子为1.0的结果,并且保证除非增长超过该载荷因子,否则表不会被重新加载:如果没有链接则这是不切实际的,因为与封闭散列的碰撞变得势不可挡,因为负载系数接近1:

23.2.5/15:的insert和emplace成员不应影响迭代器的有效性,如果(N+n) < z * B,在这里N是在之前的插入操作的容器中的元素的数量,n是插入的元素的数量,B是容器的桶计数,并且z是容器的最大载荷系数.

在23.5.4.2/1的构造函数的效果中:max_load_factor()返回1.0.

(为了允许最佳迭代而不通过任何空桶,GCC的实现将带有迭代器的桶填充到一个包含所有值的单个链接列表中:迭代器指向紧靠该桶元素之前的元素,因此下一个指针可以是如果删除桶的最后一个值,则重新连接.)

关于你引用的文字:

不,这对于实现最常见用途的哈希映射来说并不是最有效的方法.不幸的是,unordered_map规范中的一个小"疏忽"都需要这种行为.所需的行为是元素的迭代器在插入或删除其他元素时必须保持有效

没有"监督"......所做的是非常慎重的,并且充分意识到了.确实可以实现其他妥协,但开放式散列/链接方法对于一般用途来说是一种合理的折衷方案,它可以合理地优雅地处理来自普通哈希函数的冲突,对于小型或大型键/值类型来说并不是太浪费,并且处理任意多个insert/ erase对,而不会像许多封闭的哈希实现那样逐渐降低性能.

作为意识的证据,来自Matthew Austern的建议:

我不知道在通用框架中有任何令人满意的开放式寻址实现.开放式寻址存在许多问题:

•有必要区分空置位置和占用位置.

•有必要将哈希表限制为具有默认构造函数的类型,并提前构造每个数组元素,或者维护一个数组,其中某些元素是对象,其他元素是原始内存.

•开放式寻址使冲突管理变得困难:如果您要插入其哈希码映射到已占用位置的元素,则需要一个策略来告诉您下一步尝试的位置.这是一个已解决的问题,但最着名的解决方案很复杂.

•允许删除元素时,冲突管理尤其复杂.(请参阅Knuth进行讨论.)标准库的容器类应该允许擦除.

•开放寻址的冲突管理方案倾向于采用固定大小的阵列,最多可容纳N个元素.插入新元素时,标准库的容器类应该能够根据需要增长,直到可用内存的限制.

解决这些问题可能是一个有趣的研究项目,但是,由于缺乏C++环境下的实现经验,标准化开放寻址容器类是不合适的.

特别是对于只有插入的表,其数据足够小以便直接存储在存储桶中,未使用的存储桶的方便的标记值,以及良好的散列函数,封闭的散列方法可能大约快一个数量级,并且使用的内存大大减少,但是这不是一般目的.

散列表设计选项及其含义的完整比较和详细说明是SO的主题,因为它太宽泛而无法在此处正确解决.