哈希集可以用 O(1) 找到最小或最大元素吗？
我需要很好地理解哈希集的架构和功能。
与STL::set相比，哈希集与STL::set相比有什么优势？我认为进行搜索的时间为 O(1)。如果这是真的，为什么不使用哈希表呢？他们的区别是重复元素？或者其他人？
对于STL::set来说，最小/最大的搜索时间也是O(1)，因为它已经有序了。
哈希集不是二叉搜索树，如何以 O(1) 查找最小或最大元素？
我找不到答案。
我的想法：
什么时候应该使用哈希集而不是哈希表？
STL::set 是有序集。因此，获取最小/最大元素的时间复杂度为 O(1)。
如果对于哈希集怎么办？是订购的吗？
谢谢
I need to understand the architecture and functions of hash set very well.
Compared with STL::set, what is the advantage of hash set compared with STL::set ? I think the O(1) time to do search. If this is true, why not to use hash table ? Their difference is duplicated element ? or others ?
For STL::set, the search time of smallest/largest is also O(1), because it has been ordered.
A hash set is not a binary search tree, how to find the smallest or largest element with O(1) ?
After reading
What is the difference between set and hashset in C++ STL?
I cannot find the answer .
My idea:
When should use hash set not hash table ?
STL::set is ordered set. So, it is O(1) to get smallest/largest element.
What if for hash set ? it is ordered ?
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这正是关键区别之一：您无法在恒定时间内找到哈希集中的最小/最大元素。当然，您可以通过扫描整个集合在
O(n)时间内完成此操作。另一个关键区别是迭代哈希集不会按排序顺序返回元素。
This is exactly one of the key differences: you can't find the smallest/largest element in a hash set in constant time. You can, of course, do it in
O(n)time by scanning the entire set.Another key difference is that iterating over a hash set does not return the elements in sorted order.
哈希集基本上是一个没有存储值（只有键）的哈希表，C++ 中的 std::set 被实现为平衡二叉搜索树。
您应该阅读一些算法/计算机科学书籍中的差异，因为您似乎有一些基本的误解，例如，在二叉搜索树中，找到最小/最大元素的成本是对数
O(log N)，不是常数O(1)。根据您最常需要执行的操作，任一数据结构都更合适。如果您需要经常查找最小元素，那么
std::set将在O(log N)中执行操作，但是使用哈希表，您将需要检查所有元素，这意味着线性时间O(N)。另一方面，如果该操作不常见并且常规查找（集合中的元素 a 吗？）更常见，则哈希集的恒定时间查找将优于O(log N)在集合中查找。A hash set is basically a hash table without stored values (only keys), and
std::setin C++ are implemented as a balanced binary search tree.You should read on the differences in some algorithm/computer science book, as you seem to have some basic misconceptions, for example, in a binary search tree the cost of finding the smallest/largest element is logarithmic
O(log N), not constantO(1).Depending on the operations that you need to perform most often, either data structure will be more appropriate. If you need to find the smallest element quite often, then a
std::setwill perform the operation inO(log N), but with a hash table you will need to check all elements and that means linear timeO(N). If on the other hand that operation is not common and regular lookups (is element a in the set?) are more common, the constant time lookup of a hash set will be better thanO(log N)lookup in a set.