C ++-unordered_map复杂度 [英] c++ - unordered_map complexity

问题描述

我需要创建一个查找函数，其中（X，Y）对对应于特定的Z值。对此的一个主要要求是，我需要以尽可能接近O（1）的复杂度进行操作。我的计划是使用unordered_map。

I need to create a lookup function where a (X,Y) pair corresponds to a specific Z value. One major requirement for this is that I need to do it in as close to O(1) complexity as I can. My plan is to use an unordered_map.

我通常不使用哈希表进行查找，因为查找时间对我而言从来都不重要。我是否正确地认为只要构建无冲突的unordered_map，我的查找时间将是O（1）？

I generally do not use a hash table for lookup, as the lookup time has never been important to me. Am I correct in thinking that as long as I built the unordered_map with no collisions, my lookup time will be O(1)?

那么我所关心的就是复杂性会变成什么如果该密钥在无序映射中不存在。例如，如果我使用unordered_map :: find（）：来确定哈希表中是否存在键，它将如何给我答案？

My concern then is what the complexity becomes if there the key is not present in the unordered map. If I use unordered_map::find():, for example, to determine whether a key is present in my hash table, how will it go about giving me an answer? Does it actually iterate over all the keys?

我非常感谢您的帮助。

推荐答案

标准或多或少要求使用存储桶来解决
的冲突，这意味着实际查找时间
可能相对于
中的元素数量呈线性关系桶，无论元素是否存在。
可以将其设为O（lg N），但通常不会这样做，
是因为存储区中的元素数量应该很小，如果$ <
哈希表使用正确。

The standard more or less requires using buckets for collision resolution, which means that the actual look up time will probably be linear with respect to the number of elements in the bucket, regardless of whether the element is present or not. It's possible to make it O(lg N), but it's not usually done, because the number of elements in the bucket should be small, if the hash table is being used correctly.

为确保存储桶中的元素数量很少，您必须确保哈希功能有效。
的有效含义取决于散列的类型和值。
（MS实现使用FNV，这是周围最好的
通用哈希之一，但是如果您对
实际数据有特殊的了解，则可以
可以帮助减少每个
桶中元素数量的另一件事是强制使用更多的桶或使用较小的负载系数。
首先，您可以将
个存储桶的最小初始数目作为参数传递给构造函数。如果您知道
个元素在地图中的总数，则可以
这样控制负载因子。填满表格后，您还可以通过调用
rehash 来创建最少数量的
个存储桶。否则，您可以使用函数
std :: unordered_map<> :: max_load_factor 。
不能保证做任何事情，但是在任何合理的
实施中，它都会做。请注意，如果您在已填充
的 unordered_map 中使用它，则可能必须调用
unordered_map<> :: rehash 之后。

To ensure that the number of elements in a bucket is small, you must ensure that the hashing function is effective. What effective means depends on the types and values being hashed. (The MS implementation uses FNV, which is one of the best generic hashs around, but if you have special knowledge of the actual data you'll be seeing, you might be able to do better.) Another thing which can help reduce the number of elements per bucket is to force more buckets or use a smaller load factor. For the first, you can pass the minimum initial number of buckets as an argument to the constructor. If you know the total number of elements that will be in the map, you can control the load factor this way. You can also forse a minumum number of buckets once the table has been filled, by calling rehash. Otherwise, there is a function std::unordered_map<>::max_load_factor which you can use. It is not guaranteed to do anything, but in any reasonable implementation, it will. Note that if you use it on an already filled unordered_map, you'll probably have to call unordered_map<>::rehash afterwards.

（关于标准
unordered_map，我不了解几件事：为什么加载因子是 float ，而不是
double ；为何不要求有效果；为什么
不会自动为您调用 rehash 。）

(There are several things I don't understand about the standard unordered_map: why the load factor is a float, instead of double; why it's not required to have an effect; and why it doesn't automatically call rehash for you.)

这篇关于C ++-unordered_map复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！