文档提到 std::unordered_map 使用哈希表。它如何实现对哈希表中特定键的 O(1) 查找？我能想到的唯一方法是将每个键存储在一个地址，该地址是根据它所持有的数据的哈希值计算得出的。如果是这种情况，它如何将所有 key 在内存中保持在一起，以免很快用完？此外，如果使用多个 std::unordered_map 怎么办？该实现如何保证没有两个映射会计算归结为同一地址的哈希值？

最佳答案

O(1) 并不意味着算法的复杂性是“一次性”，或者在这种情况下， map 中的值必须通过某种形式的单次查找来检索，基于它的 key 。

O(1) 的真正意思是 O(amortized constant)，即:它需要固定的时间才能完成，平均而言。

无序映射的一种可能实现方式是哈希表，其中包含具有相同哈希键的所有值的链表，无序映射会根据需要动态调整哈希表的大小。偶尔的 map 查找完全有可能必须搜索一个小链表才能找到正确的哈希键。此外，偶尔，插入或删除操作会花费额外的时间来重新散列整个无序映射。

如果您在引用资料中查找无序映射方法的详细信息，您会发现它明确提到如果修改触发重新散列，则无序映射的所有现有方法都会失效。

但是，平均，预计无序 map 查找将花费固定的时间。

https://stackoverflow.com/questions/70621067/