散列表 - 用于搜索不存在的密钥的时间复杂度

Question

让我们有一个带有n个键的散列表，每个键都有一个只有一个值的存储桶。 假设我们寻找一个在哈希表中不存在的关键字，那么这个操作的最坏时间复杂度是什么？

在我看来，它会是O（n）。散列函数将必须检查其所有密钥才能确定给定的密钥不存在于散列中。

您认为如何？我对吗？

Answer 1

这取决于实施。我希望时间复杂度为O（1），因为从本质上讲，散列表不会遍历元素来查找元素，而是直接在基于散列方法的内存中索引。超出O（1）的唯一时间是需要重新调整内存大小或遇到冲突时。当然，除此之外还有许多小细节，以及影响事物的散列算法之间的差异。这里是一个很好的线程来看看以了解更多信息：

Hash table runtime complexity (insert, search and delete)