在寻找适合我正在构建的应用程序的容器时，我浏览了以下文档unordered_set。鉴于我的应用程序通常只需要insert and find函数，这个类看起来相当有吸引力。然而，我有点推迟了，因为find是 O(1) 摊销，但最坏情况是 O(n) - 我会经常使用该函数，它可能会成功或破坏我的应用程序。是什么导致复杂性激增？遇到 O(n) 搜索的可能性是可预测的吗？
_ unordered_set _ 实现为哈希表，也就是说，哈希表的常见实现之一是使用容器（例如：像向量）哈希桶（即容器（例如：喜欢列表）同一桶中 unordered_set 的元素的数量）。
当在 unordered_set 中插入元素时，会应用一个哈希函数，它会给出要放置的存储桶。
可能会在同一个存储桶中插入不同的元素，当您查找一个元素时，将应用哈希函数，为您提供存储桶，您需要去搜索您要查找的元素。
最坏的情况是所有元素都在同一个桶中（取决于用于存储同一桶中元素的容器，当所有元素都在同一个桶中时，O(n) 是搜索的最差运行时间）。
以同一桶结尾的元素的关键点是哈希函数（它有多好）和元素（可能暴露哈希函数的特定弱点）。
如果您的情况有足够的可预测性，则通常无法预测元素（您可以选择均匀分布此类元素的哈希函数）。
为了加快搜索速度，关键点是使用良好的哈希函数（将元素均匀分布在存储桶中，并在需要时使用重新哈希来增加存储桶大小（请注意此选项，哈希函数将应用于所有元素））。
我建议，如果这些元素的存储对于您的应用程序来说非常重要，那么您可以使用尽可能接近生产数据的性能测试（并从中做出决定），即 STL 中的容器以及同一组的容器（例如：关联等...）共享几乎相同的接口，很容易将一个接口更改为另一个接口，而所使用的代码几乎没有变化或没有变化。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
