use*_*825 3 c++ unordered-map hashmap c++11
std::unordered_map 保证O(1)时间搜索,但它如何管理碰撞？
无序映射是一个关联容器,包含具有唯一键的键值对.元素的搜索,插入和删除具有平均的恒定时间复杂度.
假设所有哈希码都相同的情况,内部如何处理冲突？
如果哈希码对每个键都是唯一的,那么我的假设将完全错误.在这种情况下,如何在没有冲突的情况下创建唯一的哈希码？
std::unordered_map哈希函数采用什么方法来保证O(1)搜索？
它不保证O(1),平均为O(1)...最坏的情况是,当存在大量碰撞时,它可以是O(n).有关详细信息,请参阅以下链接:
更新
由于问题已经编辑,现在专门询问碰撞std::unordered_map,请看下面的答案:
我想我们可以得出结论,std :: unordered_set(或unordered_map)的所有实际实现几乎肯定都使用碰撞链接.虽然可能(几乎不可能)使用线性探测或双重散列来满足要求,但这样的实现似乎失去了很多并且几乎没有任何回报.
| 归档时间： |
|
| 查看次数： |
3606 次 |
| 最近记录： |