unordered_set的时间复杂度 找到方法

Question

什么是find中unordered_set<int>方法的时间复杂度？

还有可能改变哈希函数吗？

Answer 1

unordered_set中find方法的时间复杂度是多少？

...它就在您链接的页面中：

复杂：

平均情况：不变。

最坏情况：容器尺寸呈线性。

---

还有可能改变哈希函数吗？

是。再次，看看at the documentation！

std::unordered_map采用Hash模板参数。这是一个自定义点，您可以注入自己的散列逻辑。定制Hash必须满足Hash概念。

Answer 2

我猜你会被默认的max_load_factor弄为1。当你在unordered_set中插入一个int x时，它会进入存储桶i（i = x％桶数）。因此，您可以想象即使哈希函数不会发生冲突，因为它会将每个int与自身进行映射，因此在某些情况下，mod操作可能会出现“冲突”。例如，如果按顺序插入1,4和6，则1和6将位于同一个存储桶中，并且find函数需要通过存储桶才能找到它们。只有当负载系数达到最大负载系数时，才会增加桶数。负载系数是每个桶的元素数的算术平均值。因此，您实际上每个存储桶中可以有多个元素，甚至可以在同一个存储桶中包含所有元素。在这种情况下，找到集合内部的元素需要在桶内进行传统的secuencial搜索（O（n））。这里有一个例子：

unordered_set<int> n;
n.insert(1);
n.insert(12);
n.insert(23);
n.insert(34);
n.insert(45);

在这种情况下，每个int都在桶1中，因此当您查找56（56％11 = 1）时，您需要遍历整个桶（大小为n，O（n））。负载系数为0.4545（5个元件/ 11个桶），因此不添加任何桶。您可以减少max_load_factor（某些语言使用0.75的加载因子），但这会增加重新加入的次数，因为您需要更频繁地保留桶（保留过程是分摊的常量，因为它使用相同的方法std :: vector使用，这就是为什么在这个例子中我们有11个桶）