find方法在unordered_set<int>
中的时间复杂度是什么?
同时,是否可以更改哈希函数?
std::hash<int>{}( 2 )
可能会返回整数本身,但容器仍然必须探测并将该整数密钥与容器中包含的值进行比较。我不知道你期望什么样的魔法,但如果你有研究表明在所有情况下(即,密钥从未在存储中发生冲突),都可以实现 O(1),那么请分享一下。 - KABoissonneault我猜您可能会因为默认的最大负载系数为1而感到困惑。当您向unordered_set中插入一个int x时,它会进入桶i(i = x%桶的数量)。因此,即使哈希函数没有冲突,因为它将每个int映射到自身,但取模运算在某些情况下可能会发生“冲突”。例如,如果您按顺序插入1、4和6,则1和6都将在同一个桶中,并且find函数需要通过桶来找到它们。只有在负载系数达到最大负载系数时才会增加桶的数量。负载系数是每个桶中元素数量的算术平均值。因此,您实际上可以在每个桶中拥有多个元素,甚至可以将所有元素都放在同一个桶中。在这种情况下,查找集合中存在的元素需要对桶进行传统的顺序搜索(O(n))。以下是一个示例:
unordered_set<int> n;
n.insert(1);
n.insert(12);
n.insert(23);
n.insert(34);
n.insert(45);
unordered_set
的Hash
模板参数或为您的类型专门化std::hash<T>
模板来更改哈希函数。 - KABoissonneault