<分区>
std::unordered_map 保证 O(1) 时间搜索，但它如何管理冲突？
Cppreference claim
Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.
假设所有哈希码都相同的情况，内部如何处理冲突？
如果哈希码对每个键都是唯一的，我的假设就完全错误了。在那种情况下，如何在完全没有冲突的情况下创建唯一的哈希码？
std::unordered_map 的哈希函数采用什么方法来保证 O(1) 搜索？
最佳答案
它不能保证 O(1)，它平均是 O(1)...当有很多碰撞时，最坏的情况可能是 O(n)。请参阅下面的链接，了解更多信息:
https://stackoverflow.com/a/2771398/5874704
更新
由于问题已被编辑，现在专门询问 std::unordered_map 的冲突，请查看以下答案:
https://stackoverflow.com/a/21519560/5874704
I think we can conclude that all practical implementations of std::unordered_set (or unordered_map) almost certainly use collision chaining. While it might be (just barely) possible to meet the requirements using linear probing or double hashing, such an implementation seems to lose a great deal and gain nearly nothing in return.
关于c++ - std::unordered_map 如何处理冲突？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37026792/