C++：为什么 unordered_set::find 比 find 快？
C++: Why is unordered_set::find faster than find?
当我做的时候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 是 “最坏情况：容器大小呈线性关系” 而
find 是 “在第一个和最后一个之间的距离上达到线性：比较元素直到找到匹配项”。
它们 运行 次不一样吗？为什么我的代码 运行 时 unordered_set::find 更快？ std::find 是否正在做我所缺少的幕后工作？
这取决于它们的实施方式。 std::find 如您所料运行。从头开始比较每个元素，直到它到达终点。这是相当普遍的，但不会从所使用的特定数据结构中受益。但是，unordered_set 是一个哈希集，因此如果没有哈希冲突，则每个元素都需要相同的时间来查找。
之所以说存在“容器大小呈线性的最坏情况”，是因为如果散列 table 的长度为 1，则每个条目都将放在容器中的相同位置table（伪代码：table[hash(element) % table_length].push(element)）。如果发生这种情况，那么根据实现的不同，它最终可能看起来更像是内存中的列表，并且必须按顺序检查每个项目。但实际上，这可能永远不会发生。
无序集就像一个文件柜。假设您拥有一家公司所有员工的档案。文件柜有 26 个抽屉，每个抽屉都标有一个字母。每个员工的记录都按姓氏的第一个字母存储。抽屉中的文件没有进一步组织。
当 unordered_set::find 被告知要查找员工的记录时，它会直接进入标有姓氏首字母的抽屉并搜索该抽屉中的所有记录。当 std::find 被赋予相同的任务时，它从 top-left 抽屉开始并检查那里的所有记录，然后移动到它旁边的抽屉，依此类推，直到检查完所有抽屉或找到记录。 （注意 top-left 抽屉不一定是“A”。）
假设公司有 20 名员工。给定一个典型的名称分布，unordered_set::find 很可能会进入一个只有一条记录的抽屉，这就是您要查找的记录。也许它找到了两条记录。仍然快速和容易。如果您的哈希函数能够胜任这项任务，这代表了常见情况。同时，std::find 可能需要查看所有记录才能找到您要查找的记录。有时它会很幸运并立即找到它。平均来说，它会浏览一半的记录。
但是，典型的情况并不是最坏的情况。最坏的情况是，公司上一次招聘是在一次家庭聚会上，结果 20 名员工都被命名为“Jones”。通常快速 unordered_set::find 将直奔抽屉“J”，只为找到该抽屉中的每个员工记录。在找到所需的记录之前，它将平均浏览一半的记录，与 std::find.
相同
您应该关注典型时间还是 worst-case 时间？这取决于你的具体情况。有时，陷入最坏情况是有系统原因的，类似于在家庭聚会上招募。另一方面，如果名字是随机分布的，在这个例子中，在同一个抽屉里有 10 条（或更多）记录的机会大约是 5×1012 中的 1；真正最坏的情况甚至更少（涉及 1026）......通常你可以指望快速 look-ups.
当我做的时候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 是 “最坏情况：容器大小呈线性关系” 而 find 是 “在第一个和最后一个之间的距离上达到线性：比较元素直到找到匹配项”。
它们 运行 次不一样吗？为什么我的代码 运行 时 unordered_set::find 更快？ std::find 是否正在做我所缺少的幕后工作？
这取决于它们的实施方式。 std::find 如您所料运行。从头开始比较每个元素，直到它到达终点。这是相当普遍的，但不会从所使用的特定数据结构中受益。但是，unordered_set 是一个哈希集，因此如果没有哈希冲突，则每个元素都需要相同的时间来查找。
之所以说存在“容器大小呈线性的最坏情况”，是因为如果散列 table 的长度为 1，则每个条目都将放在容器中的相同位置table（伪代码：table[hash(element) % table_length].push(element)）。如果发生这种情况，那么根据实现的不同，它最终可能看起来更像是内存中的列表，并且必须按顺序检查每个项目。但实际上，这可能永远不会发生。
无序集就像一个文件柜。假设您拥有一家公司所有员工的档案。文件柜有 26 个抽屉，每个抽屉都标有一个字母。每个员工的记录都按姓氏的第一个字母存储。抽屉中的文件没有进一步组织。
当 unordered_set::find 被告知要查找员工的记录时，它会直接进入标有姓氏首字母的抽屉并搜索该抽屉中的所有记录。当 std::find 被赋予相同的任务时，它从 top-left 抽屉开始并检查那里的所有记录，然后移动到它旁边的抽屉，依此类推，直到检查完所有抽屉或找到记录。 （注意 top-left 抽屉不一定是“A”。）
假设公司有 20 名员工。给定一个典型的名称分布，unordered_set::find 很可能会进入一个只有一条记录的抽屉，这就是您要查找的记录。也许它找到了两条记录。仍然快速和容易。如果您的哈希函数能够胜任这项任务，这代表了常见情况。同时，std::find 可能需要查看所有记录才能找到您要查找的记录。有时它会很幸运并立即找到它。平均来说，它会浏览一半的记录。
但是，典型的情况并不是最坏的情况。最坏的情况是，公司上一次招聘是在一次家庭聚会上，结果 20 名员工都被命名为“Jones”。通常快速 unordered_set::find 将直奔抽屉“J”，只为找到该抽屉中的每个员工记录。在找到所需的记录之前，它将平均浏览一半的记录，与 std::find.
您应该关注典型时间还是 worst-case 时间？这取决于你的具体情况。有时，陷入最坏情况是有系统原因的，类似于在家庭聚会上招募。另一方面，如果名字是随机分布的，在这个例子中，在同一个抽屉里有 10 条（或更多）记录的机会大约是 5×1012 中的 1；真正最坏的情况甚至更少（涉及 1026）......通常你可以指望快速 look-ups.