哈希表操作的时间复杂度是O(1)还是O(N)？

Question

当回答数据结构算法问题时，如果我们使用哈希表（比如Java集合框架中的哈希表）来解决问题，我们应该考虑哈希表的底层复杂度，还是可以安全地假设它为O(1)？

我看到很多帖子将其视为O(1)，但我想知道为什么我们要忽略Java执行的操作，比如运行哈希算法来获取给定键的值？

- Venkata Gopi Kolla

---

哈希表的时间复杂度是常数级别，常数时间的大O表示法为O(1)。这与哈希表中项的数量无关。 - iblamefish

Answer 1

要回答你的问题，你需要考虑哈希表的工作原理。哈希表本质上是将键映射到其值的数组。每个键在数组中的位置取决于哈希函数（哈希函数将输入映射到单个输出值）。假设哈希函数是O(1)。

插入一个值：

如果我们想要将某些东西插入哈希表中，我们使用哈希函数(f)在键上定位一个存储位置，然后将该值存储在该位置。每次我们将某些东西插入数组中，它都需要O(1)时间，因为哈希函数是O(1)。搜索哈希表中的值也是如此。

搜索一个值：

如果我们想要搜索一个值x，我们必须解决f(x)，这将告诉我们x在哈希表中的位置。这意味着搜索哈希表也将是O(1)。

承认底层复杂性：

以上答案是正确的，但仅当哈希函数从不为任何给定输入产生相同的输出时（这可能很难实现）。这意味着哈希函数有时会使用替代方法来避免这种冲突。这些替代方法通常是O(1)到达第一个位置，但需要其他操作（例如线性搜索）以找到空位置。

基本上，哈希表操作（插入和搜索）是O(1)，但在表中存在冲突的情况下（多个键指向同一位置），这些操作可能需要更长的时间。

- iSeeJay