插入和搜索时哈希表的时间复杂度
Time complexity for hash tables when inserting and searching
看Wikipedia的哈希表，说插入和查找是O(1)。但我担心的是，我的老师告诉我只有查找是 O(1) 并且散列是 O(s)，其中s字符串的长度。插入和搜索不应该是 O(s) 吗？它说哈希（s）+查找（s）= O（哈希（s）+查找（s））= O（s）。
谁能解释一下用大 O 表示法为哈希表编写时间复杂度的正确方法是什么，为什么？如果假设它是完美散列并且没有发生冲突。
这个问题和我问的一个问题非常相似：Is a lookup in a hash table O(1)?
公认的答案是，对于哈希表，"time" 是通过比较而不是操作来衡量的。这是完整的答案，引用：
What is wrong with your reasoning is the use of conflicting
definitions of "time".
When one says that lookup in a hash table takes O(1) time, one usually
means that it takes O(1) comparisons, that is, the number of
comparisons required to find an item is bounded above by a constant.
Under this idea of "time", the actual time (as in the thing you would
measure in seconds) used to compute the hash causes no variation.
Measuring time in comparisons is an approximation that, while it may
not reflect reality in the same way that measuring it in seconds
would, still provides useful information about the behaviour of the
hash table.
This sort of thing is true for most asymptotic complexity descriptions
of algorithms: people often use "time" with a very abstract meaning
that isn't the informal meaning of "time", but more often than not is
some variation of "number of operations" (with the kind of operation
often left unstated, expected to be obvious, or clear from context).
哈希 table 不仅仅用于字符串。插入和查找的 O(1) 复杂度通常用于散列 tables，并且只计算已知操作。
散列和比较计算为 O(1)，因为必须始终对这些进行 某些事情，即使您只是存储整数，但我们不知道那是什么。
如果您对某些数据类型（如字符串）使用散列 table，这会使这些操作的成本成倍增加，那么复杂性也会成倍增加。
在衡量使用散列table的具体算法的复杂性时，考虑这一点实际上非常重要。例如，该站点上的许多基于字符串的算法都基于输入字符串的长度受某个常数限制的假设而被赋予了复杂性。值得庆幸的是，情况通常如此。
看Wikipedia的哈希表，说插入和查找是O(1)。但我担心的是，我的老师告诉我只有查找是 O(1) 并且散列是 O(s)，其中s字符串的长度。插入和搜索不应该是 O(s) 吗？它说哈希（s）+查找（s）= O（哈希（s）+查找（s））= O（s）。
谁能解释一下用大 O 表示法为哈希表编写时间复杂度的正确方法是什么，为什么？如果假设它是完美散列并且没有发生冲突。
这个问题和我问的一个问题非常相似：Is a lookup in a hash table O(1)?
公认的答案是，对于哈希表，"time" 是通过比较而不是操作来衡量的。这是完整的答案，引用：
What is wrong with your reasoning is the use of conflicting definitions of "time".
When one says that lookup in a hash table takes O(1) time, one usually means that it takes O(1) comparisons, that is, the number of comparisons required to find an item is bounded above by a constant. Under this idea of "time", the actual time (as in the thing you would measure in seconds) used to compute the hash causes no variation.
Measuring time in comparisons is an approximation that, while it may not reflect reality in the same way that measuring it in seconds would, still provides useful information about the behaviour of the hash table.
This sort of thing is true for most asymptotic complexity descriptions of algorithms: people often use "time" with a very abstract meaning that isn't the informal meaning of "time", but more often than not is some variation of "number of operations" (with the kind of operation often left unstated, expected to be obvious, or clear from context).
哈希 table 不仅仅用于字符串。插入和查找的 O(1) 复杂度通常用于散列 tables，并且只计算已知操作。
散列和比较计算为 O(1)，因为必须始终对这些进行 某些事情，即使您只是存储整数，但我们不知道那是什么。
如果您对某些数据类型（如字符串）使用散列 table，这会使这些操作的成本成倍增加，那么复杂性也会成倍增加。
在衡量使用散列table的具体算法的复杂性时，考虑这一点实际上非常重要。例如，该站点上的许多基于字符串的算法都基于输入字符串的长度受某个常数限制的假设而被赋予了复杂性。值得庆幸的是，情况通常如此。