rah*_*rma 6 c++ hash stl set unordered-set
为什么插入集合的最坏情况复杂度是容器大小的线性常数而不是元素本身的大小？
我专门谈论字符串。如果我有一个大小为 m 的字符串集，那么如果我插入一个大小为 x 的新字符串，我假设插入操作需要读取大小为 x 的字符串才能计算键？那么我们为什么不考虑那个时间呢？
如果还有另一个大小为 1000*x 的字符串，那么在最坏的情况下插入仍然需要 m 大小？无论字符串大小，时间都是0(m)？如何？
这是一个很好的问题，它触及了我们分析哈希表操作成本的方式中的一些细微差别。
实际上有几种不同的方式来思考这个问题。第一个是考虑哈希表上的操作的运行时间，从纯粹关注表大小的运行时角度来测量。从这个角度来看，插入、查找或删除的成本不会随着表元素数量的变化而变化。也就是说，查找某些内容的成本不取决于表中元素的数量，插入元素的成本不取决于表中元素的数量等等。从这个角度来看，如果我们让n表示表中的元素数量，则插入、删除或查找的成本为 O(1)，因为不依赖于n。
从这个意义上说，这里的大 O 表示法应该被解释为“如果唯一的变量是n（表中元素的数量），那么事情将如何扩展？” 但这还有很多不足之处，因为它完全忽略了比较字符串是否相等的成本、评估哈希函数的成本等。
如果您将这些细节考虑在内，那么是的，您是对的 - 从具有n 个元素的哈希表中查找、插入或删除长度为m 的字符串的成本是 O( m )，而不是 O(1)。
我一直认为最有帮助的观点如下。当哈希表说所有操作都在 O(1) 时间内运行时，它的真正含义是每个操作仅需要 O(1) 总哈希计算和比较。从这个意义上说，它意味着“查找某些内容、插入某些内容或删除某些内容的成本是一定数量的哈希计算和比较”。为了计算出总成本，您可以将 O(1) 乘以散列或比较的成本，在长度为m的字符串的情况下，其结果为 O( m )。这给出了 O( m ) 的总体运行时间，这符合你的直觉。