Unordered_Map查找时间 [英] Unordered_Map Lookup Time

问题描述

C ++库中的内置映射和集合(包括unordered_map和multimap)要求find函数(用于查找特定元素)使用迭代器遍历元素. C ++参考站点声称，使用这些数据结构查找元素平均需要花费恒定时间，这与常规哈希表非常相似.但是，迭代器在查找元素之前是否不必遍历整个列表，平均花费O(n)时间?

The built in maps and sets in C++ libraries (including unordered_map and multimap) requires that the find function (used to lookup a specific element) utilize an iterator for traversing the elements. The C++ reference site claims that looking up elements using these data structures takes on average constant time, much like a regular hash table. But wouldn't an iterator have to traverse the entire list, making this O(n) time on average, before finding the element?

推荐答案

您的陈述不正确:

• map，set，multimap和multiset通常被实现为二叉树(例如:在VS中被实现为Red Black Trees)，在这种情况下，find方法使用以下属性搜索关键字:在一个节点中，left child is less大于节点(根据比较器)，而the right child is greater大于节点(根据比较器).根据标准要求，该值为 O(log n).
• 在unordered_map和unordered_set被实现为哈希表的情况下，通常被实现为存储桶的集合(例如:std::vector<Bucket>)，而存储桶被实现为unordered_map的元素的集合(例如:std::vector<elem>或std::list<elem>)，假设散列函数是恒定时间(或不包括时间)，则此集合中的搜索以平均恒定时间 O(1)(散列为元素所在的存储桶，如果在搜索到目标elem之间的存储桶中几乎没有elem).最坏的情况是所有元素都在同一个存储桶中，在这种情况下，对目标元素的搜索将需要遍历存储桶中的所有元素，直到找到为止(在 O(n)中).借助良好的哈希功能，您可以充分地提高桶中元素的分割概率(获得预期的恒定时间).

• map, set, multimap and multiset are normally implemented as binary trees (ex: in VS are implemented as Red Black Trees), the find method in this case search the key using the property that in one node the left child is less than the node (according to the comparer) and the right child is greater than the node (according to the comparer). This give O(log n), as required by the standard.
• In the case of unordered_map and unordered_set are implemented as hash tables, normally implemented as a collection of buckets (ex: std::vector<Bucket>) and the bucket is implemented as a collection of elements of the unordered_map (ex: std::vector<elem> or std::list<elem>), assuming that hashing function is constant time (or excluding the time), the search in this collections is in average constant time O(1) (the hashing give the bucket where the element are placed, if there are few elem in the bucket search between then the target elem). The worst case is when all elements are in the same bucket in this case the search of the target element would need to iterate through all elements in the bucket until found or not (in O(n)). With good hashing function you could increase probability of split evenly enough the elem in the bucket (obtaining the expected constant time).

注意:find函数返回一个iterator，这并不意味着使用迭代器来搜索所请求的元素.

Note: the find function return a iterator that don't mean that use iterator to search the requested element.

这篇关于Unordered_Map查找时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！