algorithm - 插入和搜索时哈希表的时间复杂度

Question

查看维基百科的哈希表，它说插入和搜索是O(1)。但我担心的是，我的老师告诉我只有查找是O(1)并且散列是O(s)，其中s是字符串的长度。插入和搜索不应该是O(s)。它说散列（s）+查找（s）= O（散列（s）+查找（s））= O（s）。

谁能解释一下用大 O 表示法为哈希表编写时间复杂度的正确方法是什么，为什么？如果假设它是完美的散列并且没有发生冲突。

标签： algorithmtime-complexitybig-ohashtable

Answer 1

哈希表不仅仅用于字符串。插入和查找的 O(1) 复杂性通常适用于哈希表，并且只计算已知操作。

散列和比较算作 O(1)，因为必须始终为它们做一些事情，即使你只是存储整数，但我们不知道那是什么。

如果您对某些数据类型（如字符串）使用哈希表，这会使这些操作的成本成倍增加，那么复杂性也会成倍增加。

在测量使用哈希表的具体算法的复杂性时，考虑这一点实际上非常重要。例如，此站点上的许多基于字符串的算法都基于输入字符串的长度受某个常数限制的假设而被赋予复杂性。值得庆幸的是，情况通常如此。