如何实现std :: unordered_map

Question

这是我之前提出的一个问题，我发现我对如何实现unordered_map感到困惑。我敢肯定，其他许多人也会与我混淆。根据我不阅读标准而知道的信息：

每个unordered_map实现都将一个链接列表存储到存储桶数组中的外部节点上……不，这根本不是最通用的实现哈希映射的最有效方法。不幸的是，unordered_map规范中的一个小“疏忽”几乎都需要这种行为。必需的行为是，元素的迭代器在插入或删除其他元素时必须保持有效

我希望有人可以解释该实现及其与C ++标准定义的适应性（就性能要求而言），如果它确实不是实现哈希图数据结构的最有效方法，则如何对其进行改进？

Answer 1

我在上面的回复回答了您的第二条评论，但只是注意到我从未回答过您的第一条评论。关于“实际上，它的确会逐渐降低……从（例如）100％充满到1000％充满” –由于最大负载因数而不会发生–表的大小调整为100％。但是，您并不是在谈论我提到的开放式散列的性能问题，这是当您擦除某个元素时，要么必须将存储桶标记为已使用并继续进行搜索（代价不菲） ），或将碰撞链“压缩”到铲斗中（较高的前期成本）。