C++ 无序集字符串散列时间复杂度？
C++ Unordered Set string hash time complexity?
为什么插入集合的最坏情况复杂度是容器大小的线性常量而不是元素本身的大小？
我专门说字符串。如果我有一个大小为 m 的字符串集，那么如果我插入一个大小为 x 的新字符串，我假设插入操作需要读取大小为 x 的字符串才能计算键？那我们为什么不考虑那个时间呢？
如果有另外一个大小为1000*x的字符串，那么插入在最坏的情况下仍然需要m大小？
不管字符串大小，时间都是0(m)？怎么样？
这是一个很好的问题，它在我们分析哈希操作成本的方式中遇到了一些细微差别 tables。
实际上有几种不同的思考方式。第一个是考虑对哈希 table 的操作的 运行 次，用 运行 时间的角度来衡量，纯粹关注 table 的大小。从这个角度来看，插入、查找或删除的成本不会 作为 table 个元素 数量的函数。也就是说，查找某物的成本不取决于 table 中元素的数量，插入元素的成本不取决于 table 中元素的数量，等等。从这个角度来看，如果我们让 n 表示 table 中的元素数量，那么插入、删除或查找的成本是 O(1)，因为不依赖 n.
从这个意义上说，这里的big-O表示法被解释为“如果唯一的变量是n，[=41中的元素数量=]，事情将如何扩展？”但这还有很多不足之处，因为它完全忽略了比较字符串是否相等的成本、评估哈希函数的成本等。
如果您将这些细节考虑在内，那么是的，您是对的 - 从散列中查找、插入或删除长度为 m 的字符串的成本 table 与 n 个元素是 O(m)，而不是 O(1).
我一直认为最有帮助的观点如下。当一个散列 table 说所有操作 运行 时间 O(1) 时，它真正的意思是每个操作只需要 O(1) 总散列评估和比较。从这个意义上说，它意味着“查找某物、插入某物或删除某物的成本是一定数量的哈希评估和比较。”然后计算总成本，然后将 O(1) 乘以散列或比较的成本，在长度为 m 的字符串的情况下将是 O(m)。这给了你 O(m) 的总 运行 时间，这符合你的直觉。
根据对元素类型 的原始操作，标准给出了容器中元素数量函数的复杂性。这些原始操作由实例化提供。
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on
the contained objects. [Example: The copy constructor of type vector<vector<int>> has linear complexity,
even though the complexity of copying each contained vector<int> is itself linear. — end example]
例如，这里描述了 operator== 在无序关联容器上的复杂性：
For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the == operator of the value_type, to the predicate returned by key_eq(), and to the hasher returned by hash_function()) is proportional to N in the average case and to N2 in the worst case, where N is a.size().
如果您需要其他运算的复杂性，例如小整数算术运算，您可以自己推导它，前提是您知道在这些方面对元素类型的每个运算的复杂性。
为什么插入集合的最坏情况复杂度是容器大小的线性常量而不是元素本身的大小？
我专门说字符串。如果我有一个大小为 m 的字符串集，那么如果我插入一个大小为 x 的新字符串，我假设插入操作需要读取大小为 x 的字符串才能计算键？那我们为什么不考虑那个时间呢？
如果有另外一个大小为1000*x的字符串，那么插入在最坏的情况下仍然需要m大小？ 不管字符串大小，时间都是0(m)？怎么样？
这是一个很好的问题，它在我们分析哈希操作成本的方式中遇到了一些细微差别 tables。
实际上有几种不同的思考方式。第一个是考虑对哈希 table 的操作的 运行 次，用 运行 时间的角度来衡量，纯粹关注 table 的大小。从这个角度来看，插入、查找或删除的成本不会 作为 table 个元素 数量的函数。也就是说，查找某物的成本不取决于 table 中元素的数量，插入元素的成本不取决于 table 中元素的数量，等等。从这个角度来看，如果我们让 n 表示 table 中的元素数量，那么插入、删除或查找的成本是 O(1)，因为不依赖 n.
从这个意义上说，这里的big-O表示法被解释为“如果唯一的变量是n，[=41中的元素数量=]，事情将如何扩展？”但这还有很多不足之处，因为它完全忽略了比较字符串是否相等的成本、评估哈希函数的成本等。
如果您将这些细节考虑在内，那么是的，您是对的 - 从散列中查找、插入或删除长度为 m 的字符串的成本 table 与 n 个元素是 O(m)，而不是 O(1).
我一直认为最有帮助的观点如下。当一个散列 table 说所有操作 运行 时间 O(1) 时，它真正的意思是每个操作只需要 O(1) 总散列评估和比较。从这个意义上说，它意味着“查找某物、插入某物或删除某物的成本是一定数量的哈希评估和比较。”然后计算总成本，然后将 O(1) 乘以散列或比较的成本，在长度为 m 的字符串的情况下将是 O(m)。这给了你 O(m) 的总 运行 时间，这符合你的直觉。
根据对元素类型 的原始操作，标准给出了容器中元素数量函数的复杂性。这些原始操作由实例化提供。
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [Example: The copy constructor of type
vector<vector<int>>has linear complexity, even though the complexity of copying each containedvector<int>is itself linear. — end example]
例如，这里描述了 operator== 在无序关联容器上的复杂性：
For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the
==operator of thevalue_type, to the predicate returned bykey_eq(), and to the hasher returned byhash_function()) is proportional to N in the average case and to N2 in the worst case, where N isa.size().
如果您需要其他运算的复杂性，例如小整数算术运算，您可以自己推导它，前提是您知道在这些方面对元素类型的每个运算的复杂性。