如何实现std :: unordered_map

Question

这是我之前提出的一个问题，我发现我对如何实现unordered_map感到困惑。我敢肯定，其他许多人也会与我混淆。根据我不阅读标准而知道的信息：每个unordered_map实现都将一个链接列表存储到存储桶数组中的外部节点上……不，这根本不是最通用的实现哈希映射的最有效方法。不幸的是，unordered_map规范中的一个小“疏忽”几乎都需要这种行为。必需的行为是，元素的迭代器在插入或删除其他元素时必须保持有效我希望有人可以解释该实现及其与C ++标准定义的适应性（就性能要求而言），如果它确实不是实现哈希图数据结构的最有效方法，则如何对其进行改进？

Answer 1

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