C++:为什么 unordered_set::find 比 find 快？

Question

当我做 unordered_set::find

unordered_set<int> uniqueNum;

//code...
if(uniqueNum.find(num + k) != uniqueNum.end()) 
//code ...

这段代码的运行时间是 更快 比

unordered_set<int> uniqueNum;
        
//code...
if(find(uniqueNum.begin(), uniqueNum.end(), num + k) != uniqueNum.end()) 
//code...         

根据引用， unordered_set::find 是 “最坏的情况:容器大小呈线性”尽管
找到是 “第一个和最后一个之间的距离为线性:比较元素直到找到匹配项” .
它们不是相同的运行时吗？为什么在运行代码时 unordered_set::find 会更快？ std::find 是否在幕后做一些我遗漏的事情？

Answer 1

这是由于它们的实现方式。 std::find如您所料。从头开始比较每个元素，直到它到达结尾。这是相当普遍的，但不会从所使用的特定数据结构中受益。然而，unordered_set是一个散列集，因此如果没有散列冲突，则每个元素都需要相同的时间来查找。
之所以说“容器大小为线性的最坏情况”是因为如果哈希表的长度为 1，则每个条目都将放置在表中的相同位置(伪代码:table[hash(element) % table_length].push(element))。如果发生这种情况，则取决于实现，它最终可能看起来更像是内存中的列表，并且必须按顺序检查每个项目。但在实践中，这可能永远不会发生。